En matemáticas, una matroide regular es una matroide que se puede representar en todos los campos .
Definición
Una matroide se define como una familia de subconjuntos de un conjunto finito, que satisface ciertos axiomas. Los conjuntos de la familia se denominan "conjuntos independientes". Una de las formas de construir una matroide es seleccionar un conjunto finito de vectores en un espacio vectorial y definir un subconjunto de los vectores para que sean independientes en la matroide cuando es linealmente independiente en el espacio vectorial. Cada familia de conjuntos construidos de esta manera es una matroide, pero no todas las matroides pueden construirse de esta manera, y los espacios vectoriales sobre diferentes campos conducen a diferentes conjuntos de matroides que pueden construirse a partir de ellos.
Una matroide es regular cuando, para cada campo , puede ser representado por un sistema de vectores sobre . [1] [2]
Propiedades
Si un matroide es regular, también lo es su matroide dual , [1] y también lo es cada uno de sus menores . [3] Cada suma directa de matroides regulares permanece regular. [4]
Cada matroide gráfico (y cada matroide co-gráfico) es regular. [5] A la inversa, cada matroide regular puede construirse combinando matroides gráficas, matroides co-gráficas y una determinada matroide de diez elementos que no es ni gráfica ni co-gráfica, usando una operación para combinar matroides que generaliza la operación clique-sum. en gráficos. [6]
El número de bases en una matroide regular puede calcularse como el determinante de una matriz asociada, generalizando el teorema del árbol de matrices de Kirchhoff para las matroides gráficas . [7]
Caracterizaciones
La matroide uniforme (la línea de cuatro puntos) no es regular: no se puede realizar sobre el campo finito de dos elementos GF (2) , por lo que no es una matroide binaria , aunque puede realizarse sobre todos los demás campos. La matroide del plano de Fano (una matroide de rango tres en la que siete de los triples de puntos son dependientes) y su dual tampoco son regulares: pueden realizarse sobre GF (2), y sobre todos los campos de la característica dos, pero no sobre otros campos que esos. Como mostró Tutte (1958) , estos tres ejemplos son fundamentales para la teoría de las matroides regulares: cada matroide no regular tiene al menos uno de estos tres como menor . Así, los matroids regulares son exactamente los matroids que no tienen uno de los tres menores prohibidos., el avión Fano, o su dual. [8]
Si una matroide es regular, claramente debe ser realizable sobre los dos campos GF (2) y GF (3). Lo contrario es cierto: cada matroide que se puede realizar en estos dos campos es regular. El resultado se deriva de una caracterización menor prohibida de las matroides realizables sobre estos campos, parte de una familia de resultados codificados por la conjetura de Rota . [9]
Las matroides regulares son las matroides que se pueden definir a partir de una matriz totalmente unimodular , una matriz en la que cada submatriz cuadrada tiene un determinante 0, 1 o -1. Los vectores que realizan la matroide pueden tomarse como las filas de la matriz. Por esta razón, las matroides regulares a veces también se denominan matroides unimodulares . [10] La equivalencia de matrices regulares y unimodulares, y su caracterización por menores prohibidos, son resultados profundos de WT Tutte , originalmente probado por él usando el teorema de homotopía de Tutte . [8] Gerards (1989) publicó posteriormente una prueba alternativa y más simple de la caracterización de matrices unimodulares por menores prohibidos. [11]
Algoritmos
Existe un algoritmo de tiempo polinomial para probar si un matroide es regular, dado acceso al matroide a través de un oráculo de independencia . [12]
Referencias
- ↑ a b Fujishige, Satoru (2005), Optimización y funciones submodulares , Annals of Discrete Mathematics, Elsevier, p. 24, ISBN 9780444520869.
- ^ Oxley, James G. (2006), Teoría Matroide , Textos de Posgrado en Matemáticas de Oxford , 3 , Oxford University Press, p. 209, ISBN 9780199202508.
- ^ Oxley (2006) , p. 112.
- ^ Oxley (2006) , p. 131.
- ^ Tutte, WT (1965), "Lectures on matroids" , Journal of Research of the National Bureau of Standards , 69B : 1–47, doi : 10.6028 / jres.069b.001 , MR 0179781.
- ^ Seymour, PD (1980), "Decomposition of regular matroids", Journal of Combinatorial Theory , Serie B, 28 (3): 305–359, doi : 10.1016 / 0095-8956 (80) 90075-1 , hdl : 10338.dmlcz / 101946 , MR 0579077.
- ^ Maurer, Stephen B. (1976), "Generalizaciones matriciales de algunos teoremas sobre árboles, ciclos y ciclos en gráficos", SIAM Journal on Applied Mathematics , 30 (1): 143-148, doi : 10.1137 / 0130017 , MR 0392635.
- ^ a b Tutte, WT (1958), "Un teorema de homotopía para matroides. I, II", Transactions of the American Mathematical Society , 88 (1): 144-174, doi : 10.2307 / 1993244 , JSTOR 1993244 , MR 0101526.
- ^ 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 , MR 0532586.
- ^ Oxley (2006) , p. 20.
- ^ Gerards, AMH (1989), "Una prueba corta de la caracterización de Tutte de matrices totalmente unimodulares", Álgebra lineal y sus aplicaciones , 114/115: 207-212, doi : 10.1016 / 0024-3795 (89) 90461-8.
- ^ Truemper, K. (1982), "Sobre la eficiencia de las pruebas de representabilidad para matroides", European Journal of Combinatorics , 3 (3): 275-291, doi : 10.1016 / s0195-6698 (82) 80039-5 , MR 0679212.