The Edge-Orbit Conjecture of Babai

✍ Scribed by A.J. Goodman

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 414 KB
• Volume: 57
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1993.1003

✦ Synopsis

This paper proves the Edge-Orbit Conjecture stated by L. Babai (1981, in "Combinatorics" (H. N. V. Temperley, Ed.), pp. 1-40, Cambridge Univ. Press, London). We say a graph (X) represents a group (G) if (\operatorname{Aut}(X) \cong G). Let (m_{c}(G)) be the minimum number of edge orbits among all graphs (X) which represent (G). The Edge-Orbit Conjecture was that (m_{i}(G)) is unbounded when (G) ranges over all finite groups. We show this is true using (p)-groups of class two and exponent (p). The proof uses a characterization theorem from a recent paper of L. Babai, A. J. Goodman, and L. Lovász (1991, European J. Combin. 12) to bound (m_{e}(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_{r}(G)) has a lower bound proportional to (\sqrt{\log |G|}).

1993 Academic Press, Inc.