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.

FinInG (a finite geometry package for GAP)

Over a long period time, there have been numerous people involved in developing a GAP package which deals primarily with objects in finite geometry. It all started when Max Neunhöffer visited Perth about seven years ago, and Maska Law, Sven Reichard, Michel Lavrauw and I were interested in systematically developing this package. Max is a GAP guru and taught us much about how to properly design code and he led the way on the group theoretic side of things. In fact, if it wasn’t for the GenSS and Orb packages, our package would not be as nice as it is now.

Continue reading “FinInG (a finite geometry package for GAP)”

Using “atlasrep” to find maximal subgroups

One of the things I do most often in the computer algebra software GAP is call for subgroups, and in particular, maximal subgroups of a classical group. There is work in progress (John Bray, Derek Holt, Colva Roney-Dougal) to have the maximal subgroups of low-dimensional classical groups available in GAP and Magma, but for the moment, there is a neat way to have access to these subgroups using the atlasrep package (developed by Robert Wilson, Richard Parker, Simon Nickerson, John Bray, Thomas Breuer).

In short, the atlasrep package allows the user to access permutation and matrix representations of almost simple groups that are in the online Atlas of Finite Group Representations. I often need a one-line command to get the maximal subgroups of a group that is in the ‘atlas’, and so I’ve fashioned my own little function, and I thought I should share it:

AtlasMaximalSubgroups := function( name )
  local tocs, gapname, numbers, maxs;
  if AtlasOfGroupRepresentationsInfo.remote = true  then
     tocs := AtlasTableOfContents( "remote" ).TableOfContents;
  else
     tocs := AtlasTableOfContents( "local" ).TableOfContents;
  fi;
  gapname := First( AtlasOfGroupRepresentationsInfo.GAPnames, pair -> pair[1] = name );
  gapname := gapname[2];
  numbers := List(tocs!.(gapname)!.maxes, t -> t[2]);
  maxs := List(numbers, t -> AtlasSubgroup(name, t));
  return maxs;
end;

To use it, here is an example for PSp(6,2) (which is called “S6(2)” in the ‘atlas’ world), which GAP will struggle to do without using atlasrep:

gap> LoadPackage("atlasrep");
gap> group := AtlasGroup( "S6(2)" );
gap> maximals := AtlasMaximalSubgroups( "S6(2)" );
gap> Index(group, maximals[3]);

Up ↑