Sharp spectral Moon--Moser-type theorems in the linear range via feasible graph parameters

Yang Hu

REVIEW 5 minor 19 references

Sharp spectral Moon--Moser-type theorems in the linear range via feasible graph parameters

T0 review · 0 major / 5 minor · reviewed 2026-07-09 · glm-5.2

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

Pith's one-line read Spectral Hamiltonicity thresholds hold down to linear size

desk verdict Spectral Moon–Moser theorems improved from quadratic to linear range, with clean proofs read the letter →

arxiv 2607.07064 v1 pith:ORGV6UKV submitted 2026-07-08 math.CO

Yang Hu This is my paper

classification math.CO

keywords spectralbalancedbipartitegraphsparametersextremalgraphsharp

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 proves that sharp spectral thresholds for non-Hamiltonicity in balanced bipartite graphs and non-traceability in nearly balanced bipartite graphs — previously known only under a quadratic condition n ≥ (k+1)² — remain valid in the much wider linear range n ≥ 2k (for Hamilton cycles) and n ≥ 2k+1 (for Hamilton paths). Concretely, among all balanced bipartite graphs on 2n vertices with minimum degree at least k that fail to have a Hamilton cycle, the graph B^k_n uniquely maximizes both the adjacency spectral radius and the signless Laplacian spectral radius; the analogous statement holds for nearly balanced bipartite graphs and Hamilton paths, with the unique extremal graph S^k_n. The proof works not just for these two spectral quantities but for any graph parameter that is strictly increasing under edge addition and nondecreasing under Kelmans operations — what the paper calls a feasible parameter — yielding a structural Moon–Moser-type theorem from which both spectral results and the classical edge-count result follow as corollaries.

What carries the argument

Feasible graph parameters (strictly increasing under edge addition, nondecreasing under Kelmans operations), bipartite closure of Bondy–Chvátal, Kelmans operations within one part of a bipartition, quotient-matrix eigenvalue computations for equitable partitions, and a switching/Rayleigh-quotient argument for the equality case in the signless Laplacian setting.

What would settle it

A counterexample would be a non-Hamiltonian balanced bipartite graph on 2n vertices with n ≥ 2k, minimum degree at least k, and adjacency or signless Laplacian spectral radius strictly exceeding that of B^k_n — or, equivalently, a flaw in the equality-case argument of Theorem 1.6 showing that some non-B^s_n graph in the family achieves the same parameter value as B^s_n without being forced to have a complete bipartite closure.

Watch

Extended reading notes

Core claim

The central mechanism is a two-step reduction. First, a bipartite-closure argument (Lemma 3.1) shows that any non-Hamiltonian balanced bipartite graph with minimum degree at least k must contain s vertices of degree at most s in one part, for some k ≤ s ≤ ⌊n/2⌋. Second, a sequence of Kelmans operations — which move edges from one vertex to another within the same part while preserving degrees in the opposite part — pushes the graph toward a canonical extremal form B^s_n without decreasing the feasible parameter. The equality case then forces the original graph to be exactly B^s_n, because any deviation would push the bipartite closure all the way to the complete bipartite graph, contradictng

Load-bearing premise

The most delicate step is the equality-case analysis showing that if the extremal graph is not exactly B^s_n, then every missing edge between the low-degree set and its neighborhood satisfies a degree-sum condition of at least n+1, which forces the bipartite closure to become complete and hence Hamiltonian — a contradiction. This requires the degree-sum lower bound to hold simultaneously for all relevant non-edges, which in turn depends on the structural conclusion of Lemma 3

Editorial extensions

If this is right

Any future graph parameter shown to be feasible (increasing under edge addition, nondecreasing under Kelmans) automatically inherits the Moon–Moser-type extremal theorem over balanced and nearly balanced bipartite graphs with minimum degree at least k.
The linear range n ≥ 2k removes the main practical bottleneck of the earlier Li–Ning results (which required n ≥ (k+1)²), making the spectral Hamiltonicity tests applicable to dense graphs where n is only a small constant multiple of k.
The structural characterization of extremal graphs as unique (B^k_n and S^k_n) means that any non-Hamiltonian balanced bipartite graph with minimum degree k whose spectral radius meets the threshold must be isomorphic to a single explicitly described graph.
The reduction via bipartite closure plus Kelmans operations provides a template for analogous problems on other Hamiltonian-type properties (e.g., Hamilton-connectedness, pancyclicity) in bipartite settings.

Reading between the lines

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

The feasible-parameter framework likely extends to other monotone spectral quantities not explicitly treated here — for instance the Laplacian spectral radius or distance spectral radius — provided one can verify the Kelmans monotonicity condition, which may require separate proof.
The gap between the linear range achieved here and the trivial lower bound (n must be at least 2k for the minimum-degree condition to be non-vacuous in balanced bipartite graphs) is now closed: n ≥ 2k is essentially best possible for the balanced case.
The switching argument in Lemma 4.4, which proves uniqueness of the extremal graph within the family S^s_n by comparing Perron coordinates, suggests that similar coordinate-comparison techniques could resolve equality cases in other bipartite spectral extremal problems.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

The main thing to know: this paper takes Li–Ning's spectral Moon–Moser theorems for balanced and nearly balanced bipartite graphs and improves the required graph size from quadratic (n ≥ (k+1)²) to linear (n ≥ 2k, resp. 2k+1). That's the optimal range, and the extremal graphs are uniquely identified. It's a real strengthening of known results, not a repackaging. The feasible-parameter framework (borrowed from Ai–Lei–Ning–Shi and Liu–Ning–Wang) is applied cleanly here: the structural reduction in Theorem 1.6 shows that any extremal non-Hamiltonian balanced bipartite graph must live in the family {B^s_n}, and then Lemma 3.2 does the spectral comparison via quotient matrices to pin down s = k. The nearly balanced case in Section 4 follows the same template with the two families S^s_n and T^t_n. The proofs are detailed and self-contained. The equality-case analysis in Theorem 1.6 is the most delicate step — the argument that G must be exactly B^s_n, not just a subgraph, runs through a degree-sum closure argument showing that any deviation forces cl_B(G) = K_{n,n} and hence a Hamilton cycle. I checked this carefully and it holds up: the key observation is that equality P(G) = P(H) forces G[X₂, Y] = K_{n−s,n}, which then makes the degree-sum bounds work for all non-edges simultaneously. The stress-test note on this point is correct. The spectral comparison lemmas (3.2, 4.2, 4.3) are computational but straightforward — quotient matrix, characteristic polynomial, monotonicity argument. Lemma 4.4, which handles the equality case for the families S^s_n and T^t_n via Perron vector switching, is a nice touch and handles something the feasible-parameter framework alone doesn't cover. Soft spots are minor. The proof structure closely follows [10], so readers familiar with that paper will find few surprises. The novelty is in the bipartite adaptation and the linear-range spectral comparisons, not in the method itself. The paper is also fairly mechanical in places — Section 4 mirrors Section 3 closely. But this is honest, correct work that strengthens existing theorems to their natural limit. It deserves a serious referee. The right audience is spectral extremal graph theorists working on Hamiltonicity problems.

Referee Report

0 major / 5 minor

Summary. This paper establishes sharp spectral extremal results for non-Hamiltonian balanced bipartite graphs and non-traceable nearly balanced bipartite graphs with minimum degree at least $k$. The author improves the range of validity from the quadratic condition $n ge (k+1)^2$ (due to Li and Ning) to the linear ranges $n ge 2k$ and $n ge 2k+1$, respectively. The extremal graphs are uniquely determined as $B^k_n$ (for the balanced case) and $S^k_n$ (for the nearly balanced case) for both the adjacency spectral radius $rho$ and the signless Laplacian spectral radius $q$. The proofs use the feasible graph parameter framework of Ai, Lei, Ning, and Shi, yielding a general structural theorem from which the spectral results follow via quotient-matrix computations.

Significance. The results represent a genuine quantitative improvement over the prior work of Li and Ning, reducing a quadratic part-size condition to a linear one, which is the natural range for the Moon-Moser problem. The feasible-parameter approach is elegant and unifying: Theorems 1.6 and 1.9 are structural results valid for any feasible parameter, and the spectral theorems follow as corollaries. The equality-case analysis in Theorem 1.6 (showing the extremal graph must be exactly $B^s_n$) is the most delicate part and is handled cleanly via a degree-sum argument with the bipartite closure. The spectral comparison lemmas (Lemmas 3.2, 4.2, 4.3) involve careful but straightforward calculus on quotient-matrix eigenvalues. The paper is well-written and the proofs are detailed and checkable.

minor comments (5)

In Lemma 4.2, the concavity argument for $f(u)=u^2(n-u)(n-u-1)$ is slightly terse. Stating explicitly that $u(n-u)$ and $u(n-u-1)$ are concave and attain minima at endpoints on $[k, n-k-1]$ would improve readability.
The closed-form expressions for $rho(B^s_n)$ and $q(B^s_n)$ in Lemma 3.2 are derived but not explicitly written in the lemma statement; including them (or referencing the formulas in the proof) would make the result more self-contained.
Reference [10] (Liu, Ning, Wang) is cited as arXiv:2604.01068, 2026. If this is not yet published or accepted, the authors should verify the citation details at the time of publication.
In the proof of Theorem 1.6, the step showing $G sim B^s_n$ could benefit from a brief forward reference to the specific lines where $d_G(x)+d_G(y) ge n+1$ is established, to guide the reader through the degree-sum argument.
The notation $text{spex}^B_lambda$ and $text{spex}^{NB}_lambda$ is introduced but a brief reminder that $B$ stands for 'balanced' and $NB$ for 'nearly balanced' would help.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity detected

full rationale

The derivation chain is entirely non-circular. The paper's main results (Theorems 1.7, 1.10) follow from two independent components: (1) structural feasible-parameter theorems (1.6, 1.9) that reduce extremal graphs to specific families (B^s_n, S^s_n, T^t_n) using the bipartite closure theorem of Bondy-Chvátal [2], Kelmans operations, and the feasible-parameter framework of Ai-Lei-Ning-Shi [1] — all externally cited, none authored by the present author Yang Hu; and (2) self-contained spectral comparison lemmas (3.2, 4.2, 4.3, 4.4) that compute which member of each family maximizes the spectral radius via quotient-matrix eigenvalue calculations and Rayleigh quotient switching arguments. No step reduces to its own inputs by construction. There is no self-citation at all (the author appears in none of references [1]–[19]), no fitted parameters repackaged as predictions, no ansatz smuggled through citation, and no definitional circularity. The prior results being extended (Li-Ning [8,9] with quadratic range n≥(k+1)²) are strictly weaker than the linear-range results proved here, so the contribution is genuinely new. The equality-case analysis in Theorem 1.6, while delicate, is a clean degree-sum argument that is logically sound and non-circular.

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

No free parameters, no ad hoc axioms, no invented entities. The paper is a pure mathematics derivation using standard tools (bipartite closure, Kelmans operations, quotient matrices, Perron–Frobenius). The feasible-parameter framework is cited, not invented.

assumptions (4)

standard math Bipartite closure theorem (Bondy–Chvátal): G is Hamiltonian iff cl_B(G) is Hamiltonian.
Theorem 2.1, invoked in Lemma 3.1 and the proof of Theorem 1.6. Standard result from 1976.
standard math Quotient-matrix eigenvalue interlacing (Brouwer–Haemers): Perron eigenvalue of quotient matrix equals Perron eigenvalue of original matrix for equitable partitions.
Lemma 2.2, used in all spectral computations (Lemmas 3.2, 4.2, 4.3). Standard textbook result.
domain assumption Feasible parameter framework: parameters increasing under edge addition and nondecreasing under Kelmans operations yield extremal theorems.
Definition 1.4 from Ai–Lei–Ning–Shi [1]. The paper applies this framework but does not re-derive it.
standard math Perron–Frobenius theorem: spectral radius is strictly increasing under edge addition for connected graphs.
Invoked in proofs of Theorems 1.7 and 1.10 to verify that ρ and q satisfy the feasibility conditions.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Sharp spectral Moon--Moser-type theorems in the linear range via feasible graph parameters." pith.science (2026). https://pith.science/paper/ORGV6UKV

@misc{pith2026260707064,
  author       = {Pith},
  title        = {Pith review of: Sharp spectral Moon--Moser-type theorems in the linear range via feasible graph parameters},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ORGV6UKV}},
  note         = {Machine review of arXiv:2607.07064}
}

abstract

Moon and Moser proved a sharp edge-extremal theorem for Hamilton cycles in balanced bipartite graphs with minimum degree at least $k$. Li and Ning obtained spectral analogues for Hamiltonicity in balanced bipartite graphs of order $2n$ and for traceability in nearly balanced bipartite graphs with part sizes $n$ and $n-1$, under the assumption $n\ge (k+1)^2$. We show that their sharp spectral thresholds remain valid in the linear ranges $n\ge 2k$ and $n\ge 2k+1$, respectively. More precisely, we determine the extremal values of the adjacency spectral radius and the signless Laplacian spectral radius for non-Hamiltonian balanced bipartite graphs with minimum degree $\delta(G)\ge k$, and for non-traceable nearly balanced bipartite graphs with $\delta(G)\ge k$. In each case, the extremal graph is unique up to isomorphism. Our proof is based on feasible graph parameters: parameters that increase under edge addition and are nondecreasing under Kelmans operations. This yields Moon--Moser type extremal theorems for a general class of parameters, from which the spectral results follow.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

[10]

X. Liu, B. Ning and T. Wang, Extensions of Erd˝ os’s 1962 theorem on non-Hamiltonian graphs, arXiv:2604.01068v2, 2026.https://doi.org/10.48550/arXiv.2604.01068

work page Pith review arXiv doi:10.48550/arxiv.2604.01068 1962
[1]

J. Ai, H. Lei, B. Ning and Y. Shi, Graph operations and a unified method for Tur´ an- type problems on paths, cycles, and matchings, Canad. J. Math. (2025), 1–27. https: //doi.org/10.4153/S0008414X25101788

work page doi:10.4153/s0008414x25101788 2025
[2]

J. A. Bondy and V. Chv´ atal, A method in graph theory, Discrete Math. 15 (2) (1976), 111–135

work page 1976
[3]

A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Springer, New York, 2012

work page 2012
[4]

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

work page 1986
[5]

Erd˝ os, Remarks on a paper of P´ osa, Magyar Tud

P. Erd˝ os, Remarks on a paper of P´ osa, Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl. 7 (1962), 227–229

work page 1962
[6]

Fiedler and V

M. Fiedler and V. Nikiforov, Spectral radius and Hamiltonicity of graphs, Linear Algebra Appl. 432 (9) (2010), 2170–2173

work page 2010
[7]

X. He, Y. Li and L. Feng, Spectral radius and rainbow Hamilton paths of a graph, Discrete Math. 347 (10) (2024) 114128

work page 2024

Show all 19 references

[8]

Li and B

B. Li and B. Ning, Spectral analogues of Erd˝ os’s and Moon–Moser’s theorems on Hamilton cycles, Linear Multilinear Algebra 64 (11) (2016), 2252–2269

2016
[9]

Li and B

B. Li and B. Ning, Spectral analogues of Moon–Moser’s theorem on Hamilton paths in bipartite graphs, Linear Algebra Appl. 515 (2017), 180–195

2017
[11]

Lu, H.-Q

M. Lu, H.-Q. Liu and F. Tian, Spectral radius and Hamiltonian graphs, Linear Algebra Appl. 437 (7) (2012), 1670–1674

2012
[12]

Moon and L

J. Moon and L. Moser, On Hamiltonian bipartite graphs, Israel J. Math. 1 (3) (1963), 163–165

1963
[13]

Nikiforov, Spectral radius and Hamiltonicity of graphs with large minimum degree, Czechoslovak Math

V. Nikiforov, Spectral radius and Hamiltonicity of graphs with large minimum degree, Czechoslovak Math. J. 66 (141) (2016), 925–940

2016
[14]

Ning and J

B. Ning and J. Ge, Spectral radius and Hamiltonian properties of graphs, Linear Multi- linear Algebra 63 (8) (2015), 1520–1530

2015
[15]

X. Yan, X. He, L. Feng and W. Liu, Spectral radius and the 2-power of Hamilton cycle, Discrete Math. 346 (1) (2023), 113155

2023
[16]

Zhang, Y

X. Zhang, Y. Li, L. Feng and W. Liu, Maxima of the Q-index: Forbidden rainbow Hamilton paths, matchings and linear forests, Linear Algebra Appl. 720 (2025), 213–244. 22

2025
[17]

Zhou and L

Q. Zhou and L. Wang, Some sufficient spectral conditions on Hamilton-connected and traceable graphs, Linear Multilinear Algebra 65 (2) (2017), 224–234

2017
[18]

Q. Zhou, L. Wang and Y. Lu, Signless Laplacian spectral conditions for Hamilton- connected graphs with large minimum degree, Linear Algebra Appl. 592 (2020), 48–64

2020
[19]

Q. Zhou, L. Wang and Y. Lu, Sufficient conditions for Hamilton-connected graphs in terms of (signless Laplacian) spectral radius, Linear Algebra Appl. 594 (2020), 205–225. 23

2020

Pith tools

Reviewed July 9, 2026 · model on record in the stance chip above.

[1] [10]

X. Liu, B. Ning and T. Wang, Extensions of Erd˝ os’s 1962 theorem on non-Hamiltonian graphs, arXiv:2604.01068v2, 2026.https://doi.org/10.48550/arXiv.2604.01068

work page Pith review arXiv doi:10.48550/arxiv.2604.01068 1962

[2] [1]

J. Ai, H. Lei, B. Ning and Y. Shi, Graph operations and a unified method for Tur´ an- type problems on paths, cycles, and matchings, Canad. J. Math. (2025), 1–27. https: //doi.org/10.4153/S0008414X25101788

work page doi:10.4153/s0008414x25101788 2025

[3] [2]

J. A. Bondy and V. Chv´ atal, A method in graph theory, Discrete Math. 15 (2) (1976), 111–135

work page 1976

[4] [3]

A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Springer, New York, 2012

work page 2012

[5] [4]

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

work page 1986

[6] [5]

Erd˝ os, Remarks on a paper of P´ osa, Magyar Tud

P. Erd˝ os, Remarks on a paper of P´ osa, Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl. 7 (1962), 227–229

work page 1962

[7] [6]

Fiedler and V

M. Fiedler and V. Nikiforov, Spectral radius and Hamiltonicity of graphs, Linear Algebra Appl. 432 (9) (2010), 2170–2173

work page 2010

[8] [7]

X. He, Y. Li and L. Feng, Spectral radius and rainbow Hamilton paths of a graph, Discrete Math. 347 (10) (2024) 114128

work page 2024