Matroide de pavimentación

Matroide sin cortocircuitos

El matroide Vámos , un matroide de pavimento de rango cuatro; los paralelogramos sombreados representan sus cinco circuitos de tamaño cuatro

En la teoría matemática de los matroides , un matroide de pavimentación es un matroide en el que cada circuito tiene un tamaño al menos tan grande como el rango del matroide. En un matroide de rango cada circuito tiene un tamaño como máximo , por lo que es equivalente a definir los matroides de pavimentación como los matroides en los que el tamaño de cada circuito pertenece al conjunto . ^[1] Se ha conjeturado que casi todos los matroides son matroides de pavimentación. ${\displaystyle r}$ ${\displaystyle r+1}$ ${\displaystyle \{r,r+1\}}$

Ejemplos

Todo matroide simple de rango tres es un matroide de pavimentación; por ejemplo, esto es cierto en el caso del matroide Fano . El matroide Vámos es otro ejemplo de rango cuatro.

Los matroides uniformes de rango tienen la propiedad de que cada circuito tiene una longitud exactamente igual a la de los demás y, por lo tanto, son todos matroides de pavimentación; ^[2] lo inverso no se cumple, por ejemplo, el matroide de ciclo del grafo completo es de pavimentación pero no uniforme. ^[3] ${\displaystyle r}$ ${\displaystyle r+1}$ ${\displaystyle K_{4}}$

Un sistema de Steiner es un par donde es un conjunto finito de tamaño y es una familia de subconjuntos de elementos de con la propiedad de que cada elemento distinto de está contenido en exactamente un conjunto en . Los elementos de forman una partición de y por lo tanto son los hiperplanos de un matroide de pavimento en . ^[4] ${\displaystyle S(t,k,v)}$ ${\displaystyle (S,{\mathcal {D}})}$ ${\displaystyle S}$ ${\displaystyle v}$ ${\displaystyle {\mathcal {D}}}$ ${\displaystyle k}$ ${\displaystyle S}$ ${\displaystyle t}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {D}}}$ ${\displaystyle {\mathcal {D}}}$ ${\displaystyle t}$ ${\displaystyle S}$ ${\displaystyle S}$

d-Particiones

Si un matroide de pavimentación tiene rango , entonces sus hiperplanos forman un sistema de conjuntos conocido como -partición. Una familia de dos o más conjuntos forma una -partición si cada conjunto en tiene un tamaño de al menos y cada subconjunto de -elementos de es un subconjunto de exactamente un conjunto en . Por el contrario, si es una -partición, entonces se puede utilizar para definir un matroide de pavimentación en para el cual es el conjunto de hiperplanos. En este matroide, un subconjunto de es independiente siempre que o y no sea un subconjunto de ningún conjunto en . ^[1] ${\displaystyle d+1}$ ${\displaystyle d}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle d}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle \bigcup {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle d}$ ${\displaystyle E=\bigcup {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle I}$ ${\displaystyle E}$ ${\displaystyle |I|\leq d}$ ${\displaystyle |I|=d+1}$ ${\displaystyle I}$ ${\displaystyle {\mathcal {F}}}$

Enumeración combinatoria

La enumeración combinatoria de los matroides simples en hasta nueve elementos ha demostrado que una gran fracción de ellos también son matroides de pavimentación. ^[1] Sobre esta base, se ha conjeturado que casi todos los matroides son matroides de pavimentación. ^[5] Más precisamente, de acuerdo con esta conjetura, el límite, cuando n tiende a infinito, de la relación entre el número de matroides de pavimentación y el número de todos los matroides debería ser igual a uno. Si es así, se puede hacer la misma afirmación para los matroides de pavimentación dispersos , matroides que son a la vez de pavimentación y duales a un matroide de pavimentación. Aunque esto permanece abierto, se ha demostrado una afirmación similar sobre la relación asintótica de los logaritmos de los números de matroides y matroides de pavimentación dispersos. ^[6]

Historia

Hartmanis (1959) estudió inicialmente las matroides de pavimentación en su formulación equivalente en términos de particiones; Hartmanis las denominó redes de particiones generalizadas. En su libro Combinatorial Geometries (Geometrías combinatorias) de 1970 , Henry Crapo y Gian-Carlo Rota observaron que estas estructuras eran matroidales; el nombre "matroides de pavimentación" fue introducido por Welsh (1976) siguiendo una sugerencia de Rota. ^[7] ${\displaystyle d}$

La estructura más simple de los matroides de pavimentación, en comparación con los matroides arbitrarios, ha permitido demostrar algunos hechos sobre ellos que siguen siendo difíciles de entender en el caso más general. Un ejemplo es la conjetura de la base de Rota , la afirmación de que un conjunto de n bases disjuntas en un matroide de rango n se puede organizar en una matriz n  ×  n de modo que las filas de la matriz sean las bases dadas y las columnas también sean bases. Se ha demostrado que es cierta para los matroides de pavimentación, pero sigue abierta para la mayoría de los demás matroides. ^[8]

Notas

1. galés (1976).
2. Oxley 1992, pág. 26
3. Oxley 1992, pág. 27
4. Oxley 1992, pág. 367
5. Mayhew y otros (2011).
6. Pendavingh y van der Pol (2015).
7. Oxley 1992, pág. 75
8. Geelen y Humphries (2006).

Referencias

• Geelen, Jim ; Humphries, Peter J. (2006), "Conjetura de la base de Rota para pavimentar matroides" (PDF) , SIAM Journal on Discrete Mathematics , 20 (4): 1042–1045 (electrónico), doi :10.1137/060655596, hdl : 10092/11877 , MR  2272246, archivado desde el original (PDF) el 2012-06-17 , consultado el 2013-02-03.
• Hartmanis, Juris (1959), "Teoría reticular de particiones generalizadas", Revista canadiense de matemáticas , 11 : 97–106, doi : 10.4153/CJM-1959-013-8 , MR  0099931, Zbl  0089.37002.
• Mayhew, Dillon; Newman, Mike; Welsh, Dominic; Whittle, Geoff (2011), "Sobre la proporción asintótica de matroides conectados", European Journal of Combinatorics , 32 (6): 882–890, doi : 10.1016/j.ejc.2011.01.016 , MR  2821559.
• Oxley, James G. (1992), Teoría de matroides , Oxford Science Publications, Oxford: Oxford University Press , ISBN 0-19-853563-5, Zbl0784.05002 ​
• Pendavingh, Rudi; van der Pol, Jorn (2015), "Sobre el número de matroides en comparación con el número de matroides de pavimento disperso", The Electronic Journal of Combinatorics , 22 (2), #2.51.
• Welsh, DJA (1976), "2.3. Pavimentación de matroides", Matroid Theory , Courier Dover Publications, págs. 40–41, 44, ISBN 9780486474397. Reimpreso en 2010.