[Math] Representability of matroids over $\mathbb R$

co.combinatoricslinear algebramatroid-theoryreference-request

Let $M$ be a matroid, for example viewed as being given by a finite set $X$ and a rank function $d : P(X) \to {\mathbb N}$ such that

1) $d(\varnothing)=0$, $d(\lbrace x \rbrace)=1$, for all $x \in X$,

2) $A \subset B$ implies $d(A) \leq d(B)$, and

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

A matroid is said to be representable over a field $k$, if there exists a collection of vectors $\lbrace \xi_x \in V \mid x \in X \rbrace$ of some $k$-vectorspace $V$, such that

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

It is well-known by results of Tutte, that representability of $M$ over $GF(2)$ and representability over all fields is characterized by certain finite lists of excluded minors that $M$ should not contain. At the same time Vámos has shown that there is no such finite list of excluded minors which characterizes representability over $\mathbb R$.

Question: What are sufficient conditions for representability of $M$ over $\mathbb R$?

By Tutte's result, $M$ is representable over any field if $M$ does not contain $U_{24}$, $F_7$ and $F^\ast_7$ as minors. Here, $U_{24}$ denotes the matroid of four points on a line, $F_7$ is the Fano plane and $F^\ast_7$ its dual. The question is whether there is a general result, that describes a larger class of matroids which are representable over $\mathbb R$.

Best Answer

This does not technically answer your question, but I think it may of interest to you, so bear with me. If you are interested in excluded-minor characterizations for real-representability, the situation is in fact much worse than what Vámos proved. In this paper, Mayhew, Newman, and Whittle prove the following theorem:

Theorem. For any real-representable matroid $N$, there exists an excluded-minor for real-representability that contains $N$ as a minor.

I'll remark that the same result holds over any other infinite field. Another way to view this theorem is as follows. Let $\mathcal{R}$ be the set of real-representable matroids and let $E(\mathcal{R})$ be the set of excluded minors for $ \mathcal{R}$. So, the theorem asserts that the downset of $E(\mathcal{R})$ contains all of $\mathcal{R}$! So, in some sense the set of excluded minors for $\mathcal{R}$ is as complicated as $\mathcal{R}$ itself. This is in striking constrast to the situation for finite fields, where Rota conjectured that the set of excluded minors is always finite.

Rota's Conjecture. For any finite field $\mathbb{F}$, the set of excluded minors for $\mathbb{F}$-representability is finite.

This conjecture has been proven for $\mathbb{F}_2, \mathbb{F}_3$, and $\mathbb{F}_4$, but is open for all other finite fields.


Addendum. I guess I'll take a stab at answering the actual question concerning sufficient conditions for real-representability. The quickest thing that I can think of is that all uniform matroids are real representable. To see this, let $U_{k,n}$ be a uniform matroid. By taking $n$ 'random' vectors in $\mathbb{R}^k$ we get a representation of $U_{k.n}$ over $\mathbb{R}$. This is a pretty rich class, and perhaps is sufficient for your purposes.

I'll also mention that the problem of testing real-representability is decidable. This follows from the Real Nullstellensatz.

Related Question