{"id":"281fe4ca-fe9a-4051-8d82-bdce51a13b3a","arxiv_id":"2412.21194","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Random Cayley graphs on any group of order N have clique number O(log N log log N) with high probability, giving near-optimal Ramsey and self-complementary Cayley graphs.","lead":"This paper proves a new upper bound on the largest complete subgraph, the clique, that appears in random Cayley graphs on any group of N elements, improving a decades-old bound. The result also constructs Cayley graphs with both tiny cliques and tiny independent sets, resolving open problems about Ramsey Cayley graphs and a question from information theory.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.10 is false as stated: {0,1} in F_3 gives |A-A|/|A| = 3/2 but |<A>|/|A| = 3/2 > 3^{3/2}/(7/2).","rationale":"I examined the reader's flagged weak point, Lemma 3.5 and the random color-growth process in Section 3.2. I did not find a concrete flaw in the tail bound or in the conditional-distribution claim; the argument is intricate but the estimates appear to close. The central counting theorem, Theorem 1.4, and its derivation of the O(log N log log N) clique-number bound for random Cayley graphs seem internally sound. However, I found a different, concrete and checkable error: Theorem 4.10 is false as stated, with A = {0,1} in F_3 as an explicit counterexample. The source is a false inequality in the proof. Since Lemma 4.9 is proved using Theorem 4.10, the proof of the Section 4 results on Ramsey Cayley colorings and the (2+o(1)) log N self-complementary construction has a gap as written. The gap appears patchable: the argument actually yields the weaker bound |<A>| <= p^K|A|, which would suffice because the application only needs Freiman dimension at most K + log_p t. I therefore do not change the reader's overall CONDITIONAL verdict, but I disagree with the choice of the single most load-bearing concern: the false statement in Theorem 4.10 is a more concrete issue than the unverified Lemma 3.5.","tokens_in":42332,"tokens_out":51850,"duration_ms":504952,"concrete_test":"Verify the counterexample directly: for A = {0,1} subset of F_3, compute |A-A| = 3, |A| = 2, and |<A>| = 3, so the ratio is 3/2, while the theorem's bound is 3^{3/2}/(7/2) ≈ 1.4846. Also check the proof's inequality at p = 3, K = 3/2, z = 1/2: (z+1)/(p^z(K-z+2)) ≈ 0.2887 > 1/(K+2) ≈ 0.2857. If Lemma 4.9 is repaired by using the weaker bound p^K in place of p^K/(K+2), re-run the summations in Theorems 4.7 and 4.8 to confirm the (2+o(1)) log N exponents still close.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4.5 asserts Theorem 4.10: for every K >= 1 and prime p >= 3, F^-(p,K) <= p^K/(K+2). This is false. Take A = {0,1} in F_3. Then |A-A| = 3, |A| = 2, so K = 3/2 satisfies |A-A| <= K|A|, while the affine span of A is all of F_3, giving |<A>|/|A| = 3/2. The claimed bound is 3^{3/2}/(7/2) = 3*sqrt(3)/3.5 ≈ 1.4846 < 1.5. The failure is not just numerical: in the proof of Theorem 4.10, after setting z = K - n + h, the paper uses (z+1)/[p^z(K-z+2)] <= 1/(K+2) for all p >= 3, K >= 1, z >= 0. For p = 3, K = 3/2, z = 1/2 this inequality fails (LHS ≈ 0.2887, RHS ≈ 0.2857), so the proof has a concrete algebraic gap. Lemma 4.9 is proved by invoking Theorem 4.10 to bound the Freiman dimension; as written, that proof is invalid. This does not directly affect the main counting Theorem 1.4 or the random Cayley clique-number bound, and a weaker bound like |<A>| <= p^K|A| appears to follow from the same argument and would suffice for the asymptotic (2+o(1)) log N results. Still, the current text contains a false theorem in a key supporting role for Section 4.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":42692,"tokens_out":37243,"duration_ms":332368,"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":[{"comment":"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.","section":"§4.5, Theorem 4.10"},{"comment":"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.","section":"§4.4, Theorem 4.8"},{"comment":"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.","section":"§3.3, Corollary 3.10"}],"minor_comments":[{"comment":"The title has a spacing typo: 'related topi cs' should be 'related topics'.","section":"Title"},{"comment":"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.","section":"§3.3, proof of Theorem 3.8"},{"comment":"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.","section":"§3.5, Claim 3.16"},{"comment":"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.","section":"§4.4, paragraph after the probability estimates"},{"comment":"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.","section":"§4.5, proof of Theorem 4.10"}],"recommendation":"major_revision","confidential_remarks":"The central counting theorem and the random Cayley graph application appear to be in good shape, and the paper is likely to make a strong contribution after revision. The main issues are localized to Section 4: a false theorem in §4.5 and an omitted proof of a headline theorem in §4.4. Both seem repairable within the scope of the manuscript, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Core take: Theorem 1.4 is a genuine breakthrough. The bound N^{C(K+ln n)}(CK)^n for the number of n-sets spanning at most Kn colors in a proper edge-coloring is essentially best possible, and the proof via efficiently colored trees is the real meat. It yields the O(log N log log N) clique bound for random Cayley graphs, improving Alon's O(log^2 N) after decades. The additive dimension corollaries are also new and interesting. Credit where due: this is high-level combinatorics, and the central argument in Sections 2–3 appears detailed and sound, though I haven't checked every inequality.\n\nThe soft spot is in Section 4. Theorem 4.10 is false as stated. Take A={0,1} in F_3: |A-A|/|A|=3/2, so K=3/2, but |<A>|/|A|=3/2 > 3^{3/2}/(7/2)≈1.4846. The proof's inequality (z+1)/(p^z(K-z+2)) ≤ 1/(K+2) fails for p=3,K=3/2,z=1/2. Since Lemma 4.9 is proved via Theorem 4.10 to bound Freiman dimension, that proof is invalid as written. This does not affect Theorem 1.4 or Theorem 1.1; and the applications only seem to need a weaker bound like |<A>| ≤ p^K|A|, which their argument likely supplies. Still, a false theorem in a supporting role is a real error, not a cosmetic one. The authors should fix this before acceptance.\n\nTwo smaller issues: Corollary 3.10 is stated with its proof omitted, and Theorem 4.8 is only sketched. Both should be filled in for a complete refereeable version. The citation pattern is clean; the external tools (Vizing, Plünnecke-Ruzsa, Otter, Even-Zohar-Lovett) are used appropriately.\n\nVerdict: this deserves a serious referee. The main theorem is important and likely correct; the Ramsey Cayley applications are plausible but currently rest on a faulty lemma. I'd send it out, with the instruction that the referee focus on the proof of Theorem 4.10/Lemma 4.9 and on the missing details.","headline":"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.","tokens_in":43320,"tokens_out":2239,"would_cite":true,"duration_ms":21413,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C55","05C15","11B30"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["random Cayley graphs","clique number","edge-coloring","counting subsets with few colors","Ramsey graphs","self-complementary graphs","additive dimension","Freiman dimension"],"falsifier":"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.","tokens_in":2094,"feed_emoji":"🎲","tokens_out":2000,"duration_ms":79592,"temperature":0.7,"pith_summary":"The paper establishes an essentially best possible upper bound on the number of n-vertex subsets that span at most Kn colors in any proper edge-coloring of the complete graph K_N, and derives from it a O(log N log log N) upper bound on the clique number of random Cayley graphs on any group of order N, improving Alon's longstanding O($log^{2}$ N) bound. The counting argument is purely combinatorial and does not use the underlying group structure, so it applies more broadly to random entangled graphs coming from locally bounded edge-colorings. The same counting input, supplemented by expansion arguments and a Freiman-dimension estimate for difference sets, proves Alon's conjecture on the existence of C-Ramsey Cayley graphs for abelian groups of almost all orders. For finite vector spaces whose characteristic is congruent to 1 modulo 4, the paper constructs self-complementary Cayley graphs whose clique and independence numbers are both at most (2+o(1)) log_2 N, matching the random-graph lower bound and resolving a problem of Alon and Orlitsky.","feed_headline":"Random Cayley graphs have cliques of size O(log N log log N)","feed_subtitle":"A new counting bound on color-poor subsets breaks Alon's long-standing O(log^2 N) barrier and yields near-optimal Ramsey Cayley graphs.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the O(log^2 N) upper bound that the paper improves and states the Ramsey Cayley conjecture addressed in Section 4.","marker":"[2]"},{"why":"Established the cyclic-group case and contributes the Freiman-isomorphism counting scheme reused in Lemma 4.9.","marker":"[23]"},{"why":"Proved the asymptotically sharp (2+o(1)) log N clique bound for prime cyclic groups, the target the vector-space results match.","marker":"[24]"},{"why":"Provides the Freiman--Ruzsa theorem over finite fields whose difference-set analogue, Theorem 4.10, underpins the Ramsey colorings.","marker":"[21]"},{"why":"Counts unlabeled trees, used to bound the number of efficiently colored trees in the proof of Theorem 1.4.","marker":"[30]"},{"why":"Splits bounded-degree color classes into proper colorings, extending the counting theorem to locally bounded colorings.","marker":"[35]"},{"why":"Gives the abelian additive-dimension bound O(K log n) that Corollary 1.7 generalizes to all groups.","marker":"[32]"},{"why":"Provides the quantitative Freiman--Ruzsa bound in groups that motivates and is used alongside the finite-field version.","marker":"[31]"}],"fun_headline_variants":["Improving Alon: random Cayley cliques O(log N log log N)","Tight bound O(log N log log N) for random Cayley graphs","Counting subsets improves Alon's bound for random Cayley cliques"],"cache_read_input_tokens":45184,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Improving Alon: random Cayley cliques O(log N log log N)","Tight bound O(log N log log N) for random Cayley graphs","Counting subsets improves Alon's bound for random Cayley cliques"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002056,"raw_usage":{"total_tokens":8044,"prompt_tokens":1026,"completion_tokens":7018,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":642,"completion_tokens_details":{"reasoning_tokens":6954}},"tokens_in":642,"tokens_out":7018,"duration_ms":43162,"temperature":1.0,"reasoning_tokens":6954,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T23:00:53.312814+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Alon, Research problems, Discrete Math","cited_arxiv_id":null,"evidence_quote":"Supplies the O(log^2 N) upper bound that the paper improves and states the Ramsey Cayley conjecture addressed in Section 4."},{"cited_title":"Green, Counting sets with small sumset, and the cliqu e number of random Cayley graphs, Combi- natorica 25 (2005), 307–326","cited_arxiv_id":null,"evidence_quote":"Established the cyclic-group case and contributes the Freiman-isomorphism counting scheme reused in Lemma 4.9."},{"cited_title":"Green and R","cited_arxiv_id":null,"evidence_quote":"Proved the asymptotically sharp (2+o(1)) log N clique bound for prime cyclic groups, the target the vector-space results match."},{"cited_title":"Even-Zohar and S","cited_arxiv_id":null,"evidence_quote":"Provides the Freiman--Ruzsa theorem over finite fields whose difference-set analogue, Theorem 4.10, underpins the Ramsey colorings."},{"cited_title":"Otter, The number of trees, Ann","cited_arxiv_id":null,"evidence_quote":"Counts unlabeled trees, used to bound the number of efficiently colored trees in the proof of Theorem 1.4."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Splits bounded-degree color classes into proper colorings, extending the counting theorem to locally bounded colorings."},{"cited_title":"Sanders, On a theorem of Shkredov, Online J","cited_arxiv_id":null,"evidence_quote":"Gives the abelian additive-dimension bound O(K log n) that Corollary 1.7 generalizes to all groups."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the quantitative Freiman--Ruzsa bound in groups that motivates and is used alongside the finite-field version."}],"review_version":1}