Representability of matroids over $\mathbb R$ - MathOverflow

Representability of matroids over $\mathbb R$

2010-12-03T15:12:04Z

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 by Tony Huynh for Representability of matroids over $\mathbb R$

2010-12-03T15:51:28Z

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 by Igor Pak for Representability of matroids over $\mathbb R$

2010-12-04T00:03:44Z

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 by Camilo Sarmiento for Representability of matroids over $\mathbb R$

2013-01-05T13:14:21Z

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.