After being busy for the last couple of months, it’s time to return to learning how to use a few more of the basic features of sage_matroids.
Last time we looked at graphic matroids which are the binary matroids that can be represented by the vertex-edge incidence matrix of a graph, and mentioned that sage_matroids has a very effective test for being graphic.
sage: f7 = matroids.named_matroids.Fano() sage: k5 = BinaryMatroid(graphs.CompleteGraph(5).incidence_matrix()) sage: f7.is_graphic() False sage: k5.is_graphic() True
So the Fano plane is not graphic, while the cycle matroid of is graphic. Now if a matroid is graphic then all of its minors are graphic, where a minor is any matroid obtained by repeatedly contracting and deleting elements. For example, let’s just confirm this by checking all the contractions of . We’ll do it in two steps first.
sage: k5cons = [k5.contract(x) for x in k5.groundset()] sage: [n.is_graphic() for n in k5cons] [True, True, True, True, True, True, True, True, True, True]
We can shortcircuit this to avoid making the intermediate list of minors explicitly.
sage: [k5.contract(x).is_graphic() for x in k5.groundset()] [True, True, True, True, True, True, True, True, True, True]
If we just want to check that all the values are True without listing them all, we can use the handy Python construct all which is True if all of the elements of an iterable are True.
sage: all([k5.contract(x).is_graphic() for x in k5.groundset()]) True
Now, what about the Fano plane?
sage: all([f7.contract(x).is_graphic() for x in f7.groundset()]) True sage: all([f7.delete(x).is_graphic() for x in f7.groundset()]) True
So also has this property, so although it is not graphic itself, all of its minors are graphic, and so it is a minor minimal non-graphic matroid or, in other words, an excluded minor for the class of graphic matroids.
One of the fundamental observations of matroid theory is that any minor-closed class of matroids can be characterised by listing its excluded minors, and there is a vast literature that either (1) takes a natural property defining a minor-closed class of matroids and finds the excluded minors, or (2) takes a list of matroids and investigates the properties enjoyed (endured?) by the class of matroids without minors in the initial list.
So, let’s write a function to detect when a binary matroid is an excluded minor for the class of graphic matroids. This is true when the matroid passed in as the argument to the function is not graphic itself, but all of its single element deletions and contractions are graphic.
sage: def is_excludedminor_graphic(m): return (not m.is_graphic() and all([m.contract(x).is_graphic() for x in m.groundset()]) and all([m.delete(x).is_graphic() for x in m.groundset()]))
This code defines a function that can now be called by name for the rest of the Sage session; if it proves useful, then the code can be saved in a file and “imported” at the beginning of a future Sage session.
sage: is_excludedminor_graphic(f7) True
So what are some other excluded minors for graphic matroids? It turns out that — the dual of the Fano matroid — is another one, as we can confirm.
sage: is_excludedminor_graphic(f7.dual()) True
Of course, the full list of excluded minors for graphic matroids is known, and consists of , and the duals of the graphic matroids and . Let’s just check the first of these.
sage: is_excludedminor_graphic(k5.dual()) True
It is a famous result of Robertson and Seymour that every minor-closed family of graphs has a finite list of excluded minors and Geelen, Gerards and Whittle have shown that the same is true for binary matroids. Of course, finite doesn’t mean short or easy-to-find and there are lots of minor-closed classes for which the list of excluded minors is not known at all, or for which the list of known excluded minors is vast and still growing.
Next time we’ll talk more about excluded minors for some classes of binary matroids.