The second week in Perth is over. Yesterday we went to Rottnest Island, named by the Dutch sea captain Vlaminck (“rats’ nest”) who mistook the quokkas for large rats; it is Wadjemup in the local Noongar language, and Rotto informally. It is an extraordinary place for birds. The picture shows a black-winged stilt (with what might be a plover of some sort behind), a pelican, baby oystercatchers, and a crested tern. And of course there were more quokkas than you could shake a stick at:
This one is a bit unusual; they are mostly very tame, especially round the settlement, but the first two we saw ran into the bushes to hide from us.
On Friday I gave a seminar on “Idempotent generation and road closures”; fortuitously, an email came round warning of further road closures in St Andrews that very day, and I was able to include it in my slides.
Without going into the connection with road closures, the question is: for which transitive permutation groups G is it true that, if O is an orbit of G on 2-subsets of the domain of G, and B a maximal block of imprimitivity for G acting on O, then the graph with edge set O\B is connected?
We know that such a group must be primitive, and must be basic (that is, preserves no Cartesian power structure on its domain). Moreover, João Araújo and I conjecture that, if G is a basic primitive permutation group such that G has no imprimitive subgroup of index 2 and also is not one of a class of examples related to the phenomenon of triality, then G has our “road closure” property.
Since I have been here, Cheryl Praeger and I have thought about one case of this problem, and have been thinking more generally about removing edges from a vertex-transitive graph to disconnect it.
Classical results of Mader and others assert that, if Γ is a vertex-transitive graph of valency k, then the edge-connectivity of Γ is k; this means that removing fewer than k edges do not disconnect the graph. Clearly it can be disconnected by removing the k edges through a vertex, to isolate that vertex. But the argument gives a little bit more. A set of k edges whose removal disconnects the graph must be either the edges through a vertex, or the k edges each with one end in a complete subgraph of size k. (Graphs with this property can be obtained from arc-transitive graphs by replacing each vertex with a clique of size k, each of whose vertices is on one of the edges through the original vertex.)
The second kind of disconnecting set cannot arise in an edge-transitive graph except for a cycle (with k=2) or a complete graph of size k+1, since in general the edges in the clique cannot be equivalent to the other edges under an automorphism.
The proof of this uses the concept of an atom. The boundary of a set of vertices is the set of edges having one end in that set; an atom is a set A of vertices whose boundary is minimal, and subject to that the size of A is minimal.
Cheryl went on to look at “pseudo-atoms”, sets of vertices whose boundary is minimal subject to being greater than k, and subject to this the size of the set is minimal. I will just say that if we add in the condition of edge-transitivity then such a set must be a single edge, with boundary of size 2k−2.
This already gives some information on the road-closure problem, and I hope we will have more progress to report soon. But Cheryl is off for a week in London and Paris on mathematics business …