Representabilidad de matroides sobre $\mathbb R$

Question

Sea $M$ sea un matroid, por ejemplo visto como dado por un conjunto finito $X$ y una función de rango $d : P(X) \to {\mathbb N}$ tal que

1) $d(\varnothing)=0$ , $d(\lbrace x \rbrace)=1$ para todos $x \in X$ ,

2) $A \subset B$ implica $d(A) \leq d(B)$ y

3) $d(A \cap B) + d(A \cup B) \leq d(A) + d(B)$ para todos $A,B \in P(X)$ .

Se dice que un matroid es representable sobre un campo $k$ si existe una colección de vectores $\lbrace \xi_x \in V \mid x \in X \rbrace$ de algunos $k$ -vectorspace $V$ tal que

$$d(A) = \dim {\rm span}_k \lbrace \xi_x \mid x \in A \rbrace \quad \forall A \in P(X).$$

Es bien sabido por los resultados de Tutte, que la representabilidad de $M$ en $GF(2)$ y la representabilidad sobre todos los campos se caracteriza por ciertas listas finitas de menores excluidos que $M$ no debe contener. Al mismo tiempo, Vámos ha demostrado que hay no tal lista finita de menores excluidos que caracteriza la representabilidad sobre $\mathbb R$ .

Pregunta: ¿Cuáles son las condiciones suficientes para la representabilidad de $M$ en $\mathbb R$ ?

Por el resultado de Tutte, $M$ es representable sobre cualquier campo si $M$ no contiene $U_{24}$ , $F_7$ y $F^\ast_7$ como menores. Toma, $U_{24}$ denota el matroid de cuatro puntos en una línea, $F_7$ es el plano de Fano y $F^\ast_7$ su doble. La cuestión es si existe un resultado general, que describa una clase mayor de matroides que sean representables sobre $\mathbb R$ .

Answer 1

Esto no responde técnicamente a su pregunta, pero creo que puede interesarle, así que téngame paciencia. Si te interesan las caracterizaciones de menor excluido para la representabilidad real, la situación es de hecho mucho peor de lo que demostró Vámos. En este papel Mayhew, Newman y Whittle demuestran el siguiente teorema:

Teorema. Para cualquier matroide real-representable $N$ existe un menor excluido para la representabilidad real que contiene $N$ como menor.

Observaré que el mismo resultado es válido para cualquier otro campo infinito. Otra forma de ver este teorema es la siguiente. Sea $\mathcal{R}$ sea el conjunto de matroides representables en la realidad y sea $E(\mathcal{R})$ sea el conjunto de menores excluidos para $\mathcal{R}$ . Por lo tanto, el teorema afirma que el conjunto de $E(\mathcal{R})$ contiene todo $\mathcal{R}$ ¡! Por lo tanto, en cierto sentido, el conjunto de menores excluidos para $\mathcal{R}$ es tan complicado como $\mathcal{R}$ mismo. Esto contrasta notablemente con la situación de los campos finitos, en los que Rota conjeturó que el conjunto de menores excluidos es siempre finito.

Conjetura de Rota. Para cualquier campo finito $\mathbb{F}$ el conjunto de menores excluidos para $\mathbb{F}$ -la representabilidad es finita.

Esta conjetura se ha demostrado para $\mathbb{F}_2, \mathbb{F}_3$ y $\mathbb{F}_4$ pero está abierto para todos los demás campos finitos.

---

Adenda. Supongo que intentaré responder a la pregunta sobre las condiciones suficientes para la representabilidad real. Lo más rápido que se me ocurre es que todos los matroides uniformes son representables reales. Para ver esto, dejemos que $U_{k,n}$ sea un matroid uniforme. Tomando $n$ vectores "aleatorios" en $\mathbb{R}^k$ obtenemos una representación de $U_{k.n}$ en $\mathbb{R}$ . Esta es una clase bastante rica, y tal vez sea suficiente para sus propósitos.

También mencionaré que el problema de probar la representabilidad real es decidible. Esto se deduce de la Real Nullstellensatz.

Answer 2

Tu pregunta es un poco como "¿cuáles son las condiciones suficientes para la hamiltonicidad?". La respuesta para esto último es: hay muchas familias interesantes para las que esto se establece (digamos, hipercubos, cuadrados de grafos, o varios grafos de Cayley de $S_n$ ), o condiciones generales bastante fuertes (como el grado mínimo >n/2 o grafos planos de 4 conexiones), pero dado que este problema es NP-difícil y todo eso, es posible que uno quiera tener pocas expectativas para un buen criterio general.

Ahora déjame explicarte la conexión. En vista de Teorema de universalidad de Mnёv tu pregunta es una variación de "¿cuáles son las condiciones suficientes para que un conjunto semialgebraico dado tenga un punto real?". Hay un poco de tecnicismo al pasar de matroides orientados a matroides generales, así que para simplificar, vamos a ignorar las desigualdades por completo. Entonces se quiere saber si un conjunto dado de ecuaciones algebraicas con coeficientes enteros tiene soluciones sobre $\Bbb R$ . Eso ya es muy duro.

Volviendo a tu pregunta, hay algunas buenas familias de matroides que se sabe que son realizables sobre $\Bbb R$ (o cualquier campo lo suficientemente grande). Quizás, la familia más popular sea matroides transversales que, por cierto, incluyen los matroides uniformes mencionados por Tony Huynh.

Answer 3

Hay una respuesta negativa en cuanto a los menores excluidos (esto se ha insinuado de alguna manera en las respuestas existentes): "para cualquier campo infinito $\mathbb{F}$ hay infinitos menores excluidos para $\mathbb{F}$ -representabilidad".

Esto se menciona al final de la sección 3 de la encuesta ¿Qué es un matroid? por James Oxley, y enunciado más precisamente en el teorema 5.9, donde una familia infinita de menores prohibidos para la representabilidad sobre $\mathbb{Q}$ , $\mathbb{R}$ o $\mathbb{C}$ se presenta.