## Getting started with sage_matroids IV

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 $PG(3,2)^{-}$, the
matroid obtained by deleting an arbitrary element from $PG(3,2)$, but the 12 additional excluded minors of rank 5 do not bode well for an excluded minor characterisation of even cycle matroids.

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!

## Getting started with sage_matroids: III

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 $K_5$ 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 $K_5$. 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 $F_7$ 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 $F_7^*$ — 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 $F_7$, $F_7^*$ and the duals of the graphic matroids $M(K_5)$ and $M(K_{3,3})$. 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.

## Congratulations!

The Minister for Education (finally) announced the ARC Future Fellowships commencing in 2013 this morning, and simultaneously, the DECRA’s and Discovery Projects. Our research group missed out on a grant of the first and second kind, but we had success with two Discovery Projects:

1. Cheryl Praeger, Stephen Glasby, and Alice Niemeyer (“Finite linearly representable geometries & symmetries).
2. Gordon (“Real chromatic roots of graphs & matroids”)

I remember last summer when both grant applications were being written, and it was a lot of work for all involved, so it’s great to see that both have awarded to support cutting edge research.

## Getting started with sage_matroids: II

Following on from my previous post on getting started with sage_matroids, let’s look at a few more of the built-in features.

One of the most fundamental classes of matroids is the class of graphic matroids. Given a graph $G$, the graphic matroid $M(G)$ has the edge set of $G$ as its elements, and the forests of $G$ as its independent sets. The circuits of $M(G)$, i.e. the minimal dependent sets, are then precisely the cycles of $G$, so sometimes $M(G)$ is called the cycle matroid of $G$.

The decision to go with Sage, rather than to either develop a stand-alone system or build on an existing stand-alone system, was largely driven by the fact that Sage provides both a standard programming language and a vast amount of inbuilt combinatorial functionality already. In particular, we can just piggyback on the very extensive “graphs” package to immediately create a graphic matroid using, of course, the canonical graph theory example.

sage: pm = Matroid(graphs.PetersenGraph())
sage: pm
Regular matroid of rank 9 on 15 elements with 2000 bases

## Getting started with sage_matroids: I

Sage 5.12 has just been released, and this is the first release that automatically incorporates the sage_matroids package that was primarily written by Rudi Pendavingh and Stefan van Zwam. Over at The Matroid Union, Stefan has written an introductory post along with some examples of using the package, and I’m going to complement this with some additional examples. Unlike Stefan though, I’m not an expert in Python, so this post is really to show how easy it is to just get started, even if you don’t know all that much about Python.

I’ll assume that you’ve installed Sage 5.12 and you either have a notebook (the browser interface) or command line working; on the command line Sage prompts you for input with the “sage: ” or “…” when multiline input is incomplete.

I’m mostly interested in binary matroids, which are basically just sets of binary vectors; traditionally a binary matroid is represented by the columns of a binary matrix. Let’s start with an easy binary matroid, namely the Fano plane which is, of course, the “standard” starting example in matroid theory. We can build it in two steps by typing in the representing matrix row-by-row and then creating the matroid.

sage: mat = Matrix([[0,0,0,1,1,1,1],[0,1,1,0,0,1,1],[1,0,1,0,1,0,1]])
sage: bm
Binary matroid of rank 3 on 7 elements, type (3, 0)

Notice that I have to use the “full name” of the constructor for a binary matroid, but if I get tired of typing the whole thing, then I can just tell Sage once-and-for-all where to find it and then just use the “short name”.

sage: from sage.matroids.advanced import BinaryMatroid
sage: bm = BinaryMatroid(mat)

Either way, the  variable “bm” now reports that it represents a binary matroid of rank 3 with 7 elements and gives some additional information that it is of “type (3,0)” (of which more later).

Now I can ask Sage lots of things about this matroid, such as confirming that I entered the matrix correctly, by asking for the representing matrix: notice that the syntax is the common object-oriented style whereby the object “bm” is asked to run the method “representation” and the value returned by the method is then displayed (or assigned to a variable etc.)

sage: bm.representation()
[0 0 0 1 1 1 1]
[0 1 1 0 0 1 1]
[1 0 1 0 1 0 1]

So the elements of this matroid — the groundset — is the set of columns of the matrix. To refer to a particular subset of the columns, I’ll need to know the “names” of the elements.

sage: bm.groundset()
frozenset([0, 1, 2, 3, 4, 5, 6])

This tells me that the groundset is an immutable set (the “frozen” part) containing the elements $0$, $1$, $\ldots$, $6$. 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

sage: bm.groundset_list()
[0, 1, 2, 3, 4, 5, 6]

Now I know the groundset, I can find out all the usual “matroidy things” about the matroid, such as the rank of an arbitrary subset of the groundset.

sage: bm.rank([0,2,4])
3
sage: bm.rank([0,1,2])
2

The bases of the matroid are all the independent subsets of columns, and I can find out how many of these there are, and also which they are.

sage: bm.bases_count()
28
sage: bm.bases()
Iterator over a system of subsets

Ah, the first one is clear – there are 28 bases, but the second one didn’t give me what I expected, which was the list of bases, but rather an iterator. An iterator is a container object that supplies the objects it contains “one-by-one” (the container object can thereby represent a huge collection by not actually storing any of the objects but only producing them when called for). In this case though, we just want to see them all and so we use Python’s standard syntax for working with iterables.

sage: [b for b in bm.bases()]
[frozenset([0, 2, 3]),
frozenset([1, 2, 3]),
frozenset([0, 1, 3]),
frozenset([1, 3, 4]),
frozenset([2, 3, 4]),
frozenset([0, 2, 4]),
frozenset([1, 2, 4]),
frozenset([0, 1, 4]),
frozenset([0, 4, 5]),
frozenset([1, 4, 5]),
frozenset([3, 4, 5]),
frozenset([0, 3, 5]),
frozenset([2, 3, 5]),
frozenset([0, 2, 5]),
frozenset([1, 2, 5]),
frozenset([0, 1, 5]),
frozenset([1, 5, 6]),
frozenset([2, 5, 6]),
frozenset([3, 5, 6]),
frozenset([4, 5, 6]),
frozenset([0, 4, 6]),
frozenset([2, 4, 6]),
frozenset([3, 4, 6]),
frozenset([0, 3, 6]),
frozenset([1, 3, 6]),
frozenset([0, 2, 6]),
frozenset([1, 2, 6]),
frozenset([0, 1, 6])]
sage:

The notation is simple for mathematicians because it is so similar to set notation – the command can be essentially translated directly into mathematics as $\{b : b \in {\rm bases(bm)}\}$. Of course, listing the contents of an iterable object is such a common activity that you can just use

sage: list(bm.bases())

to get the same result.

The circuits of the matroid are the minimal dependent sets of columns, and unsurprisingly can be accessed by

sage: bm.circuits()
Iterator over a system of subsets
sage: len(bm.circuits())
14

What if we want to know the lines of the binary matroid, which are the circuits of size 3. Again the Python notation is straightforward for mathematicians:

sage: [c for c in bm.circuits() if len(c) == 3]
[frozenset([0, 1, 2]),
frozenset([0, 3, 4]),
frozenset([2, 4, 5]),
frozenset([1, 3, 5]),
frozenset([0, 5, 6]),
frozenset([1, 4, 6]),
frozenset([2, 3, 6])]

And there, we have the list of the lines of the Fano plane, exactly as expected. A frozen set is iterable, and so we can smarten up the output easily enough.

sage: [list(c) for c in bm.circuits() if len(c) == 3]
[[0, 1, 2], [0, 3, 4], [2, 4, 5], [1, 3, 5], [0, 5, 6], [1, 4, 6], [2, 3, 6]]

So there we have our first run through the absolute basics of using sage_matroids. Next time, I’ll move on to using – and building on – some of the more sophisticated built-in functions.

## A matroid / geometry problem and conjecture

Rather than let this blog die off due to lack of posts, I thought I’d write about a small but annoying problem that I’ve been thinking about recently, but without success, and a natural conjecture that has arisen from it.

[Note: On some browsers there appears to be a sizing problem with the images WordPress uses for LaTeX formulas, and they appear ten times the right size. If this happens, reloading the webpage seems to fix it]

The problem arose in the context of binary matroids, but because a binary matroid is really just a set of points in a binary vector space, it can be phrased entirely as a linear algebra problem.

So let ${M}$ be a set of non-zero vectors in the vector space ${V = GF(2)^r}$ such that ${M}$ spans ${V}$ and, for reasons to be clarified later, no vector in ${M}$ is independent of the others. In matroid terminology, this just says that ${M}$ is a simple binary matroid of rank ${r}$ with no coloops.

Then define a  basis of ${M}$ to be a linearly independent subset of ${M}$ of rank ${r}$ (in other words, just a basis of ${V}$ and a circuit of ${M}$ to be a minimally dependent set of vectors, i.e. a set of vectors that is linearly dependent but any proper subset of which is linearly independent.

As an example, take ${M = PG(2,2)}$ (a.k.a the Fano plane) — this means to take all the non-zero vectors in ${GF(2)^3}$. This has 28 bases (7 choices for a first vector ${v}$, 6 for a second vector ${w}$ and then 4 for the third vector which cannot be ${v}$, ${w}$ or ${v+w}$ , then all divided by 6 because this counts each basis ${6}$ times). It has 7 circuits of size 3 (each being of the form ${v}$, ${w}$, ${v+w}$) and 7 circuits of size 4, being the complements of the circuits of size 3, for a total of 14 circuits.

Letting ${b(M)}$, ${c(M)}$ denote the numbers of bases and circuits of ${M}$ respectively, the question is about the ratio of these two numbers. More precisely,

Determine a lower bound, in terms of the rank ${r}$, for the ratio ${\frac{b(M)}{c(M)}}$?

## The Merino-Welsh Conjecture

The Merino-Welsh conjecture is an intriguing conjecture relating three graphical parameters, namely the numbers of spanning trees, acyclic orientations and totally cyclic orientations of a graph.

First recall the definitions of these terms: an orientation of a graph is an assignment of directions to the edges of the graph (thus there are $2^m$ orientations for an $m$-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 $n$-vertex graph has $(n-1)$ edges. We denote these three quantities $\tau(G)$ for trees, $\alpha(G)$ for acyclic orientations and $\alpha^*(G)$ for totally cyclic orientations.  Then we have the conjecture, due to serial conjecturer Dominic Welsh, and his former student Criel Merino.

Conjecture (Merino, Welsh) If $G$ is a multigraph with no bridges or loops, then $\tau(G) \le \max(\alpha(G),\alpha^*(G))$.

There are various stronger versions of this conjecture, such as having $\tau(G)$ less than the arithmetic or geometric mean of the other two parameters, but all seem equally difficult and equally unsolved.

Speaking very loosely, if the graph is somewhat sparse, with relatively few edges given the number of vertices, then acyclic orientations are favoured and so $\alpha(G)$ tends to dominate the number of spanning trees, while if the graph is dense, then the number of totally cyclic orientations tends to dominate. The best partial results on the conjecture are essentially about graphs at one end of the spectrum or the other, where one or other of the parameters dominates so much that relatively coarse, though ingenious, approximations are sufficient to demonstrate this fact. So, the following results are known, due to Carsten Thomassen:

• If the bridgeless multigraph $G$ has at least $4n-4$ edges, then $\tau(G) < \alpha^*(G)$.
• If $G$ is a graph (not multigraph) with at most $16n/15$ edges, then $\tau(G) < \alpha(G)$.

Obviously there is a huge gap between these bounds. It is conceivable however that there is a range of low densities where $\alpha(G)$ dominates $\tau$ (i.e. regardless of the structure of $G$) and a range of higher densities where $\alpha^*(G)$ dominates $\tau$, and that these two ranges overlap. In fact, Thomassen asked whether $m = 2n-2$ edges could possibly be the dividing point, so that any multigraph with at most $2n-2$ edges has $\alpha(G) < \tau(G)$ and any multigraph with at least $2n-2$ edges has $\tau(G) < \alpha^*(G)$. Unfortunately this is not true, as there are graphs with exactly $2n-2$ edges that have more spanning trees than acyclic orientations.

In some sense, although it may work, this approach seems rather unsatisfactory — the conjecture concerns the interplay of two dual parameters whereas the known results essentially focus on just one of the two.  This follows because all three parameters are actually evaluations of the Tutte polynomial of the graph at various points. In fact, if $T$ is the Tutte polynomial of $G$, then:

• $\tau(G) = T(1,1)$
• $\alpha(G) = T(2,0)$
• $\alpha^*(G) = T(0,2)$

So if $G$ is planar, then it has the same number of spanning trees as its planar dual, but the numbers of acyclic and totally cyclic orientations swap round. Of course, we don’t need to restrict ourselves to planar graphs – the Tutte polynomial is defined for any matroid, graphic or otherwise, and so the conjecture can be made just as $T(1,1) \le \max(T(2,0),T(0,2))$ 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.

As well as evaluating the Tutte polynomial at specific points to get numbers, we can get a variety of 1-variable polynomials from it by partially specifying the values, and lots of common graph and matroid polynomials (chromatic, flow, reliability etc) arise in this way. So we could define $f(z) = T(1+z,1-z)$ and consider the behaviour of this single-variable polynomial for $z \in [-1,1]$. In particular, it is quite possible that $f(z)$ is convex throughout its domain, except for the case where $G$ is a tree with every edge doubled, in which case $f(z)$ is actually constant. Conde and Merino said that this would make a “rather more daring strengthening of the conjecture” which I have paraphrased to incorporate matroids:

Conjecture (Conde-Merino, but for graphs only)  If $M$ is a matroid with no loops or co-loops with Tutte polynomial $T$, then $T(1-z,1+z)$ is convex on the range $z \in [-1,1]$ unless $M$ is a direct sum of pairs of parallel elements.

## Matroid theory at “La Vacquerie-et-Saint-Martin-de-Castries”

While John & Michael are in Irsee doing some finite geometry, I’m in the South of France at a matroid theory gathering organized in the tiny village of La Vacquerie-et-Saint-Martin-de-Castries which is high up on the Larzac Plateau in the South of France.

This may seem an unlikely place for a conference, but it is where one of the eminence grises of matroid theory, Henry Crapo, lives. Henry is an amazing and eclectic personality who lives in a wonderful house large enough to double as a personal conference centre that he calls Les Moutons Matheux. As the village (approximately 135 inhabitants) has no real shops, Henry engaged a personal chef who prepared amazing meals entirely from local “bio” produce.

## Binary matroids with no K_5 minor

I gave my talk at the Maastricht workshop yesterday and so here are the slides (Maastricht talk).

Matroid theory is not especially well known (in fact, when he gave a talk here, Brian Alspach used a result from matroid theory and described the subject as “the one that is allocated the smallest and furthest away room in any conference that has parallel sessions”) and so usually it’s necessary to put a lot of basic definitions into any talk. Fortunately this occasion, where everyone is working in matroids, is an exception and so I could launch straight in.

In some sense, binary matroids are a generalization of graphs, and so any question that can be asked about graphs can be asked unchanged about binary matroids. In the 1930s Klaus Wagner proved the famous excluded minor result

A graph is planar if and only if it does not have the complete graph $K_5$ or the complete bipartite graph $K_{3,3}$ as a minor.

He also gave a description of the graphs that do not have $K_5$  as a minor, and similarly the class obtained by excluding $K_{3,3}$.

We (that is,  me and my friends from Wellington NZ, Geoff Whittle and Dillon Mayhew) are trying to extend these two results to binary matroids and get descriptions of the exact structure of those classes. It turned out that the case for excluding $K_{3,3}$ was tractable, though we ended up with a long 113 page paper that has just appeared in the Memoirs of the American Mathematical Society. But excluding $K_5$ seems much more difficult and we really don’t know where to go from here.

My talk basically describes what we’ve done and where we’re stuck!