Over at the MatroidUnion, Irene has written a comprehensive series of posts on classes of matroids that arise from biased graphs, so head there for more details on how even cycle matroids fit into the grand scheme of things. In this post however, we’ll just think about even cycle matroids on their own. This is also the first post I’ve written in Markdown, rather than battling with the visual editor, and while it formats the code nicely, I can’t make it format the output nicely (without the line numbers etc).
It is often convenient to identify a binary matroid with the row space of any (and hence all) of its representing matrices. For example, we’ve already discussed graphic matroids which are the binary matroids that can be represented by the vertex-edge incidence matrix of a graph, and so we’ll just call a subspace graphic if it is the row space of such a matrix. An even cycle matroid is a binary matroid that can be represented by the vertex-edge incidence matrix of a graph with an extra row added or, equivalently, a binary vector space containing a graphic subspace of codimension one.
There is no fast algorithm known for checking if a binary matroid is an even cycle matroid and so we have to just check all of its subspaces of codimension one for being graphic. It is easy to see that all the subspaces of codimension one can be obtained from a matroid M by extending M by a binary element e not in M and then immediately contracting e and so we get the following function:
def is_evencycle(m):
if (m.rank() < 4):
return true
else:
return any([n.contract('X').is_graphic()
for n in m.linear_extensions('X')])
This uses the name ‘X’ to label the new element that is immediately contracted. If one of the elements of m is already called ‘X’, then the linear extensions method will fail. A more careful approach would be to first find a definitely new label.
Even-cycle matroids form a minor-closed class and so a very natural problem is the determination of the excluded minors for this class. We’ll certainly need to able to check that a matroid is an excluded minor – recall that this means that the matroid is not itself an even cycle matroid, but all of its single element deletions and contractions are even cycle matroids. We can easily modify the code that we used for graphic matroids to get:
def is_excludedminor_evencycle(m):
return (not is_evencycle(m)
and all([is_evencycle(m.contract(x)) for x in m.groundset()])
and all([is_evencycle(m.delete(x)) for x in m.groundset()]))
Let’s use this to find the excluded minors for even cycle matroids of rank at most 5 in the most naive fashion possible, in other words, simply applying the function to every one of the 1372 binary matroids of rank at most 5. Assume that an array called “rank5s” has been defined such that “rank5s[e]” contains all the e-element binary matroids of rank at most 5. (It is fairly easy to make such an array using Sage.)
exminors = []
for e in range(32):
for m in rank5s[e]:
if is_excludedminor_evencycle(m):
exminors.append(m)
What do we get at the end of this?
sage: len(exminors) 13 sage: [ [m.rank(),m.size()] for m in exminors] [[5, 12], [5, 12], [5, 13], [5, 13], [5, 13], [5, 13], [4, 14], [5, 14], [5, 14], [5, 14], [5, 14], [5, 15], [5, 15]]
There is a unique excluded minor of size 14 and rank 4, which can only be 
matroid obtained by deleting an arbitrary element from 
In fact, we’ll see in a later post in this series that things are even worse than it seems, but let’s return to the main point of this post, which is to demonstrate the relative ease of building on the functions provided in sage-matroids.
One fundamentally unsatisfying aspect of this code for excluded minors is that we’ve written two almost identical functions for the “excluded minor” functionality, but changing the occurrences of
m.is_graphic()
to
is_evencycle(m)
and if we continue to work with more properties, then we’ll need a separate function for
each and every property.
There is, however, a better way — we can create a function so that the property to
be tested is one of the parameters of the function.
def is_excluded_minor(p,m):
return (
not p(m)
and all([p(n) for n in [m.contract(e) for e in m.groundset()]])
and all([p(n) for n in [m.delete(e) for e in m.groundset()]]))
Now we can simply test whether a matroid is an excluded minor for the class of even cycle
matroids with
is_excluded_minor(is_evencycle, m)
and if we subsequently write a function for testing some other property, say whether the
matroid is an even cut matroid, then we can just insert the new property name into the
same function.
is_excluded_minor(is_evencut, m)
The only minor wrinkle is to remember to use the right name for the built-in functions.
is_excluded_minor(BinaryMatroid.is_graphic, m)
Next time, we’ll look a little more closely at the excluded minors for the even cycle matroids
and try to work out just how bad things might get!
i
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.
— the dual of the Fano matroid — is another one, as we can confirm.
.
, the graphic matroid 
has the edge set of 
, 
, 
, 
. Mostly the end-user doesn’t need to know about immutable sets or why the groundset is immutable, so this is just a bit of the implementation showing and can safely be ignored. Or just use the alternative version of the command
. Of course, listing the contents of an iterable object is such a common activity that you can just use
be a set of non-zero vectors in the vector space 
such that 
and, for reasons to be clarified later, no vector in 
with no coloops.
(a.k.a the Fano plane) — this means to take all the non-zero vectors in 
. This has 28 bases (7 choices for a first vector 
, 6 for a second vector 
and then 4 for the third vector which cannot be 
, then all divided by 6 because this counts each basis 
times). It has 7 circuits of size 3 (each being of the form 
, 
denote the numbers of bases and circuits of 
, for the ratio 
?
orientations for an 
-edge graph), and an orientation is called acyclic if the resulting directed graph contains no directed cycle and, at the opposite extreme, totally cyclic if every directed edge is contained in a directed cycle. A spanning tree is a connected subgraph containing every vertex of the graph, but containing no cycles; it is easy to see that a spanning tree of an 
-vertex graph has 
edges. We denote these three quantities 
for trees, 
for acyclic orientations and 
for totally cyclic orientations. Then we have the conjecture, due to serial conjecturer Dominic Welsh, and his former student Criel Merino.
is a multigraph with no bridges or loops, then 
.
edges, then 
.
edges, then 
.
(i.e. regardless of the structure of 
edges could possibly be the dividing point, so that any multigraph with at most 
edges has 
and any multigraph with at least 
is the Tutte polynomial of 
without any reference to the interpretations of these evaluations. So really, rather than crude approximations based on edge or element densities, it would be much more satisfying if there were some structural reason for the truth of the conjecture that exploited this duality – perhaps some way of defining a map from spanning trees to orientations that could be massaged into a suitable injective map.
and consider the behaviour of this single-variable polynomial for ![z \in [-1,1]](https://s0.wp.com/latex.php?latex=z+%5Cin+%5B-1%2C1%5D&bg=ffffff&fg=1a1a1a&s=0&c=20201002)
. In particular, it is quite possible that 
is convex throughout its domain, except for the case where 
is a matroid with no loops or co-loops with Tutte polynomial 
, then 
is convex on the range ![z \in [-1,1]](https://s0.wp.com/latex.php?latex=z+%5Cin+%5B-1%2C1%5D&bg=E7E6E2&fg=1a1a1a&s=0&c=20201002)
unless 
as a minor.
SymOmega 