En matemáticas, una matroide ordenable por base es una matroide que tiene la siguiente propiedad adicional, relacionada con las bases de la matroide . [1]
Para dos bases cualesquiera y existe una biyección de intercambio factible , definida como una biyección de a , de modo que para cada , ambas cosas y son bases.
La propiedad fue presentada por Brualdi y Scrimger. [2] [3] Un matroide fuertemente ordenado por bases tiene la siguiente propiedad más fuerte:
Para dos bases cualesquiera y , existe una fuerte biyección de intercambio factible , definida como una biyección de a , de modo que para cada , ambas cosas y son bases.
La propiedad en contexto
La ordenabilidad básica impone dos requisitos a la función :
- Debería ser una biyección;
- Para cada , ambas cosas y deben ser bases.
Cada una de estas propiedades por sí sola es fácil de satisfacer:
- Todas las bases de un matroide dado tienen la misma cardinalidad, por lo que hay n ! biyecciones entre ellos (donde n es el tamaño común de las bases). Pero no se garantiza que una de estas biyecciones satisfaga la propiedad 2.
- Todas las bases y de una matroide satisfacen la propiedad de intercambio de base simétrica , que es, existe algo , tal que ambos y son bases. Sin embargo, no se garantiza que la función resultante f sea una biyección; es posible que varios están emparejados con el mismo .
Matroides que no se pueden ordenar por base
Algunos matroids no se pueden ordenar por base. Un ejemplo notable es el matroide gráfico en el gráfico K 4 , es decir, el matroide cuyas bases son los árboles de expansión de la camarilla en 4 vértices. [1] Denote los vértices de K 4 por 1, 2, 3, 4 y sus aristas por 12, 13, 14, 23 , 24, 34. Tenga en cuenta que las bases son:
- {12,13,14}, {12,13,24}, {12,13,34}; {12,14,23}, {12,14,34}; {12,23,24}, {12,23,34}; {12,24,34};
- {13,14,23}, {13,14,24}; {13,23,24}, {13,23,34}; {13,24,34};
- {14,23,24}, {14,23,34}; {14,24,34}.
Considere las dos bases A = {12,23,34} y B = {13,14,24}, y suponga que hay una función f que satisface la propiedad de intercambio (propiedad 2 anterior). Luego:
- f (12) debe ser igual a 14: no puede ser 24, ya que A \ {12} + {24} = {23,24,34} que no es una base; no puede ser 13, ya que B \ {13} + {12} = {12,14,24} que no es una base.
- f (34) debe ser igual a 14: no puede ser 24, ya que B \ {24} + {34} = {13,14,34} que no es una base; no puede ser 13, ya que A \ {34} + {13} = {12,13,23} que no es una base.
Entonces f no es una biyección - mapea dos elementos de A al mismo elemento de B .
Hay matroides que se pueden ordenar por base pero no muy por orden de base. [4] [1]
Matroides que se pueden ordenar por base
Cada matroid de partición se puede ordenar por base. Cada matroide transversal es fuertemente ordenable por base. [2]
Propiedades
En matroides ordenables por bases, existe una biyección de intercambio factible no solo entre bases sino también entre dos conjuntos independientes de la misma cardinalidad, es decir, dos conjuntos independientes cualesquiera y tal que .
Esto se puede demostrar por inducción sobre la diferencia entre el tamaño de los conjuntos y el tamaño de una base (recuerde que todas las bases de un matroide tienen el mismo tamaño). Si la diferencia es 0, entonces los conjuntos son en realidad bases, y la propiedad se deriva de la definición de matroides ordenables por base. De lo contrario, mediante la propiedad de aumento de un matroide, podemos aumentar a un conjunto independiente y aumentar a un conjunto independiente . Entonces, por el supuesto de inducción existe una biyección de intercambio factible Entre y . Si, entonces la restricción de a y es una biyección de intercambio factible. De lo contrario, y , entonces se puede modificar configurando: . Entonces, la restricción de la función modificada a y es una biyección de intercambio factible.
Lo completo
La clase de matroides de base ordenada está completa . Esto quiere decir que se cierra bajo las operaciones de menores, duales, sumas directas, truncamientos e inducción por grafos dirigidos. [1] : 2 También está cerrado bajo restricción, unión y truncamiento. [5] : 410
Lo mismo es cierto para la clase de matroides fuertemente ordenados por bases.
Referencias
- ↑ a b c d Bonin, Joseph E .; Savitsky, Thomas J. (1 de enero de 2016). "Una familia infinita de menores excluidos para una fuerte ordenabilidad de base" . Álgebra lineal y sus aplicaciones . 488 : 396–429. arXiv : 1507.05521 . doi : 10.1016 / j.laa.2015.09.055 . ISSN 0024-3795 . S2CID 119161534 . Lay resumen (PDF) .
- ^ a b Brualdi, Richard A .; Scrimger, Edward B. (1 de noviembre de 1968). "Sistemas de intercambio, emparejamientos y transversales" . Revista de teoría combinatoria . 5 (3): 244–257. doi : 10.1016 / S0021-9800 (68) 80071-7 . ISSN 0021-9800 .
- ^ Brualdi, Richard A. (1 de agosto de 1969). "Comentarios sobre bases en estructuras de dependencia" . Boletín de la Sociedad Matemática Australiana . 1 (2): 161-167. doi : 10.1017 / S000497270004140X . ISSN 1755-1633 .
- ^ AW Ingleton. "Matroides no ordenados por base". En Actas de la Quinta Conferencia Combinatoria Británica (Univ. Aberdeen, Aberdeen, 1975), páginas 355–359. Congressus Numerantium, No. XV, Utilitas Math., Winnipeg, Man., 1976.
- ^ Oxley, James G. (2006), Teoría Matroide , Textos de Posgrado en Matemáticas de Oxford , 3 , Oxford University Press, ISBN 9780199202508.