En la teoría matemática de las matroides , una matroide pavimentada es una matroide en la que cada circuito tiene un tamaño al menos tan grande como el rango de la matroide. En una matroide de rango cada circuito tiene un tamaño como máximo , por lo que equivale a definir matroides de pavimentación como las matroides en las que el tamaño de cada circuito pertenece al conjunto . [1] Se ha conjeturado que casi todas las matroides son matroides pavimentadas.
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/b/b7/Vamos_matroid.svg/220px-Vamos_matroid.svg.png)
Ejemplos de
Cada simple matroide de rango tres es una matroide pavimentada; por ejemplo, esto es cierto para el matroide Fano . El matroide de Vámos proporciona otro ejemplo, de rango cuatro.
Matroides uniformes de rango tienen la propiedad de que cada circuito tiene una longitud exacta y por eso son todos los matroides de pavimentación; [2] lo contrario no se sostiene, por ejemplo, el ciclo matroide del gráfico completo es pavimento pero no uniforme. [3]
Un sistema Steiner es un par dónde es un conjunto finito de tamaño y es una familia de -subconjuntos de elementos de con la propiedad de que cada -subconjunto de elementos de es también un subconjunto de exactamente un conjunto en . Los elementos de formar un -partición de y por lo tanto son los hiperplanos de una matroide pavimentada en . [4]
d -Particiones
Si una matroide pavimentada tiene rango , entonces sus hiperplanos forman un sistema conjunto conocido como-dividir. Una familia de dos o más conjuntos forma un -partición si cada conjunto en tiene tamaño al menos y cada -subconjunto de elementos de es un subconjunto de exactamente un conjunto en . Por el contrario, si es un -partición, entonces se puede utilizar para definir una matroid de pavimentación en para cual es el conjunto de hiperplanos. En este matroide, un subconjunto de es independiente siempre que o y no es un subconjunto de ningún conjunto en . [1]
Enumeración combinatoria
La enumeración combinatoria de las matroides simples en hasta nueve elementos ha demostrado que una gran fracción de ellas también son matroides pavimentadas. [1] Sobre esta base, se ha conjeturado que casi todas las matroides son matroides pavimentadas. [5] Más precisamente, de acuerdo con esta conjetura, el límite, cuando n llega al 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 las matroides de pavimentación dispersas , matroides que son a la vez pavimentadoras y duales a una matroide de pavimentación. Aunque esto permanece abierto, se ha probado una afirmación similar sobre la relación asintótica de los logaritmos del número de matroides y matroides de pavimentación dispersa. [6]
Historia
Los matroides de pavimentación fueron inicialmente estudiados por Hartmanis (1959) , en su formulación equivalente en términos de-particiones; Hartmanis las llamó celosías de partición generalizadas. En su libro Combinatorial Geometries de 1970 , Henry Crapo y Gian-Carlo Rota observaron que estas estructuras eran matroidales; Welsh (1976) introdujo el nombre "matroide de pavimentación" siguiendo una sugerencia de Rota. [7]
La estructura más simple de los matroides de pavimentación, en comparación con los matroides arbitrarios, ha permitido probar algunos hechos sobre ellos que siguen siendo esquivos 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 una matriz 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 las bases. Se ha demostrado que es cierto para pavimentar matroids, pero permanece abierto para la mayoría de los demás matroids. [8]
Notas
- ↑ a b c Galés (1976) .
- ^ Oxley 1992 , p. 26
- ^ Oxley 1992 , p. 27
- ^ Oxley 1992 , p. 367
- ^ Mayhew y col. (2011) .
- ^ Pendavingh y van der Pol (2015) .
- ^ Oxley 1992 , p. 75
- ^ Geelen y Humphries (2006) .
Referencias
- Geelen, Jim ; Humphries, Peter J. (2006), "Conjetura básica 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) en 2012-06-17 , recuperada 02/03/2013.
- Hartmanis, Juris (1959), "Teoría de celosía de particiones generalizadas", Canadian Journal of Mathematics , 11 : 97–106, doi : 10.4153 / CJM-1959-013-8 , MR 0099931 , Zbl 0089.37002.
- Mayhew, Dillon; Newman, Mike; Galés, 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 matroide , publicaciones científicas de Oxford, Oxford: Oxford University Press , ISBN 0-19-853563-5, Zbl 0784.05002
- Pendavingh, Rudi; van der Pol, Jorn (2015), "Sobre el número de matroides en comparación con el número de matroides de pavimentación dispersos", The Electronic Journal of Combinatorics , 22 (2), # 2.51.
- Galés, DJA (1976), "2.3. Paving Matroids", Teoría de Matroid , Publicaciones de Courier Dover, págs. 40-41, 44, ISBN 9780486474397. Reimpreso en 2010.