Representación matroide

Representación combinatoria abstracta de vectores linealmente independientes

En la teoría matemática de las matroides , una representación matroide es una familia de vectores cuya relación de independencia lineal es la misma que la de una matroide dada. Las representaciones matroides son análogas a las representaciones grupales ; Ambos tipos de representación proporcionan estructuras algebraicas abstractas (matroides y grupos, respectivamente) con descripciones concretas en términos de álgebra lineal .

A matroid lineal es un matroid que tiene una representación, y un F - lineal matroid (para un campo F ) es un matroid que tiene una representación usando un espacio vectorial sobre F . La teoría de la representación matroide estudia la existencia de representaciones y las propiedades de las matroides lineales.

Definiciones

Un matroide (finito) ${\displaystyle (E,{\mathcal {I}})}$está definido por un conjunto finito ${\displaystyle E}$(los elementos de la matroide) y una familia no vacía ${\displaystyle {\mathcal {I}}}$ de los subconjuntos de ${\displaystyle E}$, llamados conjuntos independientes de la matroide. Se requiere para satisfacer las propiedades de que todo subconjunto de un conjunto independiente es en sí mismo independiente, y que si un conjunto independiente${\displaystyle A}$ es más grande que un segundo conjunto independiente ${\displaystyle B}$ entonces existe un elemento ${\displaystyle x\in A\setminus B}$ que se puede agregar a ${\displaystyle B}$para formar un conjunto independiente más grande. Uno de los ejemplos motivadores clave en la formulación de matroides fue la noción de independencia lineal de los vectores en un espacio vectorial : si${\displaystyle E}$ es un conjunto finito o multi-conjunto de vectores, y ${\displaystyle {\mathcal {I}}}$ es la familia de subconjuntos linealmente independientes de ${\displaystyle E}$, luego ${\displaystyle (E,{\mathcal {I}})}$es una matroide. ^{[1] [2]}

De manera más general, si ${\displaystyle (E,{\mathcal {I}})}$ es cualquier matroide, entonces una representación de ${\displaystyle (E,{\mathcal {I}})}$ puede definirse como una función ${\displaystyle f}$ que mapas ${\displaystyle E}$ a un espacio vectorial ${\displaystyle V}$, con la propiedad de que un subconjunto ${\displaystyle A}$ de ${\displaystyle E}$ es independiente si y solo si ${\displaystyle f|_{A}}$ es inyectable y ${\displaystyle f(A)}$es linealmente independiente. Una matroide con una representación se llama matroide lineal, y si${\displaystyle V}$es un espacio vectorial sobre el campo F, entonces la matroide se llama F -matroide lineal. Por lo tanto, las matroides lineales son exactamente las matroides que son isomórficas a las matroides definidas a partir de conjuntos o multijuegos de vectores. La función${\displaystyle f}$será uno a uno si y solo si el matroide subyacente es simple (no tiene conjuntos dependientes de dos elementos). Las representaciones matroides también pueden describirse más concretamente usando matrices sobre un campo F , con una columna por elemento matroide y con un conjunto de elementos que son independientes en la matriz si y solo si el conjunto correspondiente de columnas de la matriz es linealmente independiente. La función de rango de una matriz lineal viene dada por el rango de la matriz de las submatrices de esta matriz, o de manera equivalente, por la dimensión del intervalo lineal de subconjuntos de vectores. ^[3]

Caracterización de matroides lineales

El matroide de Vámos , no lineal sobre ningún campo

La configuración de Perles , lineal sobre los reales pero no los racionales

No todas las matroides son lineales; la matroide Vámos de ocho elementos es una de las matroides más pequeñas que es irrepresentable en todos los campos. ^[4] Si un matroide es lineal, puede representarse en algunos campos, pero no en todos. Por ejemplo, la matriz de rango tres de nueve elementos definida por la configuración de Perles es representable sobre los números reales pero no sobre los números racionales .

Las matroides binarias son las matroides que se pueden representar sobre el campo finito GF (2) ; son exactamente las matroides que no tienen la matroide uniforme ${\displaystyle U{}_{4}^{2}}$como menor . ^[5] Las matroides unimodulares o regulares son las matroides que se pueden representar en todos los campos; ^[6] se pueden caracterizar como las matroides que no tienen ninguno de${\displaystyle U{}_{4}^{2}}$, el plano Fano (un matroide binario con siete elementos), o el matroide dual del plano Fano como menores. ^{[5] [7]} Alternativamente, una matroide es regular si y solo si puede ser representada por una matriz totalmente unimodular . ^[8]

La conjetura de Rota establece que, para cada campo finito F , las matroides lineales F pueden caracterizarse por un conjunto finito de menores prohibidos, similar a las caracterizaciones descritas anteriormente para las matroides binarias y regulares. ^[9] A partir de 2012, se ha probado solo para campos de cuatro o menos elementos. ^{[5] [10] [11] [12]} Para campos infinitos (como el campo de los números reales ) no es posible tal caracterización. ^[13]

Campo de definición

Para cada campo numérico algebraico y cada campo finito F hay un matroide M para el cual F es el subcampo mínimo de su cierre algebraico sobre el cual M puede ser representado: M puede tomarse como de rango 3. ^[14]

Conjunto de características

El conjunto de características de una matroide lineal se define como el conjunto de características de los campos sobre los que es lineal. ^[15] Por cada número primo p existen infinitos matroides cuyo conjunto característico es el conjunto singleton { p }, ^[16] y por cada conjunto finito de números primos existe un matroide cuyo conjunto característico es el conjunto finito dado. ^[17]

Si el conjunto de características de un matroide es infinito, contiene cero; y si contiene cero, entonces contiene todos menos un número finito de primos. ^[18] Por tanto, los únicos conjuntos de características posibles son conjuntos finitos que no contienen cero y conjuntos cofinitos que contienen cero. ^[19] De hecho, todos estos conjuntos ocurren. ^[20]

Clases relacionadas de matroides

Una matroide uniforme ${\displaystyle U{}_{n}^{r}}$ posee ${\displaystyle n}$ elementos, y sus conjuntos independientes constan de todos los subconjuntos de hasta ${\displaystyle r}$de los elementos. Las matroides uniformes pueden estar representadas por conjuntos de vectores en posición general en un${\displaystyle r}$-espacio vectorial dimensional. El campo de representación debe ser lo suficientemente grande para que exista${\displaystyle n}$vectores en posición general en este espacio vectorial, matroides tan uniforme son F -linear para todos, pero un número finito de campos F . ^[21] Lo mismo es cierto para las matroides de partición , las sumas directas de las matroides uniformes, ya que la suma directa de dos matroides F- lineales cualesquiera es en sí misma F- lineal.

Una matroide gráfica es la matroide definida a partir de los bordes de un gráfico no dirigido al definir un conjunto de bordes para que sean independientes si y solo si no contiene un ciclo . Cada matroide gráfico es regular, y por lo tanto es F -linear para cada campo F . ^[8]

Las matroides de rigidez describen los grados de libertad de los enlaces mecánicos formados por barras rígidas conectadas en sus extremos por bisagras flexibles. Un vínculo de este tipo puede describirse como un gráfico, con un borde para cada barra y un vértice para cada bisagra, y para los vínculos unidimensionales, las matroides de rigidez son exactamente las matroides gráficas. Las matroides de rigidez de mayor dimensión pueden definirse utilizando matrices de números reales con una estructura similar a la de la matriz de incidencia del gráfico subyacente, y por lo tanto son${\displaystyle \mathbb {R} }$-lineal. ^{[22] [23]}

Como matroides uniformes y matroides de partición, los gammoides , matroides que representan la accesibilidad en gráficos dirigidos , son lineales sobre cada campo suficientemente grande. Más específicamente, un gammoide con${\displaystyle n}$ Los elementos pueden estar representados en cada campo que tenga al menos ${\displaystyle 2^{n}}$elementos. ^[24]

Las matroides algebraicas son matroides definidas a partir de conjuntos de elementos de una extensión de campo utilizando la noción de independencia algebraica . Toda matroide lineal es algebraica, y para campos de característica cero (como los números reales) coinciden las matroides lineales y algebraicas, pero para otros campos pueden existir matroides algebraicas que no son lineales. ^[25]

Referencias

1. Oxley, James G. (2006), Teoría de la matriz , Textos de posgrado de Oxford en matemáticas, 3 , Oxford University Press, p. 8, ISBN 9780199202508. Para la función de rango, consulte la p. 26.
2. Galés, DJA (2010), Teoría de Matroid , Publicaciones de Courier Dover, p. 10, ISBN 9780486474397.
3. Oxley (2006) , p. 12.
4. Oxley (2006) , págs. 170-172, 196.
5. Tutte, WT (1958), "Un teorema de homotopía para matroides. I, II", Transactions of the American Mathematical Society , 88 : 144-174, doi : 10.2307 / 1993244 , MR 0101526 .
6. White (1987) p.2
7. White (1987) p.12
8. Tutte, WT (1965), "Conferencias sobre matroides" , Revista de investigación de la Oficina Nacional de Normas , 69B : 1–47, doi : 10.6028 / jres.069b.001 , MR 0179781 .
9. Rota, Gian-Carlo (1971), "Teoría combinatoria, vieja y nueva", Actes du Congrès International des Mathématiciens (Niza, 1970), tomo 3 , París: Gauthier-Villars, págs. 229-233, MR 0505646 .
10. Bixby, Robert E. (1979), "Sobre la caracterización de Reid de las matroides ternarias", Journal of Combinatorial Theory , Serie B, 26 (2): 174-204, doi : 10.1016 / 0095-8956 (79) 90056-X , MR 0532587 .
11. Seymour, PD (1979), "Representación matroide sobre GF (3)", Journal of Combinatorial Theory , Serie B, 26 (2): 159-173, doi : 10.1016 / 0095-8956 (79) 90055-8 , MR 0532586 .
12. Geelen, JF ; Gerards, AMH; Kapoor, A. (2000), "Los menores excluidos de las matroides representables por GF (4)" (PDF) , Journal of Combinatorial Theory , Serie B, 79 (2): 247–299, doi : 10.1006 / jctb.2000.1963 , MR 1769191 , archivado desde el original (PDF) el 2010-09-24   .
13. Vámos, P. (1978), "El axioma faltante de la teoría matroide se pierde para siempre", Revista de la Sociedad Matemática de Londres , Segunda serie, 18 (3): 403–408, doi : 10.1112 / jlms / s2-18.3. 403 , MR 0518224 .
14. Blanco, Neil, ed. (1987), Geometrías combinatorias , Enciclopedia de las matemáticas y sus aplicaciones, 29 , Cambridge: Cambridge University Press , p. 18 , ISBN 0-521-33339-3, Zbl  0626.00007
15. Ingleton, AW (1971), "Representación de matroides", en galés, DJA (ed.), Matemáticas combinatorias y sus aplicaciones. Actas, Oxford, 1969 , Academic Press, págs. 149-167, ISBN 0-12-743350-3, Zbl  0222.05025
16. Oxley, James; Semple, Charles; Vertigan, Dirk; Whittle, Geoff (2002), "Infinite antichains of matroids with character set { p }", Discrete Mathematics , 242 (1-3): 175-185, doi : 10.1016 / S0012-365X (00) 00466-0 , hdl : 10092/13245 , MR 1874763 .
17. Kahn, Jeff (1982), "Conjuntos de características de matroides", Revista de la Sociedad Matemática de Londres , Segunda serie, 26 (2): 207-217, doi : 10.1112 / jlms / s2-26.2.207 , MR 0675165 , Zbl 0468.05020  .
18. Oxley (2006) , p. 225.
19. Oxley (2006) , p. 226.
20. Oxley (2006) , p. 228.
21. Oxley (2006) , p. 100.
22. Graver, Jack E. (1991), "Matroides de rigidez", SIAM Journal on Discrete Mathematics , 4 (3): 355-368, doi : 10.1137 / 0404032 , MR 1105942 .
23. Whiteley, Walter (1996), "Algunas matroides de geometría aplicada discreta", Teoría de Matroides (Seattle, WA, 1995) , Matemáticas contemporáneas, 197 , Providence, RI: American Mathematical Society, págs. 171–311, doi : 10.1090 / conm / 197/02540 , MR 1411692 .
24. Lindström, Bernt (1973), "Sobre las representaciones vectoriales de matroides inducidas", The Bulletin of the London Mathematical Society , 5 : 85–90, doi : 10.1112 / blms / 5.1.85 , MR 0335313 .
25. Ingleton, AW (1971), "Representación de matroides", Matemáticas combinatorias y sus aplicaciones (Proc. Conf., Oxford, 1969) , Londres: Academic Press, págs. 149-167, MR 0278974 .