The edge-orbit conjecture of Babai (Q757411)

This paper proves the Edge-Orbit Conjecture stated by \textit{L. Babai} [Combinatorics, Proc. 8th Conf., Swansea 1981, Lond. Math. Soc. Lect. Notes Ser. 52, 1-40 (1981; Zbl 0467.05031)]. A graph X is said to represent a group \(G\) if \(Aut(X)\cong G.\) Let \(m(G)\) be the minimum number of edge orbits among allgraphs \(X\) which represent \(G\). The Edge-Orbit Conjecture was that m(G) is unbounded when \(G\) ranges over all finite groups. This is shown to be true using \(p\)-groups of class two and exponent \(p\). The proof uses a characterization theorem from a recent paper [\textit{L. Babai}, the author, and \textit{L. Lovász}, Eur. J. Comb. 12, 185-203 (1991)] to bound \(m(G)\) from below when all subgroups of \(G\) are either `small' enough or `large' enough (so that there will be enough automorphisms leaving any small set of subgroups invariant). Then a probabilistic proof is used to show non-constructively that plenty of groups exist whose subgroups have this property. The proof shows that there is an infinite family of groups \(G\) for which \(m(G)\) has a lower bound proportional to \(\sqrt{\log | G|}\).