Representability of matroids over $\mathbb R$ - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T09:04:43Z http://mathoverflow.net/feeds/question/48182 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/48182/representability-of-matroids-over-mathbb-r Representability of matroids over $\mathbb R$ Andreas Thom 2010-12-03T15:12:04Z 2013-01-05T13:14:21Z <p>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</p> <p>1) $d(\varnothing)=0$, $d(\lbrace x \rbrace)=1$, for all $x \in X$,</p> <p>2) $A \subset B$ implies $d(A) \leq d(B)$, and</p> <p>3) $d(A \cap B) + d(A \cup B) \leq d(A) + d(B)$ for all $A,B \in P(X)$.</p> <p>A matroid is said to be <em>representable</em> 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</p> <p>$$d(A) = \dim {\rm span}_k \lbrace \xi_x \mid x \in A \rbrace \quad \forall A \in P(X).$$</p> <p>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 <em>no</em> such finite list of excluded minors which characterizes representability over $\mathbb R$.</p> <blockquote> <p><strong>Question:</strong> What are sufficient conditions for representability of $M$ over $\mathbb R$?</p> </blockquote> <p>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$.</p> http://mathoverflow.net/questions/48182/representability-of-matroids-over-mathbb-r/48185#48185 Answer by Tony Huynh for Representability of matroids over $\mathbb R$ Tony Huynh 2010-12-03T15:51:28Z 2010-12-03T16:58:03Z <p>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 <a href="http://homepages.ecs.vuw.ac.nz/~mayhew/Publications/MNW09.pdf" rel="nofollow">paper</a>, Mayhew, Newman, and Whittle prove the following theorem:</p> <p><strong>Theorem.</strong> For <em>any</em> real-representable matroid $N$, there exists an excluded-minor for real-representability that contains $N$ as a minor. </p> <p>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.</p> <p><strong>Rota's Conjecture.</strong> For any finite field $\mathbb{F}$, the set of excluded minors for $\mathbb{F}$-representability is finite. </p> <p>This conjecture has been proven for $\mathbb{F}_2, \mathbb{F}_3$, and $\mathbb{F}_4$, but is open for all other finite fields. </p> <hr> <p><strong>Addendum.</strong> 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 <em>all</em> 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. </p> <p>I'll also mention that the problem of testing real-representability is decidable. This follows from the Real Nullstellensatz. </p> http://mathoverflow.net/questions/48182/representability-of-matroids-over-mathbb-r/48234#48234 Answer by Igor Pak for Representability of matroids over $\mathbb R$ Igor Pak 2010-12-04T00:03:44Z 2010-12-04T00:03:44Z <p>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 <em>>n/2</em>, 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. </p> <p>Now let me explain the connection. In view of <a href="http://bit.ly/hI8sqV" rel="nofollow">Mnёv's Universality theorem</a>, 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. </p> <p>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 <a href="http://en.wikipedia.org/wiki/Matroid#Transversal_matroids" rel="nofollow">transversal matroids</a> which incidentally include the uniform matroids mentioned by Tony Huynh. </p> http://mathoverflow.net/questions/48182/representability-of-matroids-over-mathbb-r/118122#118122 Answer by Camilo Sarmiento for Representability of matroids over $\mathbb R$ Camilo Sarmiento 2013-01-05T13:14:21Z 2013-01-05T13:14:21Z <p>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."</p> <p>This is mentioned at the end of section 3 of the survey <a href="https://www.math.lsu.edu/~oxley/survey4.pdf" rel="nofollow">What is a matroid?</a> 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. </p>