Last week I was at the Symmetries of Graphs and Networks IV conference at Rogla in Slovenia. The conference webpage is here. At the same time was the annual PhD summer school in discrete maths. As usual it was a very enjoyable and well organised conference. It was good to catch up with some of the regulars and meet a few new people as well
I was one of the invited speakers and spoke about some of the work that I have been doing recently with Luke Morgan on graph-restrictive permutation groups. The slides are available here. The two relevant preprints are on the arxiv here and here.
Last week, I attended an excellent conference “Groups, Computation and Geometry” at the Pingree Park Conference Centre in the Colorado mountains. It was organised magnificently by Peter Brooksbank, Alexander Hulpke, Bill Kantor, Tim Penttila, and James Wilson. Pingree Park is at 9,000 feet (2,700 metres) and I did have headache on the last two days. My trip started badly with a case of gastro, but luckily I had arrived some three days before the conference, so by the second day of talks, I was feeling much better. My 50 minute talk had to be rescheduled to the Friday of the conference, because of this. Apart from your’s truly, the invited talks were given by Colva Roney-Dougal, Şükrü Yalçınkaya, Eric Moorhouse, and Simon Blackburn. Colva spoke about using pregroups to solve problems in combinatorial group theory, mainly word problems, and getting around in a Van Kampen diagram. Şükrü waved the flag for the computational group theorists and spoke on black-box recognition of classical groups. Eric waved the geometry flag and spoke on p-ranks of incidence matrices, and in particular, on ways to attack the “prime-order projective plane implies Desarguesian” conjecture. Simon’s talk carried the main theme of different types of discrete logarithm problems and their application to elliptic curve cryptography. All of these talks were amazing, and I followed each one with keen interest.
Bill Kantor was the master of the schedule, and I was one of only a few that enjoyed the format: only Bill knew who was speaking when, and the program for the subsequent day would be posted on a door each evening. No titles or abstracts, just the expectation that you would see the next talk and you would know then and there what it would be about. It’s good reasoning: if you wanted to know the title and abstract before hand, it might be because you were choosing whether to go or not, and with such a cosy conference, that is out of the question! The other argument, might be that you wanted to do some prior reading before the talk, but would you really? Read more…
Below is a guest blog post of Melissa Lee, who took part in a six-week summer vacation research project supported by the Australian Mathematical Sciences Institute.
Hi everyone! My name is Melissa Lee and I’ve recently started honours with John and Dr. Eric Swartz here at UWA. This past summer I have been working with John on an AMSI Vacation Research Scholarship. My AMSI VRS project was based on looking at structures embedded in an affine space by viewing them in terms of a game called SET. Read more…
I’m writing this post so that I can direct my students to it as I often have to go over the evolution of the concepts of ovoids of projective spaces and polar spaces, and to explain that they are (i) different, and (ii) connected. It’s a bit dry, but it will serve as a reference for future posts.
Ovoids of projective spaces
I will start with a result of Jacques Tits in 1962, though ovoids arose earlier in the work of Bose and Qvist. An ovoid of a projective space is a set of points such that for any point of , the union of the lines incident with that are tangent to forms a hyperplane of . Tits showed that an ovoid of exists if and only if . For , we should be careful to stipulate that , since the size of an ovoid of is just 5 and things are a bit messy to state. By a simple counting argument, the number of points of an ovoid of is , and for a projective plane of order , an ovoid has size . For example, the elliptic quadric of is an example of an ovoid, and a non-singular conic is an example of an ovoid of . For more on the elliptic quadric example, see this post.
In the planar case, we now call these objects ovals, and reserve the name ‘ovoid’ just for the 3-dimensional case. Now an ovoid and oval have the property that no 3 points are collinear. We have the following way to think of an ovoid in three different ways:
Let be a set of points of . The following are equivalent:
- No 3 points of are collinear and ;
- For any point of , the union of the lines incident with that are tangent to span a plane of ;
- At every point of , there is a unique plane that meets only in (i.e., a tangent plane).
Ovoids of polar spaces
Jef Thas defined ovoids of polar spaces in his seminal paper “Ovoidal translation planes” in 1972. It is a set of points such that every maximal totally isotropic subspace meets it in precisely one point. Alternatively, we could define it as a set of points no two collinear, with size the number of points divided by the number of points in a maximal. We have:
Let be a set of points of a finite polar space , and let be the number of points of divided by the number of points lying in a maximal totally istropic subspace. The following three are equivalent:
- No 2 points of are collinear and ;
- Every maximal totally isotropic subspace has exactly one point of incident with it.
- At every point of , there exists a maximal totally isotropic subspace through tangent to .
So where did Thas’ definition come from? The most impressive result of his 1972 paper is the connection between ovoids of the rank 2 symplectic space and ovoids of the 3-dimensional projective spaces.
Theorem (Thas 1972): Let be an even prime power. Then an ovoid of is also an ovoid of . Conversely, if is an ovoid of , then we can define a null polarity defining a such that are absolute points for .
This result is quite remarkable. It certainly is easier to study and enumerate ovoids of , than in . The null polarity hinted at by the theorem is truly beautiful and was first known to Segre (1959): given a point of , we define to be the unique tangent plane at ; for each secant plane of we define to be the nucleus of the oval carved out (i.e., the nucleus of ).
The situation for odd was already classified independently by Barlotti and Panella (1965): the only ovoids in this case are quadrics. So the open problem on classifying ovoids of boils down to the even case.
Another reason for defining ovoids this way is that it encapsulates natural examples. A non-degenerate hyperplane section of the Hermitian polar space is an ovoid, and a non-degenerate hyperplane section of minus type of the parabolic quadric is an ovoid. Plus, we can think of the non-singular conic as a rank 1 polar space , and hence an ‘ovoid’ of coincides trivially with an oval of .
In a future post, I’ll talk about the open problems on ovoids of polar spaces.
I’m advertising for a 2-year postdoc to work on problems relating to the real chromatic roots of graphs and matroids.
The (procedural) details are here:
If you know any bright students (or if you are a bright student) completing their PhDs in this sort of mathematics and/or statistical physics (partition function of the q-state Potts model etc) then please let them know.
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 , the
matroid obtained by deleting an arbitrary element from , 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
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
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
The only minor wrinkle is to remember to use the right name for the built-in functions.
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!
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.