A Tur\'an Theorem for Cayley Graphs

Kai Yang; Wei Li

arxiv: 2606.29284 · v1 · pith:K7ZGT332new · submitted 2026-06-28 · 🧮 math.CO

A Tur\'an Theorem for Cayley Graphs

Wei Li , Kai Yang This is my paper

Pith reviewed 2026-06-30 07:49 UTC · model grok-4.3

classification 🧮 math.CO

keywords Cayley graphsTurán numbersextremal graph theorycyclic groupsprime orderpolynomial methodforbidden cliques

0 comments

The pith

For odd prime p the Cayley-Turán number exCay(K_{r+1},Z_p) equals p-1-2⌊p/(r+1)⌋.

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

This paper determines the exact maximum size of a symmetric connection set S in the cyclic group of prime order such that the associated Cayley graph contains no copy of the complete graph K_{r+1}. It reaches the value by pairing an upper bound obtained from a polynomial method with an explicit construction that meets the bound. The formula is stated only for prime order because the underlying algebraic structure is used to make the bound tight. A reader would care because standard Turán theorems do not constrain the edge sets that must be unions of group orbits, so an exact answer in this symmetric setting is uncommon. The note also identifies the structural reason the same closed form fails when the group order is composite.

Core claim

For every odd prime p and every 1≤r≤p-1, exCay(K_{r+1},Z_p) = p-1-2⌊p/(r+1)⌋. The maximum is realized by taking S to be the complement in Z_p imes {0} of the short-difference interval D_0 = {0, ±1, …, ±⌊p/(r+1)⌋}. The proof proceeds by applying a polynomial method over the prime field to obtain a matching upper bound.

What carries the argument

The Cayley-Turán number exCay(F,G), the largest |S| with S=-S such that Cay(G,S) is F-free, bounded via polynomials over the field F_p.

If this is right

The extremal S is always the complement of the short-difference interval D_0.
The closed-form expression holds only for cyclic groups of prime order.
For general finite abelian groups the extremal value deviates from this expression because of proper subgroups.
The polynomial method supplies matching upper and lower bounds when the order is prime.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The dependence on field structure suggests the method may adapt to other additive groups equipped with a suitable polynomial ring.
Direct computation on small composite orders such as Z_9 would quantify how much the extremal size departs from the prime formula.
The interval construction may relate to classical problems on restricted difference sets in additive combinatorics.

Load-bearing premise

The polynomial method produces an exact upper bound precisely when the underlying group has prime order.

What would settle it

An explicit symmetric set S in some Z_p with |S| strictly larger than p-1-2⌊p/(r+1)⌋ such that Cay(Z_p,S) still contains no K_{r+1} would falsify the claimed equality.

read the original abstract

In this note, we give a Tur\'an theorem for Cayley graphs $\Cay(\Z_p,S)$ over prime cyclic groups $\Z_p$. For a graph $F$ and a finite abelian group $G$, define the Cayley--Tur\'an number by \[ \exCay(F,G) = \max\{|S|:S=-S\subseteq G\setminus\{0\},\ \Cay(G,S)\text{ is }F\text{-free}\}. \] Using a polynomial method, we prove that for every odd prime $p$ and every $1\le r\le p-1$, \[ \exCay(K_{r+1},\Z_p) = p-1-2\left\lfloor\frac{p}{r+1}\right\rfloor . \] The extremal construction is the complement of the short-difference interval \[ D_0=\{0,\pm1,\ldots,\pm\lfloor p/(r+1)\rfloor\}. \] We also discuss what changes for general finite abelian groups, showing why the exact prime-cyclic formula does not extend verbatim to composite cyclic groups.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This note gives an exact closed-form for the Cayley-Turán number exCay(K_{r+1}, Z_p) on odd primes via the polynomial method, with a matching construction.

read the letter

The key takeaway is that this paper gives a precise formula for the Cayley-Turán number exCay(K_{r+1}, Z_p) when p is an odd prime. It equals p minus 1 minus twice the floor of p divided by r plus 1. The construction is the Cayley graph whose connection set is everything except the short differences around zero.

This is new because it defines this extremal function for Cayley graphs on abelian groups and then solves it exactly in the prime cyclic case using the polynomial method. The lower bound is straightforward from the construction, and the upper bound comes from the algebraic technique. They also show why the formula breaks for composite orders, which adds some context.

The paper does a good job of providing an exact answer in a setting where such things are hard to come by. The polynomial method is applied cleanly to get the matching bound, and the result is stated clearly with the extremal example.

On the soft spots, the main one is the restriction to prime order groups. They are upfront about this and explain the issue with composites, so it's not a hidden flaw. The proof details aren't in the abstract, but assuming the polynomial method works as described, there doesn't seem to be a load-bearing problem. The scope is quite specific, which is typical for this kind of note but means it won't have broad impact outside the subfield.

This paper is for people who work on extremal graph theory with group structures or who use algebraic methods like polynomials in combinatorics. A reader looking for exact results in structured Turán problems would find it useful.

It shows clear thinking in setting up the problem and solving it for this case. I think it deserves a serious referee because the claim is specific and the approach is reasonable.

Recommendation: Yes, send it to peer review rather than desk reject.

Referee Report

0 major / 2 minor

Summary. The paper claims to prove, via a polynomial method, that for every odd prime p and every 1 ≤ r ≤ p-1 the Cayley-Turán number satisfies exCay(K_{r+1}, Z_p) = p-1 - 2⌊p/(r+1)⌋ exactly, with the extremal connection set being the complement of the short-difference interval D_0 = {0, ±1, …, ±⌊p/(r+1)⌋}. It also explains why the same closed-form expression fails to hold for composite-order cyclic groups.

Significance. If the derivation is correct, the manuscript supplies an exact extremal value together with a matching construction for clique-free Cayley graphs on prime-order cyclic groups. Exact Turán numbers of this form are uncommon; the explicit use of the polynomial method to obtain the matching upper bound and the clarification of the prime-order restriction are concrete strengths.

minor comments (2)

[Abstract] The definition of exCay(F,G) is given in the abstract; verify that the same notation is used without redefinition in the body.
The short-difference interval D_0 is described explicitly; a small diagram or explicit listing for a small prime (e.g., p=7, r=2) would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive report, the assessment of significance, and the recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained via polynomial method

full rationale

The paper defines exCay(F,G) explicitly, states an explicit construction (complement of short-difference interval D0), and claims to prove the matching upper bound for prime-order cyclic groups via the polynomial method. The abstract notes the formula's failure for composites, confirming the argument is specialized rather than tautological. No self-citations, fitted parameters renamed as predictions, or reductions of the central equality to its own inputs appear in the provided derivation outline. The result is therefore independent of the inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters or invented entities are apparent from the abstract. The result depends on standard mathematical axioms and the applicability of the polynomial method to this problem.

pith-pipeline@v0.9.1-grok · 5719 in / 1079 out tokens · 44868 ms · 2026-06-30T07:49:05.246247+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

14 extracted references · 2 canonical work pages · 2 internal anchors

[1]

Additive Combinatorics: A Menu of Research Problems

B. Bajnok,Additive combinatorics: a menu of research problems, arXiv:1705.07444, 2017

work page internal anchor Pith review Pith/arXiv arXiv 2017
[2]

Biggs,Algebraic Graph Theory, 2nd ed., Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1993

N. Biggs,Algebraic Graph Theory, 2nd ed., Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1993

1993
[3]

Bollob´ as,Modern Graph Theory, Graduate Texts in Mathematics 184, Springer, New York, 1998

B. Bollob´ as,Modern Graph Theory, Graduate Texts in Mathematics 184, Springer, New York, 1998

1998
[4]

Cashman and K

C. Cashman and K. Kelley, Tur´ an problems for Cayley graphs onZp, PCMI lecture slides, 2025. Available at https://www.ias.edu/sites/default/files/Cashman_Kelley.pdf

2025
[5]

F. J. Dyson, Statistical theory of the energy levels of complex systems. I,Journal of Mathematical Physics3 (1962), 140–156

1962
[6]

Erd˝ os and A

P. Erd˝ os and A. H. Stone, On the structure of linear graphs,Bulletin of the American Mathematical Society52 (1946), 1087–1091

1946
[7]

Godsil and G

C. Godsil and G. Royle,Algebraic Graph Theory, Graduate Texts in Mathematics 207, Springer, New York, 2001

2001
[8]

I. J. Good, Short proof of a conjecture by Dyson,Journal of Mathematical Physics11 (1970), 1884

1970
[9]

Odd cycles in symmetric Cayley graphs on prime cyclic groups

W. Li and K. Yang, Odd cycles in symmetric Cayley graphs on prime cyclic groups,arXiv preprint arXiv:2606.24426, 2026

work page internal anchor Pith review Pith/arXiv arXiv 2026
[10]

Mantel, Problem 28,Wiskundige Opgaven10 (1907), 60–61

W. Mantel, Problem 28,Wiskundige Opgaven10 (1907), 60–61

1907
[11]

Simonovits, A method for solving extremal problems in graph theory, stability problems, inTheory of Graphs (Proc

M. Simonovits, A method for solving extremal problems in graph theory, stability problems, inTheory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, pp. 279–319

1966
[12]

Tao and V

T. Tao and V. Vu,Additive Combinatorics, Cambridge Studies in Advanced Mathematics 105, Cambridge University Press, 2006

2006
[13]

Tur´ an, On an extremal problem in graph theory,Matematikai ´ es Fizikai Lapok48 (1941), 436–452

P. Tur´ an, On an extremal problem in graph theory,Matematikai ´ es Fizikai Lapok48 (1941), 436–452

1941
[14]

Zeilberger, A combinatorial proof of Dyson’s conjecture,Discrete Mathematics41 (1982), 317–321

D. Zeilberger, A combinatorial proof of Dyson’s conjecture,Discrete Mathematics41 (1982), 317–321. Fujian Agriculture and Forestry University, Fuzhou, Fujian, China Email address:liwei@fafu.edu.cn Fuzhou University, Fuzhou, Fujian, China Email address:443926471@qq.com

1982

[1] [1]

Additive Combinatorics: A Menu of Research Problems

B. Bajnok,Additive combinatorics: a menu of research problems, arXiv:1705.07444, 2017

work page internal anchor Pith review Pith/arXiv arXiv 2017

[2] [2]

Biggs,Algebraic Graph Theory, 2nd ed., Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1993

N. Biggs,Algebraic Graph Theory, 2nd ed., Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1993

1993

[3] [3]

Bollob´ as,Modern Graph Theory, Graduate Texts in Mathematics 184, Springer, New York, 1998

B. Bollob´ as,Modern Graph Theory, Graduate Texts in Mathematics 184, Springer, New York, 1998

1998

[4] [4]

Cashman and K

C. Cashman and K. Kelley, Tur´ an problems for Cayley graphs onZp, PCMI lecture slides, 2025. Available at https://www.ias.edu/sites/default/files/Cashman_Kelley.pdf

2025

[5] [5]

F. J. Dyson, Statistical theory of the energy levels of complex systems. I,Journal of Mathematical Physics3 (1962), 140–156

1962

[6] [6]

Erd˝ os and A

P. Erd˝ os and A. H. Stone, On the structure of linear graphs,Bulletin of the American Mathematical Society52 (1946), 1087–1091

1946

[7] [7]

Godsil and G

C. Godsil and G. Royle,Algebraic Graph Theory, Graduate Texts in Mathematics 207, Springer, New York, 2001

2001

[8] [8]

I. J. Good, Short proof of a conjecture by Dyson,Journal of Mathematical Physics11 (1970), 1884

1970

[9] [9]

Odd cycles in symmetric Cayley graphs on prime cyclic groups

W. Li and K. Yang, Odd cycles in symmetric Cayley graphs on prime cyclic groups,arXiv preprint arXiv:2606.24426, 2026

work page internal anchor Pith review Pith/arXiv arXiv 2026

[10] [10]

Mantel, Problem 28,Wiskundige Opgaven10 (1907), 60–61

W. Mantel, Problem 28,Wiskundige Opgaven10 (1907), 60–61

1907

[11] [11]

Simonovits, A method for solving extremal problems in graph theory, stability problems, inTheory of Graphs (Proc

M. Simonovits, A method for solving extremal problems in graph theory, stability problems, inTheory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, pp. 279–319

1966

[12] [12]

Tao and V

T. Tao and V. Vu,Additive Combinatorics, Cambridge Studies in Advanced Mathematics 105, Cambridge University Press, 2006

2006

[13] [13]

Tur´ an, On an extremal problem in graph theory,Matematikai ´ es Fizikai Lapok48 (1941), 436–452

P. Tur´ an, On an extremal problem in graph theory,Matematikai ´ es Fizikai Lapok48 (1941), 436–452

1941

[14] [14]

Zeilberger, A combinatorial proof of Dyson’s conjecture,Discrete Mathematics41 (1982), 317–321

D. Zeilberger, A combinatorial proof of Dyson’s conjecture,Discrete Mathematics41 (1982), 317–321. Fujian Agriculture and Forestry University, Fuzhou, Fujian, China Email address:liwei@fafu.edu.cn Fuzhou University, Fuzhou, Fujian, China Email address:443926471@qq.com

1982