Coloring sparse random Cayley graphs

Nathan Tung

Coloring sparse random Cayley graphs

T0 review · 0 major / 3 minor · reviewed 2026-06-26 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read There exists c > 0 such that Cayley graphs on any finite abelian group generated by c log |Z| random elements are properly 3-colorable with high probability.

desk verdict The paper improves the bound on generators for 3-coloring random Cayley graphs on abelian groups from (1/4)log log |Z| to c log |Z|, and claims the new bound is tight. read the letter →

arxiv 2606.23762 v1 pith:5LQ63BH5 submitted 2026-06-22 math.CO

Nathan Tung This is my paper · ORCID

classification math.CO

keywords Cayleygraphsrandomgraphcoloringabeliangroupschromaticnumberprobabilisticmethodsparse

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes that random Cayley graphs on finite abelian groups become 3-colorable once the number of generators reaches a logarithmic threshold in the group order. It improves the prior best bound from roughly one-fourth log log |Z| generators to a true logarithmic number while remaining asymptotically tight. The argument relies on the abelian structure to ensure that random choices produce graphs free of 4-chromatic obstructions with high probability. A reader cares because the result gives an explicit, group-independent guarantee on the chromatic number of these sparse random graphs and narrows the gap toward similar bounds on solvable groups.

What carries the argument

The random Cayley graph on an abelian group Z, whose edges are determined by a set of c log |Z| independently chosen uniform random generators, together with a probabilistic argument that uses commutativity to bound the appearance of odd wheels or other 4-chromatic substructures.

What would settle it

An explicit finite abelian group Z together with a set of c log |Z| random generators for which the resulting Cayley graph contains a 4-chromatic subgraph with probability bounded away from zero.

Watch

Extended reading notes

Core claim

The central claim is that there exists c > 0 so that the Cayley graph over any finite abelian group Z generated by c log |Z| random elements is properly 3-colorable with high probability as |Z| tends to infinity. This bound is asymptotically tight and improves the previous result of (1/4) log log |Z| generators.

Load-bearing premise

The generators are chosen independently and uniformly at random and the group is abelian so that the probabilistic control over colorings and independent sets remains valid.

Editorial extensions

If this is right

The chromatic number of these random Cayley graphs is at most 3 with high probability.
The logarithmic number of generators is asymptotically optimal for the 3-colorability statement.
The same logarithmic threshold advances the open question of whether c log |G| generators suffice for 3-colorability on every finite solvable group.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same random-generator construction might yield bounded chromatic number for other sparse graph families on groups if the abelian assumption can be relaxed.
One could test whether the constant c can be made explicit by tracking the failure probabilities in the probabilistic deletion step.
The result suggests that connectivity and expansion properties of these graphs coexist with 3-colorability once the generator count exceeds the connectivity threshold.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

read the letter

The main result is that for any finite abelian group Z there exists c > 0 such that a random Cayley graph generated by c log |Z| elements is 3-colorable with high probability as |Z| grows. This is the punchline and it is a quantitative step forward from the Alon bound cited in the abstract.

The work is new in reaching the logarithmic scale specifically for abelian groups, which matches the form Alon suggested might hold more generally for solvable groups. The abelian assumption is used to manage differences and independence properties in the probabilistic argument, and the claim is presented as asymptotically tight.

The derivation steps cannot be checked from the abstract alone, but the stress-test found no internal inconsistency or uniformity failure across groups. The random choice of generators is standard and the improvement over the prior log-log bound is real if the proof holds.

Soft spots are limited. The constant c is existential only, and the exact way the argument bypasses the earlier barrier is not visible without the manuscript. The tightness assertion needs to rest on a matching lower bound that is either cited or proved here; if that part is thin it would be the main thing to check in review.

This paper is for people working on random Cayley graphs, group coloring, or probabilistic combinatorics in algebra. A reader following questions about solvable groups or explicit bounds on generators would get direct value from the improved threshold.

It deserves a serious referee because the advance is concrete, the setting is well-defined, and the result sits on top of an existing open suggestion rather than inventing new machinery.

Referee Report

0 major / 3 minor

Summary. The paper proves that there exists c > 0 such that for any finite abelian group Z, the random Cayley graph Cay(Z, S) with |S| = c log |Z| generators chosen independently and uniformly at random is properly 3-colorable with high probability as |Z| → ∞. The result is asymptotically tight (matching the lower bound from the independence number) and improves Alon's explicit bound of (1/4) log log |Z|. The abelian structure is used to control differences and independence properties in the probabilistic argument.

Significance. If the proof holds, the result is a meaningful advance on the chromatic number of sparse random Cayley graphs. It closes most of the gap between the trivial O(log |Z|) upper bound and the logarithmic lower bound for abelian groups, and supplies the first constant-factor improvement over Alon's 1990s bound. The argument may extend to solvable groups as suggested by Alon.

minor comments (3)

The abstract states the result for 'any finite abelian group Z' but the introduction should explicitly note whether the constant c is uniform across all abelian groups or may depend on the exponent or rank.
Section 2 (or the probabilistic-method section) should clarify how the union bound over all potential colorings or independent sets is closed when |S| = c log |Z|; the error term controlling the probability that a fixed 3-coloring fails should be stated explicitly.
The comparison with Alon's bound appears only in the abstract; a short paragraph in the introduction or §1.2 should recall the precise statement of Alon's theorem for context.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment and recommendation to accept the manuscript. Their summary accurately captures the main contribution: a constant-factor improvement over Alon's bound for 3-colorability of random Cayley graphs on abelian groups.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified

full rationale

The paper presents a probabilistic existence proof establishing a constant c such that random Cayley graphs on finite abelian groups with c log |Z| generators are 3-colorable whp. No fitted parameters, self-definitional equations, or load-bearing self-citations appear in the abstract or described argument; the result improves an external bound by Alon and relies on the abelian property for independence control in a direct probabilistic argument. The derivation chain is self-contained as a mathematical proof without reduction to its own inputs by construction.

Assumptions & free parameters 0 free parameters · 0 assumptions · 0 invented entities

Only the abstract is available; no free parameters, axioms, or invented entities are described.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Coloring sparse random Cayley graphs." pith.science (2026). https://pith.science/paper/5LQ63BH5

@misc{pith2026260623762,
  author       = {Pith},
  title        = {Pith review of: Coloring sparse random Cayley graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5LQ63BH5}},
  note         = {Machine review of arXiv:2606.23762}
}

abstract

It is shown that there exists $c > 0$ so that the Cayley graph over any finite abelian group $Z$ generated by $c \log |Z|$ random elements is properly 3-colorable with high probability (as $|Z| \to \infty$). This is asymptotically tight and improves the best-known bound due to Alon of $\frac{1}{4}\log \log |Z|$ elements. It also makes progress toward Alon's suggestion that a bound of $c \log |G|$ may hold for any finite solvable group $G$.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Linear equations and chromatic thresholds in $B_h$ sets
math.CO 2026-06 unverdicted novelty 6.0 of 10

Sparse Roth-type results hold in near-maximal B_h sets; Sidon sets free of equations with five-coefficient zero-sums are small or have bounded-chromatic Cayley graphs, with constructions for the four-coefficient case.

Reference graph

Works this paper leans on

14 extracted references · 4 canonical work pages · cited by 1 Pith paper

[1]

Alon and Y

N. Alon and Y. Peres,Uniform dilations, Geom. Funct. Anal.2(1992), no. 1, 1–28. MR1143662

1992
[2]

Combin.34(2013), no

Noga Alon,The chromatic number of random Cayley graphs, European J. Combin.34(2013), no. 8, 1232–1243. MR3082195

2013
[3]

arXiv:2509.02561

Noga Alon and Huy Tuan Pham,Random Cayley graphs and random sumsets, (2025). arXiv:2509.02561

work page arXiv 2025
[4]

2, 271–284

Noga Alon and Yuval Roichman,Random Cayley graphs and expanders, Random Structures Algorithms 5(1994), no. 2, 271–284. MR1262979

1994
[5]

Randomly piercing algebraic sets

Daniel Altman and Nathan Tung,Randomly piercing algebraic sets, (2026). arXiv:2606.19677

work page Pith review arXiv 2026
[6]

Bourgain,Ruzsa’s problem on sets of recurrence, Israel J

J. Bourgain,Ruzsa’s problem on sets of recurrence, Israel J. Math.59(1987), no. 2, 150–166. MR920079

1987
[7]

Marcelo Campos, Gabriel Dahia, and João Pedro Marciano,On the independence number of sparser random Cayley graphs, J. Lond. Math. Soc. (2)110(2024), no. 6, Paper No. e70041, 54. MR4835287

2024
[8]

arXiv:2412.21194

David Conlon, Jacob Fox, Huy Tuan Pham, and Liana Yepremyan,On the clique number of random Cayley graphs and related topics, (2024). arXiv:2412.21194

work page arXiv 2024

Show all 14 references

[9]

A. M. Frieze,On the independence number of random graphs, Discrete Math.81(1990), no. 2, 171–175. MR1054975

1990
[10]

3, 307–326

Ben Green,Counting sets with small sumset, and the clique number of random Cayley graphs, Combi- natorica25(2005), no. 3, 307–326. MR2141661

2005
[11]

2, 129–159

Ben Green and Robert Morris,Counting sets with small sumset and applications, Combinatorica36 (2016), no. 2, 129–159. MR3516881

2016
[12]

Hoffman,On eigenvalues and colorings of graphs, Graph Theory and its Applications (Proc

Alan J. Hoffman,On eigenvalues and colorings of graphs, Graph Theory and its Applications (Proc. Advanced Sem., Math. Research Center, Univ. of Wisconsin, Madison, Wis., 1969), (1970), pp. 79–91. MR284373

1969
[13]

arXiv:2503.02100

Rajko Nenadov,A remark on the independence number of sparse random Cayley sum graphs, (2025). arXiv:2503.02100

2025
[14]

Stein and Rami Shakarchi,Fourier analysis, Princeton Lectures in Analysis, vol

Elias M. Stein and Rami Shakarchi,Fourier analysis, Princeton Lectures in Analysis, vol. 1, Princeton University Press, Princeton, NJ, (2003). An introduction. MR1970295 Stanford University, CA 94305, USA Email address:ntung@stanford.edu 16

2003

Pith tools

Reviewed June 26, 2026 · model on record in the stance chip above.

[1] [1]

Alon and Y

N. Alon and Y. Peres,Uniform dilations, Geom. Funct. Anal.2(1992), no. 1, 1–28. MR1143662

1992

[2] [2]

Combin.34(2013), no

Noga Alon,The chromatic number of random Cayley graphs, European J. Combin.34(2013), no. 8, 1232–1243. MR3082195

2013

[3] [3]

arXiv:2509.02561

Noga Alon and Huy Tuan Pham,Random Cayley graphs and random sumsets, (2025). arXiv:2509.02561

work page arXiv 2025

[4] [4]

2, 271–284

Noga Alon and Yuval Roichman,Random Cayley graphs and expanders, Random Structures Algorithms 5(1994), no. 2, 271–284. MR1262979

1994

[5] [5]

Randomly piercing algebraic sets

Daniel Altman and Nathan Tung,Randomly piercing algebraic sets, (2026). arXiv:2606.19677

work page Pith review arXiv 2026

[6] [6]

Bourgain,Ruzsa’s problem on sets of recurrence, Israel J

J. Bourgain,Ruzsa’s problem on sets of recurrence, Israel J. Math.59(1987), no. 2, 150–166. MR920079

1987

[7] [7]

Marcelo Campos, Gabriel Dahia, and João Pedro Marciano,On the independence number of sparser random Cayley graphs, J. Lond. Math. Soc. (2)110(2024), no. 6, Paper No. e70041, 54. MR4835287

2024

[8] [8]

arXiv:2412.21194

David Conlon, Jacob Fox, Huy Tuan Pham, and Liana Yepremyan,On the clique number of random Cayley graphs and related topics, (2024). arXiv:2412.21194

work page arXiv 2024