Alon's Ramsey Cayley conjecture for the small-characteristic vector spaces $\mathbb{F}_2^n$ and $\mathbb{F}_3^n$, and the associated subspace-coloring problem

Alon conjectured in 1995 that there is an absolute constant $C$ such that every finite group $G$ has a Cayley graph whose clique number and independence number are both at most $C\log|G|$ (a $C$-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 $\mathbb{F}_2^n$ and $\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>0$ such that every $n$ admits a two-coloring of $\mathbb{F}_2^n\setminus\{0\}$ with no monochromatic subspace of size at least $Cn$? Schildkraut's December 2025 extension to all groups of almost all orders has a hypothesis that explicitly excludes the orders $2^n$ and $3^n$. The small-characteristic cases and Conjecture 5.1 remain open as of August 2026.

Background

For a finite group $G$ and a symmetric subset $S\subseteq G\setminus\{1\}$, the Cayley graph $\mathrm{Cay}(G,S)$ has vertex set $G$, with distinct vertices $x,y$ adjacent when $x^{-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 $N$ vertices is called $C$-Ramsey if both numbers are at most $C\log N$. This is essentially the best behavior allowed by Ramsey theory: the classical Erdős–Szekeres argument forces every $N$-vertex graph to have a clique or an independent set of order about $\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 $2\log N$ with high probability, where 'with high probability' means with probability tending to one as $N\to\infty$. So Ramsey graphs exist in abundance, yet no explicit construction is known to be $C$-Ramsey for any constant $C$.

Alon conjectured in 1995 (in his 'Research problems' column in Discrete Mathematics) that algebraic structure is no obstruction: there should be an absolute constant $C$ such that every finite group has a $C$-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 $S$ 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 $N$ has clique and independence numbers $O(\log^2 N)$ with high probability, giving a universal $O(\log^2 N)$ bound. Green proved the conjecture for cyclic groups: the random Cayley graph on $\mathbb{Z}_N$ has clique number $O(\log N)$ with high probability, and Green and Morris later sharpened the prime case to $(2+o(1))\log N$, matching the random graph. Conlon, Fox, Pham and Yepremyan (2024) then proved: (i) on any group of order $N$ the random Cayley graph has clique number at most $C\log N\log\log N$ with high probability; (ii) Alon's conjecture holds for abelian groups of order $N$ for almost all $N$ 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\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$, 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 $H$ lie in the connection set $S$, then $H$ is a clique, and over $\mathbb{F}_2^n$ (order $N=2^n$, so $\log N=\Theta(n)$) subspaces dominate: Green observed that the uniform random Cayley graph there has clique number $\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 $\mathbb{F}_2^n$ contains a monochromatic subspace (a linear subspace all of whose nonzero elements receive one color) once $n$ 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>0$ such that, for every $n$, some two-coloring of $\mathbb{F}_2^n\setminus\{0\}$ has no monochromatic subspace of size at least $Cn$. This would follow automatically from Alon's conjecture over $\mathbb{F}_2^n$, since the nonzero elements of a monochromatic subspace form a clique or an independent set of size $|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 $\mathbb{F}_2^n\setminus\{0\}$ is known to contain a monochromatic subspace only of iterated-logarithmic size in $n$, 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 $24000$-Ramsey Cayley graph, via new structure theorems for approximate subgroups (subsets $A$ with $AA$ covered by few translates of $A$). The hypothesis of his theorem deliberately excludes the orders $2^n$ and $3^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 $C$ such that every finite group $G$ admits a Cayley graph whose clique number and independence number are both at most $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 $C$ such that, for every $n\ge 1$, the group $\mathbb{F}_2^n$ admits a Cayley graph whose clique number and independence number are both at most $C\log|G|$ (where $|G|=2^n$), and likewise the group $\mathbb{F}_3^n$ (where $|G|=3^n$)? A negative answer — a proof that along an infinite sequence of $n$, every Cayley graph on $\mathbb{F}_2^n$ (or on $\mathbb{F}_3^n$) has clique or independence number superlogarithmic in $|G|$ — also resolves the question.

(2) As the authors' proposed intermediate step toward the $\mathbb{F}_2^n$ case (their Conjecture 5.1, an automatic corollary of (1) for $\mathbb{F}_2^n$): does there exist a constant $C>0$ such that, for every $n$, there is a two-coloring of $\mathbb{F}_2^n\setminus\{0\}$ containing no subspace $H$ of size at least $Cn$ 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 $\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 $n$; an answer must establish the bound for every $n$ (or refute uniformity via an infinite family of $n$), not merely for finitely many dimensions. A complete solution resolves part (1) for both $\mathbb{F}_2^n$ and $\mathbb{F}_3^n$; resolving only the intermediate statement (2) is a partial step toward the $\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