pith. sign in

arxiv: 1907.05971 · v1 · pith:JIXDVK3Rnew · submitted 2019-07-12 · 🧮 math.CO · cs.IT· math.IT· math.NT

Linear programming bounds for cliques in Paley graphs

Mark Magsino , Dustin G. Mixon , Hans Parshall This is my paper

Pith reviewed 2026-05-24 22:04 UTC · model grok-4.3

classification 🧮 math.CO cs.ITmath.ITmath.NT
keywords Paley graphsclique numberLovász thetalinear programming boundsSchrijver nonnegativityHanson-Petridis boundvertex-transitive graphs
0
0 comments X

The pith

A linear program from the Lovász theta bound on local graphs rivals the best closed-form bound on cliques in Paley graphs.

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

Paley graphs are vertex-transitive, so the Lovász theta semidefinite program for the clique number can be applied to the local graph at any vertex instead of the full graph. Because the local graphs are circulant, the semidefinite program reduces to a linear program that admits fast computation. With Schrijver's nonnegativity constraint added, the resulting linear program produces upper bounds that rival the closed-form bound of Hanson and Petridis. The authors conjecture that the linear programming bound is strictly tighter than the closed-form bound for infinitely many Paley graphs and derive the dual linear program to support future proofs of the conjecture.

Core claim

For Paley graphs the Lovász theta number applied to the local graph reduces to a linear program whose optimum, when strengthened by Schrijver's nonnegativity constraint, rivals the Hanson-Petridis closed-form bound on the clique number, and the authors conjecture that the linear programming bound improves on it infinitely often.

What carries the argument

The linear program obtained by reducing the Lovász theta semidefinite program on the circulant local graph of a Paley graph, together with Schrijver's nonnegativity constraint.

If this is right

  • The bound admits rapid numerical evaluation for Paley graphs of large order due to circulant symmetry.
  • The dual linear program can be used to certify bound values or to attempt proofs that the bound improves on the closed-form expression infinitely often.
  • The same reduction from semidefinite to linear programming applies to any vertex-transitive graph whose local graph is circulant.

Where Pith is reading between the lines

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

  • The same local-graph reduction may produce competitive linear programming bounds for clique or independence numbers in other families of strongly regular graphs.
  • Numerical values from the linear program could be used to test whether the actual clique number of specific Paley graphs meets the new bound.
  • If the conjecture holds, the linear programming approach would give asymptotically tighter control on the growth of clique sizes in Paley graphs than the closed-form expression alone.

Load-bearing premise

That the clique number of a vertex-transitive graph is controlled by the clique number of its local graph at any vertex.

What would settle it

A specific Paley graph for which the optimum of the linear program exceeds the Hanson-Petridis value.

Figures

Figures reproduced from arXiv: 1907.05971 by Dustin G. Mixon, Hans Parshall, Mark Magsino.

Figure 1
Figure 1. Figure 1: Comparison of LS(p) and HP(p) for the 211 primes p ≡ 1 (mod 4) with p < 3000. For 60 such primes, LS(p) ≤ HP(p). For 17 such primes, LS(p) < bHP(p)c. (left) The blue points (p, LS(p)) appear to concentrate around the red curve y = HP(p). (right) If a point (p, LS(p) − HP(p)) lies below the red curve y = bHP(p)c − HP(p), then LS(p) < bHP(p)c, in which case we plot the point as a circle. Proposition 2. Let G… view at source ↗
read the original abstract

The Lov\'{a}sz theta number is a semidefinite programming bound on the clique number of (the complement of) a given graph. Given a vertex-transitive graph, every vertex belongs to a maximal clique, and so one can instead apply this semidefinite programming bound to the local graph. In the case of the Paley graph, the local graph is circulant, and so this bound reduces to a linear programming bound, allowing for fast computations. Impressively, the value of this program with Schrijver's nonnegativity constraint rivals the state-of-the-art closed-form bound recently proved by Hanson and Petridis. We conjecture that this linear programming bound improves on the Hanson-Petridis bound infinitely often, and we derive the dual program to facilitate proving this conjecture.

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.

Referee Report

0 major / 2 minor

Summary. The manuscript shows that for vertex-transitive Paley graphs the Lovász theta SDP applied to the local graph reduces to a linear program via circulant symmetry; adding Schrijver nonnegativity constraints yields an LP bound that numerically rivals the closed-form Hanson-Petridis bound. The authors conjecture that the LP bound is strictly better for infinitely many Paley graphs and derive the dual LP to support future analytic comparison.

Significance. If the conjecture holds, the work supplies a practical, symmetry-reduced LP that can improve on the best known analytic bound for an infinite family of graphs central to extremal graph theory and finite fields. Explicit provision of the dual is a concrete strength that facilitates non-numerical verification.

minor comments (2)
  1. The introduction should explicitly record the number of distinct prime-power orders q for which numerical comparisons are performed and the range of q examined.
  2. A short table collecting the LP value, Hanson-Petridis value, and their difference for each computed q would improve readability of the rivalry claim.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, assessment of significance, and recommendation to accept the manuscript. There are no major comments to address.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper applies the Lovász theta SDP to the local graph of a vertex-transitive Paley graph and reduces it to an LP via circulant symmetry; this is a standard, externally valid reduction with no self-referential definition or fitted input. The central claim is a numerical comparison to the external Hanson-Petridis closed-form bound together with an explicit conjecture of infinite improvement; the dual LP is supplied to support future analytic work. Schrijver nonnegativity is invoked as a known tightening. No load-bearing step reduces by construction to a self-citation, ansatz smuggled via citation, or renaming of a known result. The derivation remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard properties of vertex-transitive graphs and the fact that Paley graphs are circulant; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption Every vertex in a vertex-transitive graph belongs to a maximal clique
    Invoked to justify applying the bound to the local graph instead of the full graph.
  • domain assumption The local graph of a Paley graph is circulant
    Used to reduce the semidefinite program to a linear program.

pith-pipeline@v0.9.0 · 5669 in / 1368 out tokens · 82427 ms · 2026-05-24T22:04:59.471145+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages · 1 internal anchor

  1. [1]

    Quasi-random graphs,

    Chung, F. R. K., Graham, R. L., and Wilson, R. M., “Quasi-random graphs,” Combinatorica 9(4), 345–362 (1989)

    work page 1989

  2. [2]

    73 of Cambridge Studies in Advanced Mathematics , Cambridge Univer- sity Press, Cambridge, second ed

    Bollob´ as, B., [Random graphs], vol. 73 of Cambridge Studies in Advanced Mathematics , Cambridge Univer- sity Press, Cambridge, second ed. (2001)

    work page 2001

  3. [3]

    Grassmannian frames with applications to coding and communication,

    Strohmer, T. and Heath Jr, R. W., “Grassmannian frames with applications to coding and communication,” Applied and computational harmonic analysis 14(3), 257–275 (2003)

    work page 2003

  4. [4]

    Equiangular tight frames from Paley tournaments,

    Renes, J. M., “Equiangular tight frames from Paley tournaments,” Linear Algebra and its Applica- tions 426(2-3), 497–501 (2007)

    work page 2007

  5. [5]

    On the construction of equiangular frames from graphs,

    Waldron, S., “On the construction of equiangular frames from graphs,” Linear Algebra and its applica- tions 431(11), 2228–2242 (2009)

    work page 2009

  6. [6]

    The road to deterministic matrices with the restricted isometry property,

    Bandeira, A. S., Fickus, M., Mixon, D. G., and Wong, P., “The road to deterministic matrices with the restricted isometry property,” Journal of Fourier Analysis and Applications 19(6), 1123–1149 (2013)

    work page 2013

  7. [7]

    A conditional construction of restricted isometries,

    Bandeira, A. S., Mixon, D. G., and Moreira, J., “A conditional construction of restricted isometries,” International Mathematics Research Notices 2017(2), 372–381 (2017)

    work page 2017

  8. [8]

    Clique numbers of Paley graphs,

    Cohen, S. D., “Clique numbers of Paley graphs,” Quaestiones Math. 11(2), 225–231 (1988)

    work page 1988

  9. [9]

    A combinatorial problem in geometry,

    Erd˝ os, P. and Szekeres, G., “A combinatorial problem in geometry,” Compositio Math. 2, 463–470 (1935)

    work page 1935

  10. [10]

    Lower bounds for least quadratic nonresidues,

    Graham, S. W. and Ringrose, C. J., “Lower bounds for least quadratic nonresidues,” in [ Analytic number theory (Allerton Park, IL, 1989) ], Progr. Math. 85, 269–309, Birkh¨ auser Boston, Boston, MA (1990)

    work page 1989

  11. [11]

    Refined estimates concerning sumsets contained in the roots of unity,

    Hanson, B. and Petridis, G., “Refined estimates concerning sumsets contained in the roots of unity,” arXiv:1905.09134 (2019)

    work page arXiv 1905

  12. [12]

    Some colouring problems for Paley graphs,

    Maistrelli, E. and Penman, D. B., “Some colouring problems for Paley graphs,” Discrete Math. 306(1), 99–106 (2006)

    work page 2006

  13. [13]

    Squares and difference sets in finite fields,

    Bachoc, C., Matolcsi, M., and Ruzsa, I. Z., “Squares and difference sets in finite fields,” Integers 13, Paper No. A77, 5 (2013)

    work page 2013

  14. [14]

    Lower bounds for small diagonal Ramsey numbers,

    Shearer, J. B., “Lower bounds for small diagonal Ramsey numbers,” J. Combin. Theory Ser. A 42(2), 302–304 (1986)

    work page 1986

  15. [15]

    Independence numbers for Paley graphs

    Exoo, G., “Independence numbers for Paley graphs.” http://isu.indstate.edu/ge/PALEY/index.html

    work page

  16. [16]

    Open question: deterministic UUP matrices

    Tao, T., “Open question: deterministic UUP matrices.” http://terrytao.wordpress.com/2007/07/02/open-question-deterministic-uup-matrices/

    work page 2007

  17. [17]

    Explicit constructions of RIP matrices and related problems,

    Bourgain, J., Dilworth, S., Ford, K., Konyagin, S., Kutzarova, D., et al., “Explicit constructions of RIP matrices and related problems,” Duke Mathematical Journal 159(1), 145–185 (2011)

    work page 2011

  18. [18]

    Explicit matrices with the restricted isometry property: Breaking the square-root bottle- neck,

    Mixon, D. G., “Explicit matrices with the restricted isometry property: Breaking the square-root bottle- neck,” in [Compressed sensing and its applications ], 389–417, Springer (2015)

    work page 2015

  19. [19]

    Kesten-McKay law for random subensembles of Paley equiangular tight frames

    Magsino, M., Mixon, D. G., and Parshall, H., “Kesten–McKay law for random subensembles of Paley equiangular tight frames,” arXiv preprint arXiv:1905.04360 (2019)

    work page internal anchor Pith review Pith/arXiv arXiv 1905

  20. [20]

    On the Shannon capacity of a graph,

    Lov´ asz, L., “On the Shannon capacity of a graph,” IEEE Trans. Inform. Theory 25(1), 1–7 (1979)

    work page 1979

  21. [21]

    A comparison of the Delsarte and Lov´ asz bounds,

    Schrijver, A., “A comparison of the Delsarte and Lov´ asz bounds,” IEEE Trans. Inform. Theory 25(4), 425–429 (1979)

    work page 1979

  22. [22]

    Block-diagonal semidefinite programming hierarchies for 0/1 programming,

    Gvozdenovi´ c, N., Laurent, M., and Vallentin, F., “Block-diagonal semidefinite programming hierarchies for 0/1 programming,” Oper. Res. Lett. 37(1), 27–31 (2009)

    work page 2009

  23. [23]

    A conceptual breakthrough in sphere packing,

    Cohn, H., “A conceptual breakthrough in sphere packing,” Notices Amer. Math. Soc. 64(2), 102–115 (2017)

    work page 2017

  24. [24]

    https://www.sagemath.org

    The Sage Developers, SageMath, the Sage Mathematics Software System (Version 8.7) (2019). https://www.sagemath.org

    work page 2019

  25. [25]

    Fast Fourier optimization: sparsity matters,

    Vanderbei, R. J., “Fast Fourier optimization: sparsity matters,” Math. Program. Comput. 4(1), 53–69 (2012). Table 1. Comparison of ω(Gp) with the upper bounds HP( p), L(p) and LS( p) for the 63 primes p≡ 1 (mod 4) with p < 3000 and⌊HP(p)⌋ ̸= ⌊LS(p)⌋. For the 148 unlisted primes p≡ 1 (mod 4) with p < 3000, we observed ⌊HP(p)⌋ =⌊LS(p)⌋. p ω (Gp) HP( p) L( p...

    work page 2012