Matroide uniforme

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

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

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

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

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

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

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

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

El problema de encontrar la base de peso mínimo de un matroide uniforme ponderado se estudia ampliamente en informática como el problema de selección . Puede resolverse en tiempo lineal . ^{[ 9 ]}

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

El matroide libre sobre un conjunto base dado E es el matroide en el que los conjuntos independientes son todos subconjuntos de E. Es un caso especial de un matroide uniforme; específicamente, cuando E tiene cardinalidad${\displaystyle n}$, es el matroide uniforme${\displaystyle U{}_{n}^{n}}$. ^{[ 11 ]}

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

Todo matroide uniforme es un matroide pavimentador , ^{[ 13 ]} un matroide transversal ^{[ 14 ]} y un gammoid estricto . ^{[ 7 ]}

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

El${\displaystyle n}$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. ^{[ 15 ]}

• Conjunto K (geometría)
• matroide euleriano