EPPA numbers of graphs

A paper with this title has just gone on the arXiv, 2311.07995.

The random graph, discussed at length here earlier, has the property of homogeneity: any isomorphism between finite subgraphs can be extended to an automorphism of the whole graph. Now unfortunately there are very few finite homogeneous graphs. They were all found by Tony Gardiner in the 1970s. The only ones are disjoint unions of complete graphs of the same size and their complements, the 5-cycle, and the line graph of K_3,3 (the 3×3 grid).

In 1992, Udi Hrushovski established a remarkable result which goes a long way towards rectifying this. He showed that, for every finite graph G, there is a finite graph H containing G as an induced subgraph, such that every partial automorphism of G (isomorphism between induced subgraphs) extends to an automorphism of H. The property is called Extension Property for Partial Automorphisms, or EPPA for short, and the graph H is called an EPPA witness for G. (This would be trivial if there were enough finite homogeneous graphs that every finite graph is embeddable as induced subgraph in a homogeneous graph; but this is far from true!)

The obvious questions are: How large does an EPPA witness have to be? And what other classes of structures have EPPA witnesses?

On the second question, quite a bit is known: some kinds of things do, some don’t, and in somce cases (such as tournaments) the answer is unknown.

For the first question, we have a new graph-theoretic parameter to study, the EPPA number of a graph (the smallest number of vertices of an EPPA witness). The paper on the arXiv, by David Bradley-Williams, Jan Hubička, Matěj Konečný and me, has some results on this, including upper and lower bounds for the smallest EPPA witness for every n-vertex graph, roughly 2ⁿ. Also, we have a good estimate for the almost sure size of the smallest EPPA witness for an n-vertex random graph.

In fact David and I had been working intermittently on EPPA for several years. I want to give a bit of a teaser for our work, which might soon be forthcoming.

The main observation is that the smallest EPPA witness H for a graph G has a lot of symmetry. If we take the number of vertices to be as small as possible, then H is vertex-transitive, and is either vertex-primitive or a cover of a graph having vertex-primitive group with G as an induced subgraph. If we further require that H has the smallest number of edges, then it is arc-transitive. So we would expect to be able to tap into the large amount of knowledge about such graphs.

Indeed we can. As an example, consider the n-cycle graph. It is not too hard to show that the line graph of K_n, with n(n−1)/2 vertices, is an EPPA witness. Using the Classification of Finite Simple Groups, we can show that it is the smallest EPPA witness for all but finitely many n. We do not know the complete list of exceptions, but it is non-empty: for example, the 4-cycle and 5-cycle are homogeneous and so are their own EPPA witnesses, and the smallest EPPA witness of the 6-cycle is the 3×3 grid.