pith. sign in

arxiv: 2606.08913 · v1 · pith:EOEF3ML2new · submitted 2026-06-08 · 🧮 math.CO

Sharp Bounds for Guiduli-Type Hereditary Spectral Problems

Dongxiu Cai , Jiasheng Zeng , Xiao-Dong Zhang This is my paper

Pith reviewed 2026-06-27 16:43 UTC · model grok-4.3

classification 🧮 math.CO
keywords spectral radiushereditary densitygraphonGuiduli problemextremal graph theoryasymptotic boundspower-law densities
0
0 comments X

The pith

Every n-vertex graph satisfies a sharp asymptotic bound on its spectral radius in terms of its hereditary p-density d_p(G), with the form depending on whether p is less than, equal to, or greater than 3/2.

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

This paper resolves the power-law version of Guiduli's 1996 question by determining the sharp asymptotic upper bound on the spectral radius λ(G) of an n-vertex graph in terms of d_p(G), the maximum of e(G[S])/|S|^p over nonempty subsets S. The bound takes three forms: order d_p(G) sqrt(n) when 1 < p < 3/2, order d_p(G) sqrt(n log n) when p = 3/2, and order d_p(G) n^{p-1} when 3/2 < p < 2, with each leading constant best possible. The transition at p = 3/2 is explained by the sparse graphon operator estimate used to convert hereditary density constraints into spectral bounds. For the endpoint p = 2, Wilf's theorem supplies the exact finite-n bound λ(G) ≤ 2 d_2(G) n.

Core claim

Every n-vertex graph G with at least one edge satisfies λ(G) ≤ the piecewise expression with cases for 1<p<3/2, p=3/2, and 3/2<p<2, and each constant is best possible. Here C_p is characterized by an exact variational problem over finite kernels. The sparse graphon operator estimate converts hereditary p-density bounds into sharp spectral bounds, and this estimate also explains the transition at the critical exponent p=3/2. For the endpoint p=2, Wilf's theorem gives the exact finite-n bound λ(G) ≤ 2 d_2(G) n, with equality for K_n.

What carries the argument

The sparse graphon operator estimate that converts hereditary p-density bounds into sharp spectral bounds (including the precise transition at the critical exponent p=3/2) without losing the leading term.

If this is right

  • The bound holds with the stated leading constants achieved by specific constructions or finite kernels.
  • Guiduli's original question is resolved in sharp asymptotic form for every 1 < p ≤ 2.
  • The variational characterization supplies the exact constant C_p for each p > 3/2.
  • The case distinctions are required by the change in behavior of the graphon estimate at p = 3/2.

Where Pith is reading between the lines

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

  • The same graphon estimate may yield analogous sharp bounds for other spectral invariants under hereditary constraints.
  • The critical value p = 3/2 could mark a phase transition in other problems that combine density and eigenvalue control.
  • Numerical solution of the variational problem for specific p values would give concrete constants for applications.

Load-bearing premise

The sparse graphon operator estimate converts hereditary p-density bounds into sharp spectral bounds without losing the leading asymptotic term.

What would settle it

A sequence of n-vertex graphs with d_p(G) bounded by a constant but λ(G) exceeding the stated multiple of d_p(G) times the corresponding power of n (for large n) would falsify the bound.

read the original abstract

Guiduli asked in 1996 the following problem concerning the maximum spectral radius of a graph under hereditary density constraints. If an $n$-vertex graph $G$ satisfies $e(H)\le c|V(H)|^2$ for every subgraph $H$ of $G$, must one have $\lambda(G)\le 2cn$? More generally, what remains true when the exponent $2$ is replaced by a constant less than $2$? We study the natural power-law version of this question for all $1<p\le2$. For $1<p\le 2$, define \[ d_p(G)=\max_{\varnothing\ne S\subseteq V(G)}\frac{e(G[S])}{|S|^p}. \] We determine the sharp asymptotic upper bound for $\lambda(G)$ in terms of $d_p(G)$ and $n$. More precisely, every $n$-vertex graph $G$ with at least one edge satisfies \[ \lambda(G)\le \begin{cases} \left(\left(\max_{t\in\mathbb N_{\ge1}}\dfrac{t}{(t+1)^p}\right)^{-1}+o(1)\right)d_p(G)\sqrt n,&1<p<3/2,\\[0.4em] \left(\dfrac{3\sqrt3}{4}+o(1)\right)d_p(G)\sqrt{n\log n},&p=3/2,\\[0.4em] (\mathfrak C_p+o(1))d_p(G)n^{p-1},&3/2<p<2, \end{cases} \] and each constant here is best possible. Here $\mathfrak C_p$ is characterized by an exact variational problem over finite kernels. We apply a sparse graphon operator estimate to convert hereditary $p$-density bounds into sharp spectral bounds, and this estimate also explains the transition at the critical exponent $p=3/2$. For the endpoint $p=2$, Wilf's theorem gives the exact finite-$n$ bound $\lambda(G)\le 2d_2(G)n$, with equality for $K_n$. Thus Guiduli's power-law problem is resolved in its sharp asymptotic form for every $1<p\leq2$, including exact leading constants.

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

2 major / 0 minor

Summary. The paper resolves Guiduli's 1996 question on sharp asymptotic upper bounds for the spectral radius λ(G) of an n-vertex graph G under the hereditary p-density constraint d_p(G), for 1 < p ≤ 2. It establishes the piecewise bound λ(G) ≤ [(max t/(t+1)^p)^{-1} + o(1)] d_p(G) √n for 1 < p < 3/2; (3√3/4 + o(1)) d_p(G) √(n log n) for p = 3/2; and (C_p + o(1)) d_p(G) n^{p-1} for 3/2 < p < 2, where each leading constant is claimed best possible, with C_p obtained from an exact variational problem over finite kernels. The proof relies on a newly introduced sparse graphon operator estimate that converts hereditary p-density bounds into spectral bounds while preserving leading constants and explaining the transition at the critical exponent p = 3/2. For the endpoint p = 2 the result recovers Wilf's exact bound.

Significance. If the central claims hold, the work supplies the first sharp asymptotic resolution of Guiduli-type hereditary spectral problems across the full range 1 < p ≤ 2, including explicit best-possible constants and a variational characterization of the transition at p = 3/2. The introduction of a sparse graphon operator estimate that preserves leading terms constitutes a technical contribution that may be reusable for other asymptotic hereditary problems in spectral graph theory.

major comments (2)
  1. [Abstract] Abstract and the statement of the main theorem: the assertion that the stated constants are best possible and that the variational problem for C_p yields the optimum rests on the sparse graphon operator estimate, but the manuscript provides neither the full derivation of this estimate nor explicit error-term control showing that the leading constant is preserved without loss; this leaves a gap between the claimed sharpness and the supporting arguments.
  2. [Main result] The transition at p = 3/2 and the case distinctions: the claim that the sparse graphon operator estimate explains the change from √n to √(n log n) scaling requires a concrete verification that the operator norm bound converts the hereditary d_p constraint into the precise leading term in each regime; without this verification the case split remains formally asserted rather than derived.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need for greater explicitness in the derivation of the sparse graphon operator estimate. We agree that additional detail is required to fully substantiate the sharpness claims and the derivation of the case distinctions. We will revise the manuscript by expanding the relevant sections with complete proofs and verifications.

read point-by-point responses

  1. Referee: [Abstract] Abstract and the statement of the main theorem: the assertion that the stated constants are best possible and that the variational problem for C_p yields the optimum rests on the sparse graphon operator estimate, but the manuscript provides neither the full derivation of this estimate nor explicit error-term control showing that the leading constant is preserved without loss; this leaves a gap between the claimed sharpness and the supporting arguments.

    Authors: We agree that the manuscript does not currently contain a self-contained, fully detailed derivation of the sparse graphon operator estimate together with explicit error-term bounds. In the revised version we will insert a complete proof of the estimate, including the necessary quantitative error control that shows the leading constants are preserved without loss. This will rigorously close the gap identified by the referee and support the optimality assertions. revision: yes

  2. Referee: [Main result] The transition at p = 3/2 and the case distinctions: the claim that the sparse graphon operator estimate explains the change from √n to √(n log n) scaling requires a concrete verification that the operator norm bound converts the hereditary d_p constraint into the precise leading term in each regime; without this verification the case split remains formally asserted rather than derived.

    Authors: The transition at p = 3/2 is a direct consequence of the different asymptotic regimes of the sparse graphon operator estimate when applied to the hereditary p-density constraint. In the revision we will add an explicit verification subsection that derives the precise leading scalings (√n, √(n log n), and n^{p-1}) from the operator-norm bound in each range of p, thereby obtaining the case distinctions from the estimate rather than asserting them. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation converts hereditary d_p bounds into spectral bounds via a newly introduced sparse graphon operator estimate that preserves leading constants and produces the exact p=3/2 transition; the variational characterization of C_p is defined externally over finite kernels and does not reduce the claimed bounds to a fit or self-citation by construction. No self-definitional, fitted-prediction, or load-bearing self-citation steps appear in the abstract or stated method.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard facts about adjacency-matrix eigenvalues and on the applicability of graphon techniques to finite graphs; no free parameters or new entities are introduced in the abstract statement.

axioms (2)
  • standard math Standard spectral properties of the adjacency matrix of a finite graph
    Invoked to relate λ(G) to the Rayleigh quotient and to apply operator-norm bounds.
  • domain assumption Existence of graphon representations that capture hereditary density constraints for sparse graphs
    The sparse graphon operator estimate is the key new tool used to convert d_p bounds into spectral bounds.

pith-pipeline@v0.9.1-grok · 5955 in / 1408 out tokens · 28063 ms · 2026-06-27T16:43:36.206236+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

33 extracted references · 1 linked inside Pith

  1. [1]

    Spectral extrema for graphs: The Zarankiewicz problem

    László Babai and Barry Guiduli. Spectral extrema for graphs: The Zarankiewicz problem. Electronic Journal of Combinatorics, 16(1):Research Paper R123, 8 pp., 2009

    2009

  2. [2]

    Percolation on dense graph sequences.Annals of Probability, 38(1):150–183, 2010

    Béla Bollobás, Christian Borgs, Jennifer Chayes, and Oliver Riordan. Percolation on dense graph sequences.Annals of Probability, 38(1):150–183, 2010

    2010

  3. [3]

    The phase transition in inhomogeneous random graphs.Random Structures & Algorithms, 31(1):3–122, 2007

    Béla Bollobás, Svante Janson, and Oliver Riordan. The phase transition in inhomogeneous random graphs.Random Structures & Algorithms, 31(1):3–122, 2007

    2007

  4. [4]

    Chayes, Henry Cohn, and Yufei Zhao

    Christian Borgs, Jennifer T. Chayes, Henry Cohn, and Yufei Zhao. AnLp theory of sparse graph convergence II: LD convergence, quotients, and right convergence.Annals of Probability, 46(1):337–396, 2018

    2018

  5. [5]

    Chayes, Henry Cohn, and Yufei Zhao

    Christian Borgs, Jennifer T. Chayes, Henry Cohn, and Yufei Zhao. AnLp theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions.Transactions of the American Mathematical Society, 372(5):3019–3062, 2019

    2019

  6. [6]

    Jane Breen, Alex W. N. Riasanovsky, Michael Tait, and John Urschel. Maximum spread of graphs and bipartite graphs.Communications of the American Mathematical Society, 2:417–480, 2022

    2022

  7. [7]

    A general theorem in spectral extremal graph theory.Transactions of the American Mathematical Society, 2025

    John Byrne, Dheer Noal Desai, and Michael Tait. A general theorem in spectral extremal graph theory.Transactions of the American Mathematical Society, 2025. To appear; also available as arXiv:2401.07266

    arXiv 2025

  8. [8]

    Cioabă, Dheer Noal Desai, and Michael Tait

    Sebastian M. Cioabă, Dheer Noal Desai, and Michael Tait. The spectral even cycle problem. Combinatorial Theory, 4(1):Paper No. 10, 2024

    2024

  9. [9]

    Shuang Gao and Peter E. Caines. Spectral representations of graphons in very large network systems control. In2019 IEEE 58th Conference on Decision and Control (CDC), pages 5068–5075, 2019. 18

    2019

  10. [10]

    PhD thesis, University of Chicago, 1996

    Barry Guiduli.Spectral Extrema for Graphs. PhD thesis, University of Chicago, 1996

    1996

  11. [11]

    Undecidability of linear inequalities in graph homomorphism densities.Journal of the American Mathematical Society, 24(2):547–565, 2011

    Hamed Hatami and Serguei Norine. Undecidability of linear inequalities in graph homomorphism densities.Journal of the American Mathematical Society, 24(2):547–565, 2011

    2011

  12. [12]

    Maxi- mum spectral sum of graphs.arXiv preprint, 2026

    Hitesh Kumar, Lele Liu, Hermie Monterde, Shivaramakrishna Pragada, and Michael Tait. Maxi- mum spectral sum of graphs.arXiv preprint, 2026

    2026

  13. [13]

    Spectral radius of graphs with size constraints: Resolving a conjecture of Guiduli.arXiv preprint, 2024

    Rui Li, Anyao Wang, and Mingqing Zhai. Spectral radius of graphs with size constraints: Resolving a conjecture of Guiduli.arXiv preprint, 2024. arXiv:2412.06375

    arXiv 2024

  14. [14]

    Graph limits and spectral extremal problems for graphs.SIAM Journal on Discrete Mathematics, 38(1):590–608, 2024

    Lele Liu. Graph limits and spectral extremal problems for graphs.SIAM Journal on Discrete Mathematics, 38(1):590–608, 2024

    2024

  15. [15]

    Unsolved problems in spectral graph theory.Operations Research Transactions, 27(4):33–60, 2023

    Lele Liu and Bo Ning. Unsolved problems in spectral graph theory.Operations Research Transactions, 27(4):33–60, 2023. Also available as arXiv:2305.10290

    arXiv 2023

  16. [16]

    On spectral Turán theorems: Confirming a conjecture of Guiduli and two problems of Nikiforov.arXiv preprint, 2026

    Lele Liu and Bo Ning. On spectral Turán theorems: Confirming a conjecture of Guiduli and two problems of Nikiforov.arXiv preprint, 2026. arXiv:2605.05048

    Pith/arXiv arXiv 2026

  17. [17]

    American Mathematical Society, Providence, RI, 2012

    László Lovász.Large Networks and Graph Limits, volume 60 ofAmerican Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2012

    2012

  18. [18]

    Limits of dense graph sequences.Journal of Combinatorial Theory, Series B, 96(6):933–957, 2006

    László Lovász and Balázs Szegedy. Limits of dense graph sequences.Journal of Combinatorial Theory, Series B, 96(6):933–957, 2006

    2006

  19. [19]

    W. Mantel. Problem 28.Wiskundige Opgaven met de Oplossingen, 10:60–61, 1907

    1907

  20. [20]

    Bounds on graph eigenvalues II.Linear Algebra and its Applications, 427(2– 3):183–189, 2007

    Vladimir Nikiforov. Bounds on graph eigenvalues II.Linear Algebra and its Applications, 427(2– 3):183–189, 2007

    2007

  21. [21]

    The spectral radius of graphs without paths and cycles of specified length

    Vladimir Nikiforov. The spectral radius of graphs without paths and cycles of specified length. Linear Algebra and its Applications, 432(9):2243–2256, 2010

    2010

  22. [22]

    Eigenvalues of graphs

    Eva Nosal. Eigenvalues of graphs. Master’s thesis, University of Calgary, 1970

    1970

  23. [23]

    Razborov

    Alexander A. Razborov. Flag algebras.Journal of Symbolic Logic, 72(4):1239–1282, 2007

    2007

  24. [24]

    Razborov

    Alexander A. Razborov. On the minimal density of triangles in graphs.Combinatorics, Probability and Computing, 17(4):603–618, 2008

    2008

  25. [25]

    The clique density theorem.Annals of Mathematics, 184(3):683–707, 2016

    Christian Reiher. The clique density theorem.Annals of Mathematics, 184(3):683–707, 2016

    2016

  26. [26]

    Richard P. Stanley. A bound on the spectral radius of graphs withe edges.Linear Algebra and its Applications, 87:267–269, 1987

    1987

  27. [27]

    Limits of kernel operators and the spectral regularity lemma.European Journal of Combinatorics, 32(7):1156–1167, 2011

    Balázs Szegedy. Limits of kernel operators and the spectral regularity lemma.European Journal of Combinatorics, 32(7):1156–1167, 2011

    2011

  28. [28]

    Three conjectures in extremal spectral graph theory.Journal of Combinatorial Theory, Series B, 126:137–161, 2017

    Michael Tait and Josh Tobin. Three conjectures in extremal spectral graph theory.Journal of Combinatorial Theory, Series B, 126:137–161, 2017

    2017

  29. [29]

    Joel A. Tropp. An introduction to matrix concentration inequalities.Foundations and Trends in Machine Learning, 8(1-2):1–230, 2015

    2015

  30. [30]

    On an extremal problem in graph theory.Mat

    Paul Turán. On an extremal problem in graph theory.Mat. Fiz. Lapok, 48:436–452, 1941. 19

    1941

  31. [31]

    The laplacian spectrum of large graphs sampled from graphons.IEEE Transactions on Network Science and Engineering, 8(2):1711–1721, 2021

    Renato Vizuete, Federica Garin, and Paolo Frasca. The laplacian spectrum of large graphs sampled from graphons.IEEE Transactions on Network Science and Engineering, 8(2):1711–1721, 2021

    2021

  32. [32]

    On a conjecture of spectral extremal problems.Journal of Combinatorial Theory, Series B, 159:20–41, 2023

    Jing Wang, Liying Kang, and Yisai Xue. On a conjecture of spectral extremal problems.Journal of Combinatorial Theory, Series B, 159:20–41, 2023

    2023

  33. [33]

    Herbert S. Wilf. Spectral bounds for the clique and independence numbers of graphs.Journal of Combinatorial Theory, Series B, 40(1):113–117, 1986. 20

    1986