REVIEW 3 major objections 5 minor 1 cited by
On the clique number of random Cayley graphs and related topics
T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read This paper proves an essentially optimal counting bound for subsets with few colors in properly edge-colored complete graphs, and uses it to show random Cayley graphs have clique number O(log N log log N) and to build Ramsey and…
desk verdict Theorem 1.4 is a real advance, but Section 4 contains a false theorem (4.10) that needs repair before the Ramsey Cayley results can be trusted. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the efficiently colored tree: a tree on at least n/4 of a color-poor subset A, drawn with an ordered list of 900(K+\ln n) colors, built in two phases. First, a random sequence of 900K colors grows each vertex's connected component until it is incident to at least Kn/128 colors; second, 900 ln n further colors coalesce components so their number shrinks by a factor of (1-1/512) per color. The proof that O(K) colors suffice in phase one is Lemma 3.5, an exponential tail bound on the stopping time of the color-growth process; counting these colored trees via Otter's enumeration and then extending each tree to the remaining vertices yields the $N^{{C(K+\ln n)}}$(CK)^n bound. For the Ramsey applications, the same counting result is combined with expansion coming from the absence of monochromatic quadruples {y,2y,4y,8y} and with a Freiman-dimension bound for difference sets in vector spaces.
What would settle it
Run the growth procedure from Lemma 3.4 on the explicit K_n coloring with roughly Kn colors constructed in Lemma 3.15, recording T_J for J = K/16; if P(T_J > 900K) is not at most 2 exp(-900/128), Lemma 3.5 is false, and the paper predicts this exponential tail uniformly for every proper edge-coloring.
Extended reading notes
Core claim
The paper's main theorem is a counting statement: there is an absolute constant C such that in every proper edge-coloring of K_N, the number of n-vertex subsets whose edges use at most Kn distinct colors is at most $N^{{C(K+\ln n)}}$(CK)^n. This is essentially best possible: over F_2^m, subspaces give $N^{{c\log(Kn)}}$K^n examples, and abelian subgroups show the $N^{{CK}}$ factor is needed. From it, the authors derive that the uniform (and fixed-p) random Cayley graph on any group of order N has clique number O(\log N \log\log N) with high probability, a bound that is tight up to the constant for groups such as F_2^n. They then use the same counting input to prove Alon's conjecture for abelian groups of almost all orders and to construct self-complementary Cayley graphs on vector spaces with characteristic 1 modulo 4 whose clique and independence numbers are both at most (2+o(1))\log_2 N.
Load-bearing premise
The load-bearing premise is that the random color-exposure process reaches a component seeing a constant fraction of all colors within O(K) steps with probability exponentially close to one; if that tail estimate fails, the improved counting bound and the O(log N log log N) clique bound fall apart.
Editorial extensions
If this is right
- The random Cayley graph on any group of order N has clique number O(\log N \log\log N) with high probability, and for groups such as F_2^n this is best possible up to the constant.
- The counting theorem transfers, via Vizing's theorem, to all locally bounded edge-colorings, so random entangled graphs coming from such colorings have the same clique-number bound.
- Any subset A of a group with |AA^{-1}| \le K|A| satisfies d^*(A) = O(K \log n); in abelian groups this improves to O(K \log\log n + \log n), or O(K \log r + \log n) when the group has exponent r.
- Alon's conjecture holds for abelian groups of almost all orders, and for vector spaces of characteristic at least 5 there are Cayley graphs with clique and independence numbers at most (2+o(1))\log_2 N.
- For vector spaces of characteristic congruent to 1 modulo 4, self-complementary Cayley graphs achieve clique and independence numbers at most (2+o(1))\log_2 N, resolving the Alon--Orlitsky problem.
Reading between the lines
- Because every locally bounded coloring decomposes into O(\Delta) proper colorings, the counting theorem should transfer to any graph family whose edge dependencies are bounded-degree matchings; random Latin-square graphs are a natural test case, and the paper already notes the independence-number half follows.
- The explicit self-complementary Ramsey Cayley graphs provide a test bed for information-theoretic savings in repeated dual-source coding; computing their independence numbers in small vector spaces would show how quickly the (2+o(1)) log N bounds kick in.
- The two-phase growth argument is group-free, so the clique-number bound for random entangled graphs may extend to other dependent random graph models; a natural conjecture is that any model where each edge is independent except within bounded-degree neighborhoods inherits the O(\log N \log\log N) bound.
- The difference-set Freiman-dimension bound has the right constant-one exponent of N to serve as a template for counting low-doubling sets in vector spaces beyond the Ramsey application in this paper.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves that a random Cayley graph on any group of order N has clique number O(log N log log N) with high probability, improving Alon's earlier O(log^2 N) bound. The main technical engine is a purely combinatorial counting theorem (Theorem 1.4): in any proper edge-coloring of K_N, the number of n-vertex subsets spanning at most Kn colors is at most N^{C(K+ln n)}(CK)^n. A weak version of this bound is proved first and already yields the random Cayley graph clique-number theorem. The full counting theorem is proved through a random color-exposure process, a tail bound for a stopping time (Lemma 3.5), and a counting argument based on 'efficiently colored trees'. The paper also applies the counting results to Alon's conjecture on Ramsey Cayley graphs, proving it for many abelian groups, and to the construction of (self-complementary) Ramsey Cayley graphs over finite vector spaces, including a claimed (2+o(1)) log N bound.
Significance. If correct, the main clique-number result is a substantial improvement over the previous general bound and is tight up to constants for groups such as F_2^n. Theorem 1.4 is an essentially best-possible counting statement in a proper edge-coloring and is likely to have further applications. The Ramsey Cayley graph results, especially the self-complementary construction, resolve a strong form of the Alon--Orlitsky problem for an infinite family of groups. The proofs of the central counting theorem and the random entangled graph application are detailed and appear sound; in particular, the stress-test concern about Lemma 3.5 does not, on my reading, land. However, several statements in Section 4 are not fully proved, and one theorem there is false as stated, so the manuscript needs revision.
major comments (3)
- [§4.5, Theorem 4.10] Theorem 4.10 is false as stated for non-integer K. For A={0,1} in F_3, we have |A-A|=3 and |A|=2, so K=3/2 satisfies |A-A|≤K|A|, but |<A>|/|A|=3/2, which is larger than p^K/(K+2)=3^{3/2}/3.5≈1.4846. The proof fails at the inequality (z+1)/(p^z(K-z+2))≤1/(K+2), which is false for p=3, K=3/2, z=1/2. Since Theorem 4.10 is used to bound the Freiman dimension in the proof of Lemma 4.9, the proof of Lemma 4.9 is invalid as written. This does not affect Theorems 1.1 or 1.4, and the weaker bound |<A>|/|A|≤p^K appears to follow from the same argument and would suffice for Lemma 4.9, but the statement and proof must be corrected.
- [§4.4, Theorem 4.8] Theorem 4.8, which implies Theorem 1.13, is a headline result, but its proof is not supplied: the text says only that it 'goes through essentially the same' as Theorem 4.7 'with the analogous estimates substituted'. The rotational coloring requires a genuinely different probability estimate (the multinomial coefficient ratio Q_I and the r^{-(1+o(1))|A-A|/2} bound) and a different doubling lower bound |A-A|≥|A|(log|A|)^2. The preceding paragraphs give a useful sketch, but the final estimates and the choice of ℓ need to be written out and checked.
- [§3.3, Corollary 3.10] Corollary 3.10 is stated with its proof explicitly omitted. This corollary is load-bearing: together with Vizing's theorem it yields Corollary 3.11 / Theorem 1.2, which is used throughout Section 4. The missing proof is probably a straightforward adaptation of Theorem 2.2, but it should be included rather than left as an exercise.
minor comments (5)
- [Title] The title has a spacing typo: 'related topi cs' should be 'related topics'.
- [§3.3, proof of Theorem 3.8] The proof assumes n is sufficiently large, since Lemma 3.7 constructs 900K colors and this requires the color set of the n-vertex set to be large enough (roughly n≥450). For bounded n the claimed bound is trivial after enlarging C, but this should be stated explicitly.
- [§3.5, Claim 3.16] In the proof of Claim 3.16, the line 'Let C_{i-1}=C_{i-1}B(L-i)^2∩G_0' uses the same symbol on both sides; this makes the inductive definition of C_i hard to follow and should be clarified, for example by introducing a new symbol for the enlarged set.
- [§4.4, paragraph after the probability estimates] The sentence 'any A of size (2+o(1) log_r n which has a positive probability...' is missing a closing parenthesis and should presumably say log_r N rather than log_r n.
- [§4.5, proof of Theorem 4.10] The tightness discussion after Theorem 4.10 uses K as an integer (adding K elements to a subspace); the theorem statement should clarify whether K is intended to be an integer, since the body and the proof use real K, and the current statement is false for real K.
Circularity Check
No significant circularity: the central counting theorem is proved from an independent random-process lemma and external tools, and the paper's self-references are non-load-bearing.
full rationale
I walked the derivation chain from Theorem 1.4 back to its inputs. The main counting result is proved in Section 3 by introducing the random color-exposure process, proving the tail bound Lemma 3.5, deriving the existence of efficiently colored trees (Lemma 3.9), and then enumerating such trees using Otter's tree-counting theorem and the properness of the coloring to identify vertices. None of these inputs states or assumes the desired upper bound on the number of subsets with few colors; the bound is obtained by counting, not by fitting. Theorem 1.2 and Corollary 3.11 are immediate consequences of Theorem 3.8, and the earlier weak bound in Theorem 2.1 is a separate, simpler argument. The Ramsey-Cayley results in Section 4 use Theorem 1.2 together with additive-combinatorial inputs (Plunnecke-Ruzsa, Even-Zohar-Lovett, Green's lemmas), again without assuming the target clique or independence bounds. The only self-references are [15] and [22]; [15] is described as 'a forthcoming paper' on a different random graph model, and [22] is described as subsequent work 'using as input some of the combinatorial ideas behind the proof of Theorem 1.4'. Neither is invoked as a premise of the present proofs, so they are not load-bearing. I found no equation or construction in which a claimed prediction reduces to a fitted parameter or to a self-citation by definition. A possible numerical issue in the supporting Theorem 4.10 would be a correctness concern, not a circularity concern, and does not affect this verdict.
Assumptions & free parameters
free parameters (1)
- auxiliary block length ell in Theorem 4.8 =
o(log N), e.g., log log log log N
assumptions (5)
- standard math Vizing's theorem: every graph of maximum degree Delta has a proper edge-coloring with Delta+1 colors.
- standard math Pluennecke-Ruzsa inequality for finite subsets of abelian groups.
- standard math Otter's enumeration of unlabeled trees: there are at most 3^n unlabeled trees on n vertices.
- standard math Green's Lemmas 11 and 13(i) from [23] on Freiman isomorphism classes and unique determination by a bounded-size subset.
- domain assumption Even-Zohar-Lovett Freiman-Ruzsa machinery over finite fields, including the compression method and structure of *-compressed sets.
Cite this review
Pith. "Pith review of On the clique number of random Cayley graphs and related topics." pith.science (2026). https://pith.science/paper/ZCU4A756
@misc{pith2026241221194,
author = {Pith},
title = {Pith review of: On the clique number of random Cayley graphs and related topics},
year = {2026},
howpublished = {\url{https://pith.science/paper/ZCU4A756}},
note = {Machine review of arXiv:2412.21194}
}
abstract
We prove that a random Cayley graph on a group of order $N$ has clique number $O(\log N \log \log N)$ with high probability. This bound is best possible up to the constant factor for certain groups, including~$\mathbb{F}_2^n$, and improves the longstanding upper bound of $O(\log^2 N)$ due to Alon. Our proof does not make use of the underlying group structure and is purely combinatorial, with the key result being an essentially best possible upper bound for the number of subsets of given order that contain at most a given number of colors in a properly edge-colored complete graph. As a further application of this result, we study a conjecture of Alon stating that every group of order $N$ has a Cayley graph whose clique number and independence number are both $O(\log N)$, proving the conjecture for all abelian groups of order $N$ for almost all $N$. For finite vector spaces of order $N$ with characteristic congruent to $1 \pmod 4$, we prove the existence of a self-complementary Cayley graph on the vector space whose clique number and independence number are both at most $(2+o(1))\log N$. This matches the lower bound for Ramsey numbers coming from random graphs and solves, in a strong form, a problem of Alon and Orlitsky motivated by information theory.
Forward citations
Cited by 1 Pith paper
-
The VC-dimension of random subsets of finite groups
A random Bernoulli subset of any finite group of order N has VC-dimension (1+o(1)) log_r N with high probability, where r = 1/min(p,1-p).
Reference graph
Works this paper leans on
-
[1]
P. K. Agarwal, N. Alon, B. Aronov and S. Suri, Can visibili ty graphs be represented compactly?, Discrete Comput. Geom. 12 (1994), 347–365. 1.1
work page 1994
-
[2]
Alon, Research problems, Discrete Math
N. Alon, Research problems, Discrete Math. 138 (1995), 405–411. 1, 1.1, 1.2
work page 1995
-
[3]
Alon, Graph powers, in Contemporary combinatorics, 1 1–28, Bolyai Soc
N. Alon, Graph powers, in Contemporary combinatorics, 1 1–28, Bolyai Soc. Math. Stud., 10, János Bolyai Math. Soc., Budapest, 2002. 1.2
work page 2002
-
[4]
N. Alon, Ramsey properties of Cayley graphs, Open proble m garden, available at http://www.openproblemgarden.org/op/ramsey_properties_of_cayley_graphs. 1.2
-
[5]
Alon, The chromatic number of random Cayley graphs, European J
N. Alon, The chromatic number of random Cayley graphs, European J. Combin. 34 (2013), 1232–1243. 1.1
work page 2013
-
[6]
N. Alon, M. Bucić, L. Sauermann, D. Zakharov and O. Zamir, Essentially tight bounds for rainbow cycles in proper edge-colourings, preprint available at ar Xiv:2309.04460 [math.CO]. 1.1
-
[7]
N. Alon and A. Orlitsky, Repeated communication and Rams ey graphs, IEEE Trans. Inform. Theory 41 (1995), 1276–1289. 1, 1.1, 1.2, 1.2, 4, 4.1
work page 1995
-
[8]
B. Bollobás and P. Erdős, Cliques in random graphs, Math. Proc. Cambridge Philos. Soc. 80 (1976), 419–427. 1
work page 1976
Show all 35 references
-
[9]
Campos, On the number of sets with a given doubling cons tant, Israel J
M. Campos, On the number of sets with a given doubling cons tant, Israel J. Math. 236 (2020), 711–726. 1.1
2020
-
[10]
Campos, M
M. Campos, M. Collares, R. Morris, N. Morrison and V. Sou za, The typical structure of sets with small sumset, Int. Math. Res. Not. IMRN (2022), 11011–11055. 1.1
2022
-
[11]
Campos, M
M. Campos, M. Coulson, O. Serra and M. Wötzel, The typica l approximate structure of sets with bounded sumset, SIAM J. Discrete Math. 37 (2023), 1386–1418. 1.1
2023
-
[12]
Campos, S
M. Campos, S. Griffiths, R. Morris and J. Sahasrabudhe, An exponential improvement for diagonal Ramsey, preprint available at arxiv:2303.09521 [math.CO] . 1
-
[13]
Chattopadhyay and J.-J
E. Chattopadhyay and J.-J. Liao, Extractors for sum of t wo sources, in STOC ’22 — Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computin g, 1584–1597, Association for Computing Machinery (ACM), New York, 2022. 5 32
2022
-
[14]
Christofides and K
D. Christofides and K. Markström, Random Latin square gr aphs, Random Structures Algorithms 41 (2012), 47–65. 1.1, 5
2012
-
[15]
Conlon, J
D. Conlon, J. Fox, H. T. Pham and L. Yepremyan, Independe nce in random graph models, in prepara- tion. 5
-
[16]
Erdős, Some remarks on the theory of graphs, Bull
P. Erdős, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292–294. 1
1947
-
[17]
Erdős, A
P. Erdős, A. Hajnal and R. Rado, Partition relations for cardinal numbers, Acta Math. Acad. Sci. Hungar. 16 (1965), 93–196. 4.4
1965
-
[18]
Erdős and G
P. Erdős and G. Szekeres, A combinatorial problem in geo metry, Compos. Math. 2 (1935), 463–470. 1
1935
-
[19]
Erdős and A
P. Erdős and A. Szemerédi, On a Ramsey type theorem, Period. Math. Hungar. 2 (1972), 295–299. 4.4
1972
-
[20]
Even-Zohar, On sums of generating sets in Zn 2 , Combin
C. Even-Zohar, On sums of generating sets in Zn 2 , Combin. Probab. Comput. 21 (2012), 916–941. 4.5
2012
-
[21]
Even-Zohar and S
C. Even-Zohar and S. Lovett, The Freiman–Ruzsa theorem over finite fields, J. Combin. Theory Ser. A 125 (2014), 333–341. 1.2, 4, 4.5, 4.5, 4.5
2014
-
[22]
Fox and H
J. Fox and H. T. Pham, Ruzsa’s conjecture and random Cayl ey graphs, in preparation. 1.1
-
[23]
Green, Counting sets with small sumset, and the cliqu e number of random Cayley graphs, Combi- natorica 25 (2005), 307–326
B. Green, Counting sets with small sumset, and the cliqu e number of random Cayley graphs, Combi- natorica 25 (2005), 307–326. 1, 1.1, 1.1, 1.2, 4.5
2005
-
[24]
Green and R
B. Green and R. Morris, Counting sets with small sumset a nd applications, Combinatorica 36 (2016), 129–159. 1, 1.1, 1.1
2016
-
[25]
S. V. Konyagin and I. D. Shkredov, On subgraphs of random Cayley sum graphs, European J. Combin. 70 (2018), 61–74. 5
2018
-
[26]
D. Liu, L. Mattos, and T. Szabó, On the number of sets with small sumset, preprint available at arXiv:2407.04492 [math.CO]
-
[27]
D. W. Matula, The largest clique size in a random graph, T echnical report CS 7608, Southern Methodist University, Dallas, TX, 1976. 1
1976
-
[28]
McDiarmid and A
C. McDiarmid and A. Steger, Tidier Examples for Lower Bo unds on Diagonal Ramsey Numbers, J. Combin. Theory Ser. A 74 (1996), 147–152. 1.2
1996
-
[29]
Mrazović, One-point concentration of the clique and chromatic numbers of the random Cayley graph on Fn 2 , SIAM J
R. Mrazović, One-point concentration of the clique and chromatic numbers of the random Cayley graph on Fn 2 , SIAM J. Discrete Math. 31 (2017), 143–154. 1.1
2017
-
[30]
Otter, The number of trees, Ann
R. Otter, The number of trees, Ann. Math. 49 (1948), 583–599. 2
1948
-
[31]
I. Z. Ruzsa, An analog of Freiman’s theorem in groups, Astérisque (1999), no. 258, xv, 323–326. 1.1, 4.5
1999
-
[32]
Sanders, On a theorem of Shkredov, Online J
T. Sanders, On a theorem of Shkredov, Online J. Anal. Comb. 5 (2010), 4 pp. 1.1
2010
-
[33]
Sanders, Bootstrapping partition regularity of lin ear systems, Proc
T. Sanders, Bootstrapping partition regularity of lin ear systems, Proc. Edinb. Math. Soc. 63 (2020), 630–653. 5
2020
-
[34]
Schoen and I
T. Schoen and I. D. Shkredov, Additive dimension and a th eorem of Sanders, J. Aust. Math. Soc. 100 (2016), 124–144. 1.1
2016
-
[35]
V. G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964), 25–30. 2 33
1964
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.