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 2*k*−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 …