Matroide uniforme

Matroide en el que cada permutación es una simetría

En matemáticas, un matroide uniforme es un matroide en el que los conjuntos independientes son exactamente los conjuntos que contienen como máximo r elementos, para algún entero fijo r . Una definición alternativa es que cada permutación de los elementos es una simetría .

Definición

El matroide uniforme se define sobre un conjunto de elementos. Un subconjunto de los elementos es independiente si y solo si contiene como máximo elementos. Un subconjunto es una base si tiene exactamente elementos, y es un circuito si tiene exactamente elementos. El rango de un subconjunto es y el rango del matroide es . ^{[1] [2]} ${\displaystyle U{}_{n}^{r}}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle r+1}$ ${\displaystyle S}$ ${\displaystyle \min(|S|,r)}$ ${\displaystyle r}$

Un matroide de rango es uniforme si y sólo si todos sus circuitos tienen exactamente elementos. ^[3] ${\displaystyle r}$ ${\displaystyle r+1}$

El matroide se llama línea de puntos . ${\displaystyle U{}_{n}^{2}}$ ${\displaystyle n}$

Dualidad y menores

El matroide dual del matroide uniforme es otro matroide uniforme . Un matroide uniforme es autodual si y solo si . ^[4] ${\displaystyle U{}_{n}^{r}}$ ${\displaystyle U{}_{n}^{n-r}}$ ${\displaystyle r=n/2}$

Todo menor de un matroide uniforme es uniforme. Restringir un matroide uniforme por un elemento (siempre que ) produce el matroide y contraerlo por un elemento (siempre que ) produce el matroide . ^[5] ${\displaystyle U{}_{n}^{r}}$ ${\displaystyle r<n}$ ${\displaystyle U{}_{n-1}^{r}}$ ${\displaystyle r>0}$ ${\displaystyle U{}_{n-1}^{r-1}}$

Realización

El matroide uniforme puede representarse como el matroide de subconjuntos afínmente independientes de puntos en posición general en un espacio euclidiano -dimensional , o como el matroide de subconjuntos linealmente independientes de vectores en posición general en un espacio vectorial real -dimensional . ${\displaystyle U{}_{n}^{r}}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle (r+1)}$

Todo matroide uniforme puede también ser realizado en espacios proyectivos y espacios vectoriales sobre todos los cuerpos finitos suficientemente grandes . ^[6] Sin embargo, el cuerpo debe ser lo suficientemente grande para incluir suficientes vectores independientes. Por ejemplo, la línea de -puntos puede ser realizada solamente sobre cuerpos finitos de o más elementos (porque de otra manera la línea proyectiva sobre ese cuerpo tendría menos de puntos): no es un matroide binario , no es un matroide ternario, etc. Por esta razón, los matroides uniformes juegan un papel importante en la conjetura de Rota concerniente a la caracterización menor prohibida de los matroides que pueden ser realizados sobre cuerpos finitos. ^[7] ${\displaystyle n}$ ${\displaystyle U{}_{n}^{2}}$ ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle U{}_{4}^{2}}$ ${\displaystyle U{}_{5}^{2}}$

Algoritmos

El problema de encontrar la base de peso mínimo de un matroide uniforme ponderado es un problema muy estudiado en informática como el problema de selección . Puede resolverse en tiempo lineal . ^[8]

Cualquier algoritmo que pruebe si un matroide dado es uniforme, dado acceso al matroide a través de un oráculo de independencia , debe realizar un número exponencial de consultas de oráculo y, por lo tanto, no puede tomar un tiempo polinomial. ^[9]

Matroides relacionados

A menos que , un matroide uniforme esté conectado: no es la suma directa de dos matroides más pequeños. ^[10] La suma directa de una familia de matroides uniformes (no necesariamente todas con los mismos parámetros) se denomina matroide de partición . ${\displaystyle r\in \{0,n\}}$ ${\displaystyle U{}_{n}^{r}}$

Todo matroide uniforme es un matroide de pavimento , ^[11] un matroide transversal ^[12] y un gammoide estricto . ^[6]

No todo matroide uniforme es gráfico , y los matroides uniformes proporcionan el ejemplo más pequeño de un matroide no gráfico, . El matroide uniforme es el matroide gráfico de un grafo dipolar de arista , y el matroide uniforme dual es el matroide gráfico de su grafo dual , el grafo de ciclo de arista . es el matroide gráfico de un grafo con bucles propios, y es el matroide gráfico de un bosque de aristas . Aparte de estos ejemplos, todo matroide uniforme con contiene como menor y por lo tanto no es gráfico. ^[13] ${\displaystyle U{}_{4}^{2}}$ ${\displaystyle U{}_{n}^{1}}$ ${\displaystyle n}$ ${\displaystyle U{}_{n}^{n-1}}$ ${\displaystyle n}$ ${\displaystyle U{}_{n}^{0}}$ ${\displaystyle n}$ ${\displaystyle U{}_{n}^{n}}$ ${\displaystyle n}$ ${\displaystyle U{}_{n}^{r}}$ ${\displaystyle 1<r<n-1}$ ${\displaystyle U{}_{4}^{2}}$

La línea de puntos proporciona un ejemplo de un matroide de Sylvester , un matroide en el que cada línea contiene tres o más puntos. ^[14] ${\displaystyle n}$

Véase también

• Conjunto K (geometría)

Referencias

1. Oxley, James G. (2006), "Ejemplo 1.2.7", Matroid Theory , Oxford Graduate Texts in Mathematics, vol. 3, Oxford University Press, pág. 19, ISBN 9780199202508Para la función de rango, véase la página 26.
2. Welsh, DJA (2010), Teoría matroide , Publicaciones Courier Dover, p. 10, ISBN 9780486474397.
3. Oxley (2006), pág. 27.
4. Oxley (2006), págs. 77 y 111.
5. Oxley (2006), págs. 106-107 y 111.
6. Oxley (2006), pág. 100.
7. Oxley (2006), págs. 202-206.
8. Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), "Capítulo 9: Medianas y estadísticas de orden", Introducción a los algoritmos (2.ª ed.), MIT Press y McGraw-Hill, págs. 183-196, ISBN 0-262-03293-7.
9. Jensen, Per M.; Korte, Bernhard (1982), "Complejidad de los algoritmos de propiedades de matroides", SIAM Journal on Computing , 11 (1): 184–190, doi :10.1137/0211014, MR  0646772.
10. Oxley (2006), pág. 126.
11. Oxley (2006, pág. 26).
12. Oxley (2006), págs. 48-49.
13. Welsh (2010), pág. 30.
14. Welsh (2010), pág. 297.