This post is about some conjectures\u00a0on matroid minor structure theory in the most general setting possible: excluding a uniform matroid.\u00a0Jim Geelen previously discussed questions in this area in [1], and most of what I write here comes from discussions with him.<\/p>\n
Whether they be for graphs or matroids, qualitative structure theorems for minor-closed classes usually fit a particular template. They make a statement that the members of a minor-closed class are ‘close’ to having a particular basic structure, where the structure should be something that differs the graphs\/matroids in the class from arbitrary\/random ones. In the case of proper minor-closed classes of graphs, this structure takes the form of embeddability on a fixed topological surface, as was famously shown by Robertson and Seymour. For matroids representable over a fixed finite field, the structure arises\u00a0from classes of group-labelled graphs that embed on a fixed topological surface, classes of group-labelled graphs in general, and (when the order of the field is non-prime) classes of matroids representable over a fixed subfield.\u00a0These results for finite fields have been shown in recent years\u00a0by Geelen, Gerards and Whittle, and have already given us powerful tools for understanding the matroids in minor-closed classes, as demonstrated most notably in their proof of Rota’s conjecture.<\/p>\n
Extending graph minors structure theory to minor-closed classes of matroids over finite fields was no mean feat, but there is real reason to believe that we can generalise it further. \u00a0It seems unlikely that one could obtain very strong structural results for all<\/em> minor-closed classes; for example, the class of sparse paving matroids<\/em> (that is, the matroids whose girth is at least\u00a0the rank and whose cogirth at least the corank) is minor-closed, and is conjectured to contain almost all matroids – intuitively, a structure theorem that allows us to ‘understand’ the class of sparse paving matroids seems unlikely. The sticking point here seems to be that this class contains all uniform matroids. At the moment, we think that one should be able to obtain sensible qualititative structure theorems precisely for the minor-closed classes that don’t contain all the uniform matroids. In this post, I’ll state a\u00a0conjectures\u00a0that makes this kind of statement. For this, we need two ingredients.<\/p>\n Basic\u00a0Structures<\/strong><\/p>\n We first need\u00a0an idea which basic structures we expect to see as outcomes. These turn out to be pretty close to what goes on in the finite field representable case. Let $\\mathcal{M}$ be a minor-closed class not containing all uniform matroids. Let $U$ be a uniform matroid not contained\u00a0in $\\mathcal{M}$. Without loss of generality, we may assume that $U = U_{s,2s}$ where $s \\ge 4$, as every uniform matroid is a minor of a matroid of this form.\u00a0Here are some examples of interesting classes that \u00a0$\\mathcal{M}$ could be:<\/p>\n Although they are not at all trivial\u00a0from a graph-theoretic perspective, classes of the last type are less rich as they all have small vertical separations. Classes of the the other types, however, contain matroids of arbitrarily high vertical connectivity. Structural statements simplify a lot when they are made about highly connected matroids, and the main conjecture I’ll be stating will apply only to very highly vertically connected matroids in a given minor-closed class;\u00a0the last type of class will therefore not show up.<\/p>\n The divide between the ‘highly connected’ minor-closed classes and other\u00a0classes is made concrete by the following conjecture.<\/p>\n Conjecture 1.\u00a0<\/strong>Let $\\mathcal{M}$ be a minor-closed class of matroids not containing all uniform matroids. Either<\/p>\n Closeness\u00a0<\/b><\/p>\n We now need to say what, according to our structural conjecture, exactly is meant by two matroids being ‘close’. For minor-closed classes of graphs, ‘closeness’ is measured in terms of vortices, apex vertices, and clique-sums. For matroids over finite fields, the structure theory considers\u00a0two matroids on the same ground set to be ‘close’ if they have representations that differ by a bounded-rank matrix. None of these ideas quite work for matroids in general, as we don’t have representations, let alone vertices. However, there is something that will.<\/p>\n A\u00a0single-element\u00a0<\/em>projection\u00a0<\/em>of a matroid $M$ is a matroid $N$ for which there exists a matroid $L$ such that $L \\backslash e = M$ and $L \/ e = N$. If $N$ is a single-element projection of $M$ then $N$ is a\u00a0single-element lift\u00a0<\/em>of $M$. Single-element lifts and projections are dual notions that ‘perturb’ a matroid by a small amount to another matroid on the same ground set; for example, they change the rank and corank of any given set by at most $1$. We write $\\mathrm{dist}(M,N)$ to denote the minimum number of single-element lifts and\/or projections to transform $M$ into $N$. If this ‘distance’ is small, then $M$ and $N$ are ‘close’.\u00a0This will serve as the\u00a0notion of closeness in our structure conjecture. (In a more general structure theory, vortices will also arise). This distance only makes sense if $M$ and $N$ have the same ground set, if this is not the case, then we say\u00a0$\\mathrm{dist}(M,N) = \\infty$.<\/p>\n Incidentally (and I’m looking at you, grad students), I would like an answer to the following question, which would simplify the notion of perturbation distance\u00a0–\u00a0I don’t have a good intuition for whether it should be true or false, and either way it could be easy.<\/p>\n Problem.\u00a0<\/strong>Let $M$ and $N$ be matroids for which there exists a matroid $L$ that is a single-element lift of both $M$ and $N$. Does there exist a matroid $P$ that is a single-element projection of both $M$ and $N$?<\/p>\n The Conjecture<\/strong><\/p>\n Here goes! If $\\mathcal{M}$ is a minor-closed class not containing all uniform matroids, then the highly connected members of $\\mathcal{M}$ should be close to being frame, co-frame, or representable.<\/p>\n Conjecture 2:\u00a0<\/strong>Let $\\mathcal{M}$ be a minor-closed class of matroids not containing a uniform matroid $U$. There is an integer $t \\ge 0$ so that, if $M$ is a vertically $t$-connected matroid in $\\mathcal{M}$, then there is a matroid $N$ such that $\\mathrm{dist}(M,N) \\le t$ and either<\/p>\n If true, this conjecture would tell us that minor-closed classes of matroids inhabit a very beautiful universe. The hypotheses are very minimal, applying to a massive variety of different $\\mathcal{M}$.\u00a0The conclusions, on the other hand, imply that all ‘nondegenerate’\u00a0members of $\\mathcal{M}$ are at a small distance from a matroid $N$ that is\u00a0very\u00a0<\/em>far from being generic. Somehow, as happens again and again in matroid theory, the ‘special’ classes of representable and graph-like matroids are in fact fundamental to understanding the minor order.<\/p>\n Conjecture 2 is one of the many goals of a more general matroid structure theory; in my next post I will discuss some recent progress we have made towards it.<\/p>\n Reference<\/strong><\/p>\n [1] Some open problems on excluding a uniform matroid<\/em>, J. Geelen, Adv. Appl. Math. 41 (2008), 628-637.<\/p>\n","protected":false},"excerpt":{"rendered":" This post is about some conjectures\u00a0on matroid minor structure theory in the most general setting possible: excluding a uniform matroid.\u00a0Jim Geelen previously discussed questions in this area in [1], and most of what I write here comes from discussions with … Continue reading \n
\n
\n