Representación matroide

Vectores con patrón de independencia dado

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 determinada. Las representaciones matroides son análogas a las representaciones de grupos ; Ambos tipos de representación proporcionan estructuras algebraicas abstractas (matroides y grupos respectivamente) con descripciones concretas en términos de álgebra lineal .

Una matroide lineal es una matroide que tiene una representación, y una matroide lineal F ( para un campo F ) es una matroide que tiene una representación utilizando 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

Una matroide (finita) está definida por un conjunto finito (los elementos de la matroide) y una familia no vacía de subconjuntos de , llamados conjuntos independientes de la matroide. Se requiere satisfacer las propiedades de que cada subconjunto de un conjunto independiente es en sí mismo independiente, y que si un conjunto independiente es mayor que un segundo conjunto independiente, entonces existe un elemento al que se le puede agregar 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 vectores en un espacio vectorial : si es un conjunto finito o multiconjunto de vectores, y es la familia de subconjuntos linealmente independientes de , entonces es una matroide. ^{[1] [2]} ${\displaystyle (E,{\mathcal {I}})}$ ${\displaystyle E}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle E}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle x\in A\setminus B}$ ${\displaystyle B}$ ${\displaystyle E}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle E}$ ${\displaystyle (E,{\mathcal {I}})}$

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

Caracterización de matroides lineales.

La matroide Vámos , no lineal sobre ningún campo.

La configuración de Perles , lineal sobre los reales pero no sobre 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 no es representable en todos los campos. ^[4] Si una matroide es lineal, puede ser representable en algunos campos, pero no en todos. Por ejemplo, la matroide 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 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 nada de , el plano Fano (una matroide binaria con siete elementos), o la matroide dual del plano Fano como menores. ^{[5] [7]} Alternativamente, una matroide es regular si y sólo si puede representarse mediante una matriz totalmente unimodular . ^[8] ${\displaystyle U{}_{4}^{2}}$ ${\displaystyle U{}_{4}^{2}}$

La conjetura de Rota establece que, para cada campo finito F , las F -matroides lineales 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 ) tal caracterización no es posible. ^[13]

Campo de definición

Para cada campo de números algebraicos y cada campo finito F hay una matroide M para la cual F es el subcampo mínimo de su cierre algebraico sobre el cual M puede representarse: M puede considerarse 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 cuales es lineal. ^[15] Para cada número primo p existen infinitas matroides cuyo conjunto de características es el conjunto singleton { p }, ^[16] y para cada conjunto finito de números primos existe una matroide cuyo conjunto de características es el conjunto finito dado. ^[17]

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

Clases relacionadas de matroides

Una matroide uniforme tiene elementos y sus conjuntos independientes constan de todos los subconjuntos de hasta de los elementos. Las matroides uniformes pueden representarse mediante conjuntos de vectores en posición general en un espacio vectorial dimensional. El campo de representación debe ser lo suficientemente grande como para que existan vectores en posición general en este espacio vectorial, por lo que las matroides uniformes son F -lineales para todos los campos F , excepto para un número finito . ^[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. ${\displaystyle U{}_{n}^{r}}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle n}$

Una matroide gráfica es la matroide definida a partir de los bordes de un gráfico no dirigido definiendo un conjunto de bordes como independientes si y sólo si no contiene un ciclo . Cada matroide gráfica es regular y, por tanto, es F -lineal para cada campo F . ^[8]

Las matroides de rigidez describen los grados de libertad de 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 vínculos unidimensionales las matroides de rigidez son exactamente las matroides gráficas. Las matroides de rigidez de dimensiones superiores se pueden definir utilizando matrices de números reales con una estructura similar a la de la matriz de incidencia del gráfico subyacente y, por tanto, son lineales. ^{[22] [23]} ${\displaystyle \mathbb {R} }$

Al igual que las matroides uniformes y las matroides de partición, las gammaides , matroides que representan la accesibilidad en gráficos dirigidos , son lineales en cada campo suficientemente grande. Más específicamente, se puede representar un gammaide con elementos sobre cada campo que tenga al menos elementos. ^[24] ${\displaystyle n}$ ${\displaystyle 2^{n}}$

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) las matroides lineales y algebraicas coinciden, pero para otros campos pueden existir matroides algebraicas que no son lineales. ^[25]

Referencias

1. Oxley, James G. (2006), Teoría matroide , Textos de posgrado en matemáticas de Oxford, vol. 3, Oxford University Press, pág. 8, ISBN 9780199202508. Para la función de rango, consulte la p. 26.
2. Welsh, DJA (2010), Teoría matroide , Publicaciones Courier Dover, p. 10, ISBN 9780486474397.
3. Oxley (2006), pág. 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. Blanco (1987) p.2
7. Blanco (1987) p.12
8. Tutte, WT (1965), "Conferencias sobre matroides", Revista de investigación de la Oficina Nacional de Estándares , 69B : 1–47, doi : 10.6028/jres.069b.001 , MR  0179781.
9. Rota, Gian-Carlo (1971), "Teoría combinatoria, antigua 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 , SEÑOR  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 , SEÑOR  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 24 de septiembre de 2010.
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, señor  0518224.
14. Blanco, Neil, ed. (1987), Geometrías combinatorias, Enciclopedia de las matemáticas y sus aplicaciones, vol. 29, Cambridge: Cambridge University Press , pág. 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; Sencillo, Charles; Vértigan, Dirk; Whittle, Geoff (2002), "Anticadenas infinitas de matroides con conjunto de características { p }", Matemáticas discretas , 242 (1–3): 175–185, doi :10.1016/S0012-365X(00)00466-0, hdl : 10092/13245 , señor  1874763.
17. Kahn, Jeff (1982), "Conjuntos característicos 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ág. 225.
19. Oxley (2006), pág. 226.
20. Oxley (2006), pág. 228.
21. Oxley (2006), pág. 100.
22. Graver, Jack E. (1991), "Matroides de rigidez", Revista SIAM de Matemáticas Discretas , 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) , Contemporary Mathematics, vol. 197, Providence, RI: Sociedad Matemática Estadounidense, págs. 171–311, doi : 10.1090/conm/197/02540 , SEÑOR  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.