McKay–Praeger conjecture

Let $\mathcal{V}_n$ and $\mathcal{D}_n$ denote, respectively, the sets of labelled vertex-transitive graphs and vertex-transitive digraphs on $[n]=\{1,\ldots,n\}$ , and let $\mathcal{C}_n\subseteq\mathcal{V}_n$ and $\mathcal{K}_n\subseteq\mathcal{D}_n$ denote the subsets consisting of Cayley graphs and Cayley digraphs. The McKay–Praeger conjecture asserts that $\displaystyle\lim_{n\to\infty}\frac{|\mathcal{C}_n|}{|\mathcal{V}_n|}=1$ and $\displaystyle\lim_{n\to\infty}\frac{|\mathcal{K}_n|}{|\mathcal{D}_n|}=1$ ; equivalently, asymptotically almost every labelled vertex-transitive graph and digraph is a Cayley graph or digraph.

References

Primary source

arXiv

Additional references

Asymptotic enumeration of minimally transitive permutation groups — arXiv

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed progress

New counting results strengthen the evidence behind the conjecture, but they do not prove it or disprove it.

The McKay–Praeger conjecture predicts that, as the number of vertices grows, almost every vertex-transitive graph or digraph is a Cayley graph or digraph.

Known results

A conditional strategy shows that controlling transitive $2$ -closed subgroups of $\operatorname{Sym}(n)$ would make non-Cayley vertex-transitive digraphs asymptotically negligible; this remains a conjectural reduction.
For fixed $m\geq 2$ , the proportion of graphs or digraphs with suitable $m$ -semiregular representations exceeds $1-m^2/\sqrt{n}$ for sufficiently large $n$ , but this does not settle the conjecture.

August 2026 asymptotic-enumeration development

A recent paper obtains $2^{\Theta(n\log n)}$ subgroup counts and matching-scale counts for related vertex-transitive graphs and digraphs along prime-power degrees. These results provide structural input toward McKay–Praeger, but the source explicitly does not claim a resolution.

Current status (as of August 2026): The conjecture remains open; recent asymptotic enumeration gives claimed supporting progress, not a proof or counterexample.

Sources

No solutions have been posted yet.