12
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Either I'm misreading or you left out something, but it sounds like you're saying that $\mathbb{R}$ is not a field. $\endgroup$ Dec 3 '10 at 15:26
  • 2
    $\begingroup$ @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 $\endgroup$ Dec 3 '10 at 15:32
  • 4
    $\begingroup$ @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. $\endgroup$
    – Tony Huynh
    Dec 3 '10 at 15:56
  • 2
    $\begingroup$ @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.). $\endgroup$ Dec 3 '10 at 16:07
  • $\begingroup$ @Tony: Oh, I see, it's one of those where do you place the quantifier things again! Thanks for the clarification. $\endgroup$ Dec 3 '10 at 16:27
11
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Dec 3 '10 at 16:52
  • 1
    $\begingroup$ 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). $\endgroup$ Dec 4 '10 at 13:03
  • $\begingroup$ I am not sure what the definition of managable is, but given a matroid $M$ of size $n$ and rank $r$, you can introduce $nr$ real variables and use the fact that the determinant is a polynomial. This defines a semi-algebraic set $S$ such that $M$ is real-representable if and only if $S$ is non-empty. $\endgroup$
    – Tony Huynh
    Sep 11 at 11:30
10
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks. What does Mnёv's Universality theorem say for matroids? $\endgroup$ Dec 4 '10 at 13:01
  • 1
    $\begingroup$ It implies that the realization space of a matroid can satisfy any given system of algebraic equations with integer coefficients. $\endgroup$
    – Igor Pak
    Dec 4 '10 at 16:09
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jan 5 '13 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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