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.

## Leave a Reply