Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
Either I'm misreading or you left out something, but it sounds like you're saying that $\mathbb{R}$ is not a field. –  Thierry Zell Dec 3 '10 at 15:26
1  
@Andreas: Are you familiar with Geelen's conjecture? That if $M$ is matroid representable over $\mathbb{R}$, then there is an excluded minor $M'$ for real-reprensentability such that $M$ is a minor of $M'$. It was established by Mayhew, Newman, & Whittle. temple.birs.ca/~09w5103/mayhew_09w5103_talk.pdf –  Joseph O'Rourke Dec 3 '10 at 15:32
4  
@Thierry: A matroid is called regular if it representable over every field. Andreas is saying that the set of excluded-minors for regular matroids is known and finite, while the set of excluded minors for just real-representability is infinite. –  Tony Huynh Dec 3 '10 at 15:56
1  
@Joseph: I knew about the result, but do not know what to do with it. It somehow shows that the class of excluded minors is huge. In my opinion, it seems to show that any answer to my question must either be of very limited generality or use quite different methods (i.e. for example not speak about minors at all.). –  Andreas Thom Dec 3 '10 at 16:07
    
@Tony: Oh, I see, it's one of those where do you place the quantifier things again! Thanks for the clarification. –  Thierry Zell Dec 3 '10 at 16:27
add comment

3 Answers 3

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.

share|improve this answer
    
Thanks. This is somehow saying that there cannot be any positive answers to my question using the language of minors etc. Is there any positive result using different terms? –  Andreas Thom Dec 3 '10 at 16:52
    
You said that real-presentability is decidable. Has this been used for anything so far? I mean, is there a managable $\mathbb R$-algebra $A(M)$ that one can construct out of a matroid $M$, so that $M$ is real-representable if and only if $-1$ is not a sum of squares in $A(M)$ (or something like this). –  Andreas Thom Dec 4 '10 at 13:03
add comment

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.

share|improve this answer
    
Thanks. What does Mnёv's Universality theorem say for matroids? –  Andreas Thom Dec 4 '10 at 13:01
1  
It implies that the realization space of a matroid can satisfy any given system of algebraic equations with integer coefficients. –  Igor Pak Dec 4 '10 at 16:09
add comment

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.

share|improve this answer
    
It follows from the before-mentioned Mayhew-Newman-Whittle theorem which is more precise: For any real representable matroid M there exists a forbidden minor for real representability that has M as a minor. –  Thomas Jan 5 '13 at 14:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.