Exponential graph-size conjecture for alternating-group quotients

Let XX be a graph with nn vertices, and let Aut(X)\operatorname{Aut}(X) be its automorphism group. Let AkA_k denote the alternating group on kk letters.

Exponential graph-size conjecture. There exists a constant C>1C>1 such that, if k3k\geq3 and Aut(X)\operatorname{Aut}(X) has an epimorphism onto AkA_k, then

nCk.n\geq C^k.

The conjecture is motivated by Liebeck's result that n2kk2n\geq2^k-k-2 for k13k\geq13 when Aut(X)Ak\operatorname{Aut}(X)\cong A_k, with this bound tight for k0k\equiv0 or 1(mod4)1\pmod4. The broader quotient formulation is left as a conjecture in the supplied text.

Sources & referencesView supporting material

Primary source

Laszlo Babai, “Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker's Conjecture confirmed”, arXiv:2110.08492 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.