Representability of matroids over $\mathbb R$

Question

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$.

Answer 1

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.

Answer 2

Your question is a bit like "what are the sufficient conditions for hamiltonicity?" The answer for the latter is: there are many interesting families for which this is established (say, hypercubes, graph squares, or various Cayley graphs of $S_n$), or rather strong general conditions (like min-degree >n/2, or 4-connected planar graphs), but this problem being NP-hard and all, one might want to have low expectations for a nice general criterion.

Now let me explain the connection. In view of Mnёv's Universality theorem, your question is a variation on "what are sufficient conditions that a given semialgebraic set has a real point?" There is a bit of a technicality when going from oriented to general matroids, so to simplify this, let us ignore the inequalities altogether. Then you want to know whether a given set of algebraic equations with integer coefficients has solutions over $\Bbb R$. That is already very hard.

Back to your question, there are some nice families of matroids which are known to be realizable over $\Bbb R$ (or any large enough field). Perhaps, the most popular family is transversal matroids which incidentally include the uniform matroids mentioned by Tony Huynh.

Answer 3

There is a negative answer in terms of excluded minors (this has been somehow hinted in the existing answers): "for any infinite field $\mathbb{F}$, there are infinitely many excluded minors for $\mathbb{F}$-representability."

This is mentioned at the end of section 3 of the survey What is a matroid? by James Oxley, and more precisely stated in theorem 5.9, where an infinite family of forbidden minors for representability over $\mathbb{Q}$, $\mathbb{R}$ or $\mathbb{C}$ is presented.