En el álgebra lineal y la teoría matroide , la conjetura de la base de Rota es una conjetura no probada sobre reordenamientos de bases , que lleva el nombre de Gian-Carlo Rota . Establece que, si X es un espacio vectorial de dimensión n o más generalmente una matroide de rango n , con n bases disjuntas B i , entonces es posible organizar los elementos de estas bases en una matriz n × n de tal manera que las filas de la matriz son exactamente las bases dadas y las columnas de la matriz también son bases. Es decir, debería ser posible encontrar un segundo conjunto de n bases disjuntas C i , cada una de las cuales consta de un elemento de cada una de las bases B i .
Ejemplos de
La conjetura básica de Rota tiene una formulación simple para puntos en el plano euclidiano : establece que, dados tres triángulos con vértices distintos, con cada triángulo coloreado con uno de tres colores, debe ser posible reagrupar los nueve vértices del triángulo en tres "arco iris". triángulos que tienen un vértice de cada color. Todos los triángulos deben ser no degenerados, lo que significa que no tienen los tres vértices en una línea.
Para ver esto como una instancia de la conjetura base, se puede usar la independencia lineal de los vectores ( x i , y i , 1) en un espacio vectorial real tridimensional (donde ( x i , y i ) son las coordenadas cartesianas de los vértices del triángulo) o, de manera equivalente, se puede usar una matroide de rango tres en la que un conjunto S de puntos es independiente si | S | ≤ 2 o S forma los tres vértices de un triángulo no degenerado. Para este álgebra lineal y este matroide, las bases son exactamente los triángulos no degenerados. Dados los tres triángulos de entrada y los tres triángulos del arco iris, es posible organizar los nueve vértices en una matriz de 3 × 3 en la que cada fila contiene los vértices de uno de los triángulos de un solo color y cada columna contiene los vértices de uno de los triángulos arcoiris.
De manera análoga, para los puntos en el espacio euclidiano tridimensional, la conjetura establece que los dieciséis vértices de cuatro tetraedros no degenerados de cuatro colores diferentes pueden reagruparse en cuatro tetraedros arco iris.
Resultados parciales
La declaración de la conjetura de base de Rota fue publicada por primera vez por Huang & Rota (1994) , acreditándola (sin citar) a Rota en 1989. [1] La conjetura de base ha sido probada para pavimentar matroides (para todos n ) [2] y el caso n ≤ 3 (para todos los tipos de matroide). [3] Para matroides arbitrarios, es posible organizar los elementos base en una matriz cuyas primeras columnas Ω ( √ n ) son bases. [4] La conjetura de base para álgebras lineales sobre campos de característica cero y para valores pares de n se seguiría de otra conjetura sobre cuadrados latinos de Alon y Tarsi. [1] [5] Con base en esta implicación, se sabe que la conjetura es cierta para álgebras lineales sobre los números reales para un número infinito de valores de n . [6]
Problemas relacionados
En conexión con el teorema de Tverberg , Bárány y Larman (1992) conjeturaron que, para cada conjunto de r ( d + 1) puntos en el espacio euclidiano d- dimensional , coloreados con d + 1 colores de tal manera que hay r puntos de cada color, hay una manera de dividir los puntos en simples arco iris (conjuntos de puntos d + 1 con un punto de cada color) de tal manera que los cascos convexos de estos conjuntos tengan una intersección no vacía. [7] Por ejemplo, el caso bidimensional (probado por Bárány y Larman) con r = 3 establece que, por cada conjunto de nueve puntos en el plano, coloreados con tres colores y tres puntos de cada color, es posible divide los puntos en tres triángulos arco iris que se cruzan, una declaración similar a la conjetura básica de Rota que establece que es posible dividir los puntos en tres triángulos arco iris no degenerados. La conjetura de Bárány y Larman permite considerar un triple colineal de puntos como un triángulo arcoíris, mientras que la conjetura básica de Rota no lo permite; por otro lado, la conjetura básica de Rota no requiere que los triángulos tengan una intersección común. Blagojević, Matschke & Ziegler (2009) hicieron un progreso sustancial en la conjetura de Bárány y Larman . [8]
Ver también
- Conjetura de Rota , una conjetura diferente de Rota sobre álgebra lineal y matroides
Referencias
- ^ a b Huang, Rosa; Rota, Gian-Carlo (1994), "Sobre las relaciones de varias conjeturas sobre cuadrados latinos y coeficientes de enderezamiento", Matemáticas discretas , 128 (1-3): 225-236, doi : 10.1016 / 0012-365X (94) 90114- 7 , MR 1271866. Ver en particular la Conjetura 4, p. 226.
- ^ Geelen, Jim ; Humphries, Peter J. (2006), "Conjetura de base de Rota para pavimentar matroides" (PDF) , SIAM Journal on Discrete Mathematics , 20 (4): 1042-1045, CiteSeerX 10.1.1.63.6806 , doi : 10.1137 / 060655596 , MR 2272246.
- ^ Chan, Wendy (1995), "An exchange property of matroid", Discrete Mathematics , 146 (1-3): 299-302, doi : 10.1016 / 0012-365X (94) 00071-3 , MR 1360125.
- ^ Geelen, Jim ; Webb, Kerri (2007), "Conjetura sobre la base de Rota" (PDF) , SIAM Journal on Discrete Mathematics , 21 (3): 802–804, doi : 10.1137 / 060666494 , MR 2354007.
- ^ Onn, Shmuel (1997), "Una identidad determinante colorida, una conjetura de Rota y cuadrados latinos", The American Mathematical Monthly , 104 (2): 156-159, doi : 10.2307 / 2974985 , JSTOR 2974985 , MR 1437419.
- ^ Glynn, David G. (2010), "Las conjeturas de Alon-Tarsi y Rota en dimensión prima menos uno", SIAM Journal on Discrete Mathematics , 24 (2): 394–399, doi : 10.1137 / 090773751 , MR 2646093.
- ^ Bárány, I .; Larman, DG (1992), "Una versión coloreada del teorema de Tverberg", Journal of the London Mathematical Society , Second Series, 45 (2): 314–320, CiteSeerX 10.1.1.108.9781 , doi : 10.1112 / jlms / s2- 45.2.314 , MR 1171558.
- ^ Blagojević, Pavle VM; Matschke, Benjamin; Ziegler, Günter M. (2009), Límites óptimos para el problema de Tverberg coloreado , arXiv : 0910.4987 , Bibcode : 2009arXiv0910.4987B.
enlaces externos
- Conjetura básica de Rota , Open Problem Garden.