Pith. sign in

REVIEW 2 major objections 4 minor 23 references

This paper solves the weighted relaxation and shows the minimum spectral radius for an n-vertex, e-edge graph equals a closed bi-regular formula in the average degree 2e/n, and that any simple graph attaining it has degrees differing by at

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review

2026-08-01 16:43 UTC pith:4VD6SF3U

load-bearing objection The weighted relaxation is solved cleanly and gives real new bounds, but Theorem 1.5's reducible-case induction has a genuine gap around odd-sum components; worth refereeing with a requested patch. the 2 major comments →

arxiv 2607.17895 v1 pith:4VD6SF3U submitted 2026-07-20 math.CO

A New Lower Bound on the Spectral Radius of Graphs with Prescribed Average Degree

Sonny Ben-Shimon , Idan Eisner , Shlomo Hoory This is my paper
classification math.CO MSC 05C5005C3505C0715A42
keywords spectral radiusaverage degreeextremal graphsweighted adjacency matricesbi-regular graphsHong's conjecturePillai's arithmetical functionspectral radius lower bound
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

Given only the number of vertices and edges, how small can a graph's spectral radius be? This paper answers the question for a natural relaxation: allow non-negative symmetric adjacency matrices with integral row sums instead of only 0/1 entries. It proves that the minimum spectral radius in this wider family equals an explicit function of the average degree d=2e/n, achieved by weighted bi-regular graphs with degrees floor(d) and floor(d)+1. That closed-form expression gives a new lower bound for ordinary simple graphs, improving two previously known bounds. The authors then characterize exactly when a simple graph can realize the relaxed minimum: the parameters must satisfy four number-theoretic conditions, and in those cases the extremal graph's minimum and maximum degree differ by at most one, confirming Hong's 1993 conjecture for those configurations. Counting the number of such realizable edge counts shows it always grows at least linearly with n and is Θ(n log n) on average.

Core claim

The central claim is Theorem 1.5: among symmetric n×n non-negative matrices with integral row sums and total sum 2e, the smallest spectral radius is ρ1(2e/n), where ρ1 is defined from the bi-regular formula ρ0(d1,d2,ν) of Theorem 1.4 with d1=⌊2e/n⌋, d2=d1+1, and ν={2e/n}. Any minimizer is bi-regular: the degree-d1 vertices induce an empty subgraph and the degree-d2 vertices induce a regular subgraph. For simple graphs, this yields the lower bound ρ(G_{n,e}) ≥ ρ1(2e/n). Theorem 1.6 gives necessary and sufficient conditions for the existence of an ordinary graph in the extremal bi-regular family, and Theorem 1.7 extracts the list of average degrees for which the bound is attained by a discrete

What carries the argument

The proof centers on the convexity of the spectral radius on symmetric matrices together with first-order perturbation theory (Corollaries 2.6 and 2.7): moving weight between two vertices of unequal Perron-eigenvector entries lowers ρ at rate −(xi−xj)^2/||x||^2. Repeated application forces any minimizer to have Perron entries constant on degree classes, an empty induced subgraph on the low-degree class, and a regular induced subgraph on the high-degree class, reducing the problem to a 2×2 matrix whose spectral radius is the closed form ρ0(d1,n1,d2,n2) = (1/2)[d2−d1(n1/n2) + sqrt(4d1²(n1/n2)+(d2−d1(n1/n2))²)]. Theorem 1.5 shows the average-degree relaxation collapses to this bi-regular formul

Load-bearing premise

In the disconnected case of the proof of Theorem 1.5 (Section 4), the argument assumes every direct-sum component of a global minimizer is itself a minimizer for its own subproblem — a step the text does not justify, and which is delicate because a component's total edge weight may be odd and thus outside the family to which the induction hypothesis applies.

What would settle it

For a concrete pair such as n=6, e=7, numerically minimize the spectral radius over the convex set of 6×6 non-negative symmetric matrices with integral row sums summing to 14, and compare the optimum to ρ1(7/3); any value below ρ1 would refute Theorem 1.5. Alternatively, take a disconnected candidate minimizer for some larger (n,e) and check whether each component's spectral radius equals ρ1 of that component's own average degree; a failure would isolate the unproved component-optimality step.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • For every n,e, ρ(G_{n,e}) ≥ ρ1(2e/n), which improves on both the root-mean-square and the entropy-based lower bounds in the covered cases.
  • If the bound is attained by a simple graph, its maximum and minimum degree differ by at most one, so Hong's conjecture holds for every average degree appearing in the list (3).
  • The four conditions of Theorem 1.6 give a complete, checkable criterion for when the weighted minimum is realized by an ordinary graph.
  • The number E(n) of non-trivial edge counts for which the relaxation is tight satisfies E(n) ≥ ⌊(3n−5)/2⌋, with equality exactly when n is prime or twice a prime, and E(n) grows super-linearly along an infinite family of highly composite, square-free integers.
  • For large average degree d, the gap between ρ1(d) and the trivial bound d decays as Δ²ν(1−ν) max(ν,1−ν)/d, where Δ=1 and ν is the fractional part of d.

Where Pith is reading between the lines

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

  • Because E(n) averages Θ(n log n) out of ~n²/2 possible edge counts, the density of (n,e) pairs for which the relaxed bound is tight tends to zero; proving Hong's conjecture in full generality would require a strictly stronger lower bound than ρ1 for most pairs, so this paper delineates the boundary of the weighted relaxation.
  • The same convexity-plus-perturbation argument could be applied to other extremal spectral problems on weighted matrices, such as minimizing the spectral radius of the non-backtracking matrix under an average-degree constraint, as the authors themselves suggest.
  • The connectedness characterization (Theorem 6.5) provides explicit construction patterns (star, double-star, regular core with leaves) for connected graphs with prescribed spectral radius, which might be useful for designing expanders or graphs with controlled spectral gaps.
  • If the direct-sum induction step in the proof of Theorem 1.5 can be repaired, the structural rigidity (empty V1, regular V2) would hold for disconnected minimizers as well; until then, the structural conclusion is fully established only for irreducible minimizers.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper studies the minimization of the spectral radius ρ(G) over simple n-vertex, e-edge graphs G_{n,e}. It relaxes the problem to symmetric non-negative n×n matrices with integral row sums and total sum 2e (family M_{n,e}), and proves (Theorem 1.5) that every minimizer in M_{n,e} must be bi-regular with degrees ⌊2e/n⌋ and ⌊2e/n⌋+1. This yields a closed-form lower bound ρ1(2e/n) on ρ(G_{n,e}). The paper also characterizes exactly when this bound is attained by a simple graph (Theorem 1.6), gives a number-theoretic condition for the ratio ν (Theorem 1.7), and counts the number E(n) of edge values for which the bound is tight (Theorem 1.8), proving E(n) grows linearly at worst and super-linearly on average. The proof of the bi-regular formula (Theorem 1.4) is complete; the induction for the general case handles the irreducible case through perturbation lemmas, but the reducible case relies on an induction hypothesis applied to components that may lie outside the induction domain.

Significance. The main results are significant if the proof of Theorem 1.5 can be completed. Theorem 1.4 is a clean, self-contained contribution to the weighted relaxation. The counting and characterization results (Theorems 1.6–1.8) are elegant and appear internally consistent conditional on Theorem 1.5. The paper gives explicit, parameter-free derivations and a new lower bound that improves on known Hoffman/RMS and entropy bounds. However, because the central structural theorem is used as the foundation for the lower bound and the enumeration, the unpatched gap in its proof currently blocks acceptance.

major comments (2)
  1. [Section 4, proof of Theorem 1.5, reducible case] The equality chain ρ1(d) ≥ ρ(M) = max_i ρ(M_i) = max_i ρ1(d_i) ≥ ρ1(max_i d_i) ≥ ρ1(d) applies the induction hypothesis to each component M_i without verifying that M_i belongs to M_{n_i,e_i} for an integer e_i. A component's total sum s_i = n_i d_i can be odd, so M_i is not in any M_{n_i,e_i}; for example, when (n,e)=(6,5) a direct sum of two 3-vertex components with total sum 5 each has s_i odd. The equality max_i ρ(M_i)=max_i ρ1(d_i) is therefore unjustified. An attempted repair by extending Theorem 1.5 to all integral total sums is false: for n=4 and total sum 5, Proposition 1.2 gives ρ ≥ √7/2 ≈ 1.323, while ρ1(5/4) = (√13−1)/2 ≈ 1.303. This gap invalidates the proof of Theorem 1.5, and with it the lower bound ρ(G_{n,e}) ≥ ρ1(2e/n) and the structural conclusions used in Sections 6–7.
  2. [Section 4, proof of Theorem 1.5, d<1 case] The claim that 'if d<1, then d_i ≤ 1 for all i' is false. For n=6, e=2, take components of sizes 2 and 4 with total sums 3 and 1; the first component has average degree 1.5 while the global average is 2/3 < 1. Thus even in the subcase d<1, the components need not have average degree at most 1, and the induction step as written does not apply. This is a separate obstruction in the same reducible-case argument.
minor comments (4)
  1. [Section 1.1] The paragraph beginning 'The maximization problem has been extensively studied...' appears twice, with the second copy followed by Hong's bound; please remove the duplication.
  2. [Theorem 1.5] For e=0, the conclusion refers to M_{d1,n1,d2,n2} with n2=0, which is not a defined family (Theorem 1.4 assumes n2>0). Please handle e=0 explicitly.
  3. [Section 2] The notation ρ(G)=ρ_min(G) in the introduction is potentially confusing; consider using ρ_min consistently.
  4. [Lemma 2.8 and Corollary 2.7] The perturbation matrix E^{(ij)} includes diagonal entries -1; this is clear from Corollary 2.7 but the notation in Lemma 2.8 could be annotated to avoid confusion.

Circularity Check

0 steps flagged

No significant circularity: the main derivation is self-contained; self-citations are contextual only.

full rationale

The paper's central claims are derived from explicit optimization and eigenvalue calculations rather than from fitting or self-referential construction. Theorem 1.4 derives the spectral radius formula for the bi-regular weighted family by solving the 2x2 Perron eigenvalue system under the row-sum constraints; the result is not defined to equal the input. Theorem 1.5, the structural characterization for M_{n,e}, is proved in the irreducible case from convexity and perturbation lemmas (Corollaries 2.4, 2.7, Lemma 4.3, Lemma 4.4) rather than by assuming the bi-regular conclusion. The reducible case invokes an induction hypothesis on direct-sum components, and the paper's own application of that hypothesis is questionable because a component's total sum need not be even, so the component may not belong to any M_{n_i,e_i}. However, this is a correctness gap, not circularity: the proof does not use its target claim as an input; it simply applies an induction hypothesis more broadly than the stated family permits. The discrete realizability conditions in Theorem 1.6 are derived from external Erdős-Gallai/Gale-Ryser criteria cited to Tripathi-Vijay and Berger, not from the paper's own fitted values. The enumeration in Theorem 7.1 is an exact summation over number-theoretic functions; no parameter is fitted to any target count. Author-overlap citations ([1], [9], [13]) appear only as motivational or technical background (Moore bounds, entropy estimates, universal covering trees) and are not load-bearing for the new lower bound or its structural characterization. There is no self-definitional reduction, no fitted input relabeled as a prediction, and no imported uniqueness theorem from the authors' prior work. Thus the circularity score is 0.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

The central claim has no fitted constants: all degrees, sizes, and edge counts are problem inputs. The proof rests on standard matrix theory, standard graphic-sequence criteria, a nonstandard weighted-graph convention, and externally proved results for Pillai's function. No new particles, forces, or unexplained entities are introduced.

axioms (5)
  • standard math Perron-Frobenius theorem: irreducible nonnegative matrices have a simple positive spectral radius with strictly positive Perron vectors, and for symmetric matrices the spectral radius equals the operator 2-norm.
    Used throughout Section 2 for convexity of ρ and the eigenvector equalities; stated in Proposition 2.1.
  • standard math First-order eigenvalue perturbation formula dρ(A+tE)/dt = x^T E x / ||x||^2 for symmetric nonnegative irreducible A.
    Basis for the negative-direction arguments in Lemmas 2.8, 4.3 and 4.4; cited from Horn-Johnson.
  • standard math Erdős-Gallai/Tripathi-Vijay characterization of graphic sequences and Gale-Ryser/Berger bipartite degree-sequence criterion.
    Used in Lemmas 6.1 and 6.2 to certify existence of regular and bipartite bi-regular simple graphs.
  • standard math Known maximal order and average order of Pillai's arithmetical function P(n)=Σ gcd(n,k), as surveyed by Tóth.
    Used in Claim 7.9 and Remark 7.10 to obtain E(n)=Ω(n log n) on a subsequence and Θ(n log n) on average.
  • domain assumption Weighted matrices may carry self-loops counted as one unit of row-sum degree; the ρ-minimizer over this superset is a valid lower bound for simple graphs.
    The relaxation to M_{n,e} is the core modeling choice; perturbation lemmas repeatedly transfer diagonal weight, so self-loops are load-bearing.

reviewed 2026-08-01 · how reviews work

0 comments
Cite this review

Pith. "Pith review of A New Lower Bound on the Spectral Radius of Graphs with Prescribed Average Degree." pith.science (2026). https://pith.science/paper/4VD6SF3U

@misc{pith2026260717895,
  author       = {Pith},
  title        = {Pith review of: A New Lower Bound on the Spectral Radius of Graphs with Prescribed Average Degree},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4VD6SF3U}},
  note         = {Machine review of arXiv:2607.17895}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

This work establishes an improved lower bound for the spectral radius of a graph given its average degree. The new bound follows from an exact solution of the fractional relaxation of the problem. Our findings lead to an affirmative answer to a conjecture by Hong (1993) for graphs with specific average degrees -- as the extremal graphs that meet our bound are proven to have a minimal and maximal degree that differ by at most one. Furthermore, we provide an exact characterization of the conditions that permit such discrete realizations. We prove that for a fixed number of vertices $n$, the number of valid edge configurations grows at least linearly with $n$, achieving an average asymptotic order of $\Theta(n\log n)$.

Figures

Figures reproduced from arXiv: 2607.17895 by Idan Eisner, Shlomo Hoory, Sonny Ben-Shimon.

Figure 1
Figure 1. Figure 1: ρ(Mn,e) as a function of d = 2e/n. our figures and it emerges naturally in Theorem 5.1, where we establish the precise scaling law of ρ(Mn,e)−d for large values of d. The last results ask whether the minimum ρ on a weighted graph family is in fact achievable by a simple graph in that family. For the family Mn,e, an affirmative answer implies that Hong’s conjecture is true for the specific n, e pair. By The… view at source ↗
Figure 2
Figure 2. Figure 2: Comparing the three lower bounds for bi-regular graphs with [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Similar to Figure 2 with [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗

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

23 extracted references · 1 linked inside Pith

  1. [1]

    N. Alon, S. Hoory, and N. Linial. The Moore bound for irregular graphs.Graphs and Combinatorics, 18:53–57, 2002

    2002

  2. [2]

    Angel, J

    O. Angel, J. Friedman, and S. Hoory. The non-backtracking spectrum of the universal cover of a graph. Transactions of the American Mathematical Society, 367(6):4287–4318, 2015

    2015

  3. [3]

    A. Berger. A note on the characterization of digraphic sequences.Discrete Mathematics, 314:38–41, 2014

    2014

  4. [4]

    R. A. Brualdi and A. J. Hoffman. On the spectral radius of (0, 1)-matrices.Linear Algebra and its Applications, 65:133–146, 1985

    1985

  5. [5]

    R. A. Brualdi and E. S. Solheid. On the spectral radius of connected graphs.Publ. Inst. Math.(Beograd), 39(53):45–54, 1986

    1986

  6. [6]

    Burda, J

    Z. Burda, J. Duda, J. M. Luck, and B. Waclaw. Localization of the maximal entropy random walk. Phys. Rev. Lett., 102:160602, Apr 2009

    2009

  7. [7]

    S. M. Cioaba, V. Gupta, and C. Marques. On the minimum spectral radius of connected graphs of given order and size.Special Matrices, 12(1):20240027, 2024

    2024

  8. [8]

    Cvetkovi´ c, P

    D. Cvetkovi´ c, P. Rowlinson, and S. Simi´ c.An introduction to the theory of graph spectra. Cambridge University Press, 2009

    2009

  9. [9]

    Eisner and S

    I. Eisner and S. Hoory. Entropy and the growth rate of universal covering trees.arXiv preprint arXiv:2410.10337, 2024

    Pith/arXiv arXiv 2024

  10. [10]

    Y. Hong. Bounds of eigenvalues of a graph.Acta Mathematicae Applicatae Sinica, 4(2):165–168, 1988

    1988

  11. [11]

    Y. Hong. Bounds of eigenvalues of graphs.Discrete Mathematics, 123(1-3):65–74, 1993

    1993

  12. [12]

    Hong, J.-L

    Y. Hong, J.-L. Shu, and K. Fang. A sharp upper bound of the spectral radius of graphs.Journal of Combinatorial Theory, Series B, 81(2):177–183, 2001

    2001

  13. [13]

    S. Hoory. On the girth of graph lifts.arXiv preprint arXiv:2401.01238, 2024

    arXiv 2024

  14. [14]

    R. A. Horn and C. R. Johnson.Matrix analysis. Cambridge University Press, 2012

    2012

  15. [15]

    Liu and C.-w

    C.-a. Liu and C.-w. Weng. Spectral radius and degree sequence of a graph.Linear Algebra and its Applications, 438(8):3511–3515, 2013. 24

    2013

  16. [16]

    Nikiforov

    V. Nikiforov. Some inequalities for the largest eigenvalue of a graph.Combinatorics, Probability and Computing, 11(2):179–189, 2002

    2002

  17. [17]

    Nikiforov

    V. Nikiforov. Some new results in extremal graph theory. In R. Chapman, editor,Surveys in Combina- torics 2011, volume 392 ofLondon Mathematical Society Lecture Note Series, pages 141–182. Cambridge University Press, 2011

    2011

  18. [18]

    T. R´ eti. Graph irregularity and a problem raised by Hong.Acta Polytechnica Hungarica, 15(6):27–43, 2018

    2018

  19. [19]

    Shu and Y

    J. Shu and Y. Wu. Sharp upper bounds on the spectral radius of graphs.Linear algebra and its applications, 377:241–248, 2004

    2004

  20. [20]

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

    1987

  21. [21]

    L. T´ oth. A survey of gcd-sum functions.Journal of Integer Sequences, 13(8):1–23, 2010

    2010

  22. [22]

    Tripathi and S

    A. Tripathi and S. Vijay. A note on a theorem of Erd˝ os & Gallai.Discrete Mathematics, 265(1-3):417– 420, 2003

    2003

  23. [23]

    Von Collatz and U

    L. Von Collatz and U. Sinogowitz. Spektren endlicher grafen: Wilhelm blaschke zum 70. geburtstag gewidmet. InAbhandlungen aus dem Mathematischen Seminar der Universit¨ at Hamburg, volume 21, pages 63–77. Springer, 1957. 25

    1957

This paper was first reviewed by deepseek-v4-flash on August 1, 2026.