En matemáticas, un matroide regular es un matroide que puede representarse sobre todos los campos .
Un 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 un matroide es seleccionar un conjunto finito de vectores en un espacio vectorial y definir un subconjunto de los vectores que sea independiente en el matroide cuando sea linealmente independiente en el espacio vectorial. Toda familia de conjuntos construida de esta manera es un matroide, pero no todos los matroides pueden construirse de esta manera, y los espacios vectoriales sobre diferentes cuerpos conducen a diferentes conjuntos de matroides que pueden construirse a partir de ellos.
Un matroide es regular cuando, para cada cuerpo , puede representarse mediante un sistema de vectores sobre . [1] [2]
Si un matroide es regular, también lo es su matroide dual , [1] y también lo es cada uno de sus menores . [3] Toda suma directa de matroides regulares sigue siendo regular. [4]
Todo matroide gráfico (y todo matroide cográfico) es regular. [5] A la inversa, todo matroide regular puede construirse combinando matroides gráficos, matroides cográficos y un determinado matroide de diez elementos que no es ni gráfico ni cográfico, utilizando una operación para combinar matroides que generaliza la operación de suma de camarillas en grafos. [6]
El número de bases en un matroide regular se puede calcular como el determinante de una matriz asociada, generalizando el teorema de matriz-árbol de Kirchhoff para matroides gráficos . [7]
El matroide uniforme (la línea de cuatro puntos) no es regular: no puede realizarse sobre el cuerpo finito de dos elementos GF(2) , por lo que no es un matroide binario , aunque puede realizarse sobre todos los demás cuerpos. El matroide del plano de Fano (un matroide de rango tres en el que siete de los triples de puntos son dependientes) y su dual tampoco son regulares: pueden realizarse sobre GF(2), y sobre todos los cuerpos de característica dos, pero no sobre ningún otro cuerpo que no sean esos. Como mostró Tutte (1958), estos tres ejemplos son fundamentales para la teoría de los matroides regulares: cada matroide no regular tiene al menos uno de estos tres como menor . Por lo tanto, los matroides regulares son exactamente los matroides que no tienen uno de los tres menores prohibidos , el plano de Fano o su dual. [8]
Si un matroide es regular, debe ser claramente realizable sobre los dos cuerpos GF(2) y GF(3). Lo inverso es cierto: todo matroide que sea realizable sobre ambos cuerpos es regular. El resultado se desprende de una caracterización menor prohibida de los matroides realizables sobre estos cuerpos, 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 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 las matroides regulares y las matrices unimodulares, y su caracterización por menores prohibidos, son resultados profundos de WT Tutte , demostrados originalmente por él utilizando el teorema de homotopía de Tutte . [8] Gerards (1989) publicó más tarde una prueba alternativa y más simple de la caracterización de matrices unimodulares por menores prohibidos. [11]
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]
