Representación matroide

Vectores con patrón dado de independencia

En la teoría matemática de matroides , una representación matroide es una familia de vectores cuya relación de independencia lineal es la misma que la de un matroide dado. 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 .

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

Definiciones

Un matroide (finito) se define por un conjunto finito (los elementos del matroide) y una familia no vacía de los subconjuntos de , llamados los conjuntos independientes del 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 que se puede agregar para formar un conjunto independiente mayor. 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 un 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 es linealmente independiente. Un matroide con una representación se denomina matroide lineal, y si es un espacio vectorial sobre un cuerpo F , entonces el matroide se denomina matroide F -lineal. Por lo tanto, los matroides lineales son exactamente los matroides que son isomorfos a los matroides definidos a partir de conjuntos o multiconjuntos de vectores. La función será biunívoca si y solo si el matroide subyacente es simple (no tiene conjuntos dependientes de dos elementos). Las representaciones de matroides también se pueden describir de manera más concreta utilizando matrices sobre un cuerpo F , con una columna por elemento de matroide y con un conjunto de elementos que son independientes en el matroide si y solo si el conjunto correspondiente de columnas de matriz es linealmente independiente. La función de rango de un matroide lineal está dada por el rango matricial de las submatrices de esta matriz, o equivalentemente por la dimensión del intervalo 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

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

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

No todos los matroides son lineales; el matroide Vámos de ocho elementos es uno de los matroides más pequeños que no se puede representar en todos los campos. ^[4] Si un matroide es lineal, puede ser representable en algunos campos, pero no en todos. Por ejemplo, el matroide de rango tres de nueve elementos definido por la configuración de Perles se puede representar en los números reales, pero no en los números racionales .

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

La conjetura de Rota establece que, para cada cuerpo finito F , las matroides F -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 demostrado solo para cuerpos de cuatro o menos elementos. ^{[5] [10] [11] [12]} Para cuerpos infinitos (como el cuerpo de los números reales ) no es posible tal caracterización. ^[13]

Campo de definición

Para cada cuerpo numérico algebraico y cada cuerpo finito F existe un matroide M para el cual F es el subcuerpo mínimo de su clausura algebraica sobre el cual M puede ser representado: M puede tomarse como de rango 3. ^[14]

Conjunto de características

El conjunto característico de un 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 infinitos matroides cuyo conjunto característico es el conjunto singleton { p }, ^[16] y para cada conjunto finito de números primos existe un matroide cuyo conjunto característico es el conjunto finito dado. ^[17]

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

Clases relacionadas de matroides

Un matroide uniforme tiene elementos, y sus conjuntos independientes consisten en todos los subconjuntos de hasta de los elementos. Los matroides uniformes pueden representarse por conjuntos de vectores en posición general en un espacio vectorial -dimensional. El campo de representación debe ser lo suficientemente grande para que existan vectores en posición general en este espacio vectorial, por lo que los matroides uniformes son F -lineales para todos los campos F excepto un número finito . ^[21] Lo mismo es cierto para los matroides de partición , las sumas directas de los 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}$

Un matroide gráfico es el matroide definido a partir de los bordes de un grafo no dirigido definiendo un conjunto de bordes como independientes si y solo si no contiene un ciclo . Todo matroide gráfico es regular y, por lo tanto, es F -lineal para cada cuerpo F. ^[8]

Las matroides de rigidez describen los grados de libertad de los vínculos mecánicos formados por barras rígidas conectadas en sus extremos por bisagras flexibles. Un vínculo de este tipo puede describirse como un grafo, con una arista 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 pueden definirse utilizando matrices de números reales con una estructura similar a la de la matriz de incidencia del grafo subyacente y, por lo tanto, son -lineales. ^{[22] [23]} ${\displaystyle \mathbb {R} }$

Al igual que los matroides uniformes y los matroides de partición, los gammoides , matroides que representan la alcanzabilidad en grafos dirigidos , son lineales sobre cada campo suficientemente grande. Más específicamente, un gammoide con elementos puede representarse sobre cada campo que tenga al menos elementos. ^[24] ${\displaystyle n}$ ${\displaystyle 2^{n}}$

Los matroides algebraicos son matroides definidos a partir de conjuntos de elementos de una extensión de cuerpo utilizando la noción de independencia algebraica . Todo matroide lineal es algebraico, y para cuerpos de característica cero (como los números reales) los matroides lineales y algebraicos coinciden, pero para otros cuerpos pueden existir matroides algebraicos que no sean lineales. ^[25]

Referencias

1. Oxley, James G. (2006), Teoría de matroides , Oxford Graduate Texts in Mathematics, vol. 3, Oxford University Press, pág. 8, ISBN 9780199202508Para la función de rango, véase la página 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ág. 2
7. Blanco (1987) pág. 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, 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 , MR  0532587.
11. Seymour, PD (1979), "Representación de matroides 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 para 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 ha perdido para siempre", Journal of the London Mathematical Society , Segunda serie, 18 (3): 403–408, doi :10.1112/jlms/s2-18.3.403, MR  0518224.
14. White, Neil, ed. (1987), Geometrías combinatorias, Enciclopedia de matemáticas y sus aplicaciones, vol. 29, Cambridge: Cambridge University Press , pág. 18, ISBN 0-521-33339-3, Zbl0626.00007 ​
15. Ingleton, AW (1971), "Representación de matroides", en galés, DJA (ed.), Combinatorial mathematics and its applications. Proceedings, Oxford, 1969 , Academic Press, pp. 149–167, ISBN 0-12-743350-3, Zbl0222.05025 ​
16. Oxley, James; Semple, Charles; Vertigan, Dirk; Whittle, Geoff (2002), "Anticadenas infinitas de matroides con conjunto característico { 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 característicos de matroides", Journal of the London Mathematical Society , 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", Matroid theory (Seattle, WA, 1995) , Contemporary Mathematics, vol. 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", Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) , Londres: Academic Press, págs. 149-167, MR  0278974.