Alon conjectured in 1995 that there is an absolute constant CC such that every finite group GG has a Cayley graph whose clique number and independence number are both at most Clog⁡∣G∣C\log|G| (a CC-Ramsey Cayley graph). Conlon, Fox, Pham and Yepremyan (arXiv:2412.21194, 2024) proved the conjecture for abelian groups of almost all orders and for finite vector spaces of characteristic at least 5, and identified the elementary abelian groups F2n\mathbb{F}_2^n and F3n\mathbb{F}_3^n as the principal open cases: their methods, and the uniform random Cayley graph itself, provably fail in characteristics 2 and 3. They pose an intermediate question (their Conjecture 5.1): is there a constant C>0C>0 such that every nn admits a two-coloring of F2n∖{0}\mathbb{F}_2^n\setminus\{0\} with no monochromatic subspace of size at least CnCn? Schildkraut's December 2025 extension to all groups of almost all orders has a hypothesis that explicitly excludes the orders 2n2^n and 3n3^n. The small-characteristic cases and Conjecture 5.1 remain open as of August 2026.

Background

For a finite group GG and a symmetric subset S⊆G∖{1}S\subseteq G\setminus\{1\}, the Cayley graph Cay(G,S)\mathrm{Cay}(G,S) has vertex set GG, with distinct vertices x,yx,y adjacent when x−1y∈Sx^{-1}y\in S; Cayley graphs are the natural algebraically defined graph family, and every Cayley graph is a vertex-transitive (in fact regular, with all vertices equivalent under the group action) graph. The clique number of a graph is the size of its largest complete subgraph, and its independence number is the size of its largest set of pairwise non-adjacent vertices, which is the clique number of the complement. A graph on NN vertices is called CC-Ramsey if both numbers are at most Clog⁡NC\log N. This is essentially the best behavior allowed by Ramsey theory: the classical Erdős–Szekeres argument forces every NN-vertex graph to have a clique or an independent set of order about 12log⁡N\tfrac{1}{2}\log N (and the recent breakthrough of Campos, Griffiths, Morris and Sahasrabudhe improves this lower bound slightly), while Erdős's probabilistic argument shows that a uniformly random graph has clique and independence numbers at most 2log⁡N2\log N with high probability, where 'with high probability' means with probability tending to one as N→∞N\to\infty. So Ramsey graphs exist in abundance, yet no explicit construction is known to be CC-Ramsey for any constant CC.

Alon conjectured in 1995 (in his 'Research problems' column in Discrete Mathematics) that algebraic structure is no obstruction: there should be an absolute constant CC such that every finite group has a CC-Ramsey Cayley graph. The question is motivated partly by information theory, where Alon and Orlitsky connected Ramsey Cayley graphs to the efficiency of repeated-communication protocols, and partly by the long-standing failure to prove that any explicit family — most famously the Paley graphs, the Cayley graphs in which SS is the set of nonzero squares in a finite field — is Ramsey.

The prior results define the frontier. Alon showed that the uniform random Cayley graph on any group of order NN has clique and independence numbers O(log⁡2N)O(\log^2 N) with high probability, giving a universal O(log⁡2N)O(\log^2 N) bound. Green proved the conjecture for cyclic groups: the random Cayley graph on ZN\mathbb{Z}_N has clique number O(log⁡N)O(\log N) with high probability, and Green and Morris later sharpened the prime case to (2+o(1))log⁡N(2+o(1))\log N, matching the random graph. Conlon, Fox, Pham and Yepremyan (2024) then proved: (i) on any group of order NN the random Cayley graph has clique number at most Clog⁡Nlog⁡log⁡NC\log N\log\log N with high probability; (ii) Alon's conjecture holds for abelian groups of order NN for almost all NN and for finite vector spaces of characteristic at least 5 (their most general theorem needs a large abelian subgroup of order coprime to 6); and (iii) in characteristic congruent to 1(mod4)1\pmod 4 there is a self-complementary (isomorphic to its own complement) Cayley graph with clique and independence numbers at most (2+o(1))log⁡N(2+o(1))\log N, solving in strong form the self-complementary problem of Alon and Orlitsky.

The obstruction in small characteristic is subgroup structure. If all non-identity elements of a subgroup HH lie in the connection set SS, then HH is a clique, and over F2n\mathbb{F}_2^n (order N=2nN=2^n, so log⁡N=Θ(n)\log N=\Theta(n)) subspaces dominate: Green observed that the uniform random Cayley graph there has clique number Θ(log⁡Nlog⁡log⁡N)\Theta(\log N\log\log N) with high probability, so uniform randomness provably cannot witness the conjecture. Worse, a classical Ramsey result, the finite unions theorem, implies that every two-coloring of the nonzero elements of F2n\mathbb{F}_2^n contains a monochromatic subspace (a linear subspace all of whose nonzero elements receive one color) once nn is large enough, so one cannot hope to avoid monochromatic subspaces entirely — only to bound their size. Conlon, Fox, Pham and Yepremyan therefore pose Conjecture 5.1 as an intermediate step: there exists C>0C>0 such that, for every nn, some two-coloring of F2n∖{0}\mathbb{F}_2^n\setminus\{0\} has no monochromatic subspace of size at least CnCn. This would follow automatically from Alon's conjecture over F2n\mathbb{F}_2^n, since the nonzero elements of a monochromatic subspace form a clique or an independent set of size ∣H∣−1|H|-1 in the corresponding Cayley graph. The quantitative gap is enormous: adapting Sanders' quantitative bounds for Rado's theorem on partition-regular linear equations, every two-coloring of F2n∖{0}\mathbb{F}_2^n\setminus\{0\} is known to contain a monochromatic subspace only of iterated-logarithmic size in nn, while the conjecture predicts colorings avoiding all linear-size monochromatic subspaces.

Most recently, Schildkraut (December 2025) extended the approach to all, not necessarily abelian, groups of almost all orders — indeed to every group whose order has no large factor that is a product of powers of 2 and 3 — proving each has a 2400024000-Ramsey Cayley graph, via new structure theorems for approximate subgroups (subsets AA with AAAA covered by few translates of AA). The hypothesis of his theorem deliberately excludes the orders 2n2^n and 3n3^n, and his paper treats small characteristic as remaining open. As of August 2026, no subsequent work resolves the small-characteristic cases or Conjecture 5.1.

Problem Statement

The problem is the small-characteristic case of Alon's conjecture on Ramsey Cayley graphs — the case that Conlon, Fox, Pham and Yepremyan (arXiv:2412.21194) explicitly identify as open. Alon's full conjecture (1995) asserts that there is an absolute constant CC such that every finite group GG admits a Cayley graph whose clique number and independence number are both at most Clog⁡∣G∣C\log|G|; the derived, still-open restriction is to the elementary abelian families of characteristic 2 and 3:

(1) Does there exist an absolute constant CC such that, for every n≥1n\ge 1, the group F2n\mathbb{F}_2^n admits a Cayley graph whose clique number and independence number are both at most Clog⁡∣G∣C\log|G| (where ∣G∣=2n|G|=2^n), and likewise the group F3n\mathbb{F}_3^n (where ∣G∣=3n|G|=3^n)? A negative answer — a proof that along an infinite sequence of nn, every Cayley graph on F2n\mathbb{F}_2^n (or on F3n\mathbb{F}_3^n) has clique or independence number superlogarithmic in ∣G∣|G| — also resolves the question.

(2) As the authors' proposed intermediate step toward the F2n\mathbb{F}_2^n case (their Conjecture 5.1, an automatic corollary of (1) for F2n\mathbb{F}_2^n): does there exist a constant C>0C>0 such that, for every nn, there is a two-coloring of F2n∖{0}\mathbb{F}_2^n\setminus\{0\} containing no subspace HH of size at least CnCn all of whose nonzero elements receive the same color?

Both parts serve one scientific objective: establishing (or refuting) optimal-order Ramsey graphs within the Cayley family over the small-characteristic vector spaces, with part (2) following automatically from the F2n\mathbb{F}_2^n case of part (1) and proposed by the source authors as an intermediate step toward it. Both are uniform statements over all nn; an answer must establish the bound for every nn (or refute uniformity via an infinite family of nn), not merely for finitely many dimensions. A complete solution resolves part (1) for both F2n\mathbb{F}_2^n and F3n\mathbb{F}_3^n; resolving only the intermediate statement (2) is a partial step toward the F2n\mathbb{F}_2^n case and does not by itself resolve the task.

References

  1. D. Conlon, J. Fox, H. T. Pham, L. Yepremyan, On the clique number of random Cayley graphs and related topics, arXiv preprint (2024). Identifier: arXiv:2412.21194, DOI: 10.48550/arXiv.2412.21194, https://arxiv.org/abs/2412.21194
  2. N. Alon, Research problems, Discrete Mathematics 138 (1995), 405–411. Identifier: DOI 10.1016/0012-365X(95)90059-T, https://doi.org/10.1016/0012-365X(95)90059-T
  3. B. Green, Counting sets with small sumset, and the clique number of random Cayley graphs, Combinatorica 25 (2005), 307–326. Identifier: DOI 10.1007/s00493-005-0018-2, https://doi.org/10.1007/s00493-005-0018-2
  4. B. Green, R. Morris, Counting sets with small sumset and applications, Combinatorica 36 (2016), 129–159. Identifier: DOI 10.1007/s00493-015-3129-4, https://doi.org/10.1007/s00493-015-3129-4
  5. N. Alon, A. Orlitsky, Repeated communication and Ramsey graphs, IEEE Transactions on Information Theory 41 (1995), 1276–1289. Identifier: DOI 10.1109/18.412676, https://doi.org/10.1109/18.412676
  6. C. Schildkraut, Abelian structure in approximate groups and Alon's conjecture on Ramsey Cayley graphs, arXiv preprint (2025). Identifier: arXiv:2512.15125, DOI: 10.48550/arXiv.2512.15125, https://arxiv.org/abs/2512.15125
  7. N. Alon, H. T. Pham, Random Cayley graphs and random sumsets, arXiv preprint (2025). Identifier: arXiv:2509.02561, DOI: 10.48550/arXiv.2509.02561, https://arxiv.org/abs/2509.02561
  8. T. Sanders, Bootstrapping partition regularity of linear systems, Proceedings of the Edinburgh Mathematical Society 63 (2020), 630–653. Identifier: DOI 10.1017/s0013091520000048, https://doi.org/10.1017/s0013091520000048
  9. N. Tung, Coloring sparse random Cayley graphs, arXiv preprint (2026). Identifier: arXiv:2606.23762, DOI: 10.48550/arXiv.2606.23762, https://arxiv.org/abs/2606.23762
  10. M. Campos, S. Griffiths, R. Morris, J. Sahasrabudhe, An exponential improvement for diagonal Ramsey, arXiv preprint (2023). Identifier: arXiv:2303.09521, DOI: 10.48550/arXiv.2303.09521, https://arxiv.org/abs/2303.09521