Pith. sign in

REVIEW 3 major objections 1 minor 1 cited by

Extensions of Erd\H{o}s's 1962 theorem on non-Hamiltonian graphs

T0 review · 3 major / 1 minor · reviewed 2026-07-13 · grok-4.5

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

Pith's one-line read A single theorem unifies Erdős’s 1962 edge bound for non-Hamiltonian graphs with its spectral analogues.

desk verdict Wrong manuscript body: abstract claims a common Erdős–spectral generalization and solutions to post-2016 open problems, but the supplied text is an unrelated hep-ex paper on Blobel unfolding, so nothing can be checked. read the letter →

arxiv 2604.01068 v2 pith:MBJNLWTA submitted 2026-04-01 math.CO

Xu Liu , Bo Ning , Tao Wang This is my paper
classification math.CO MSC 05C3505C5005C45
keywords non-HamiltoniangraphsErdőstheoremextremalgraphtheoryspectralproblemsminimumdegreejoinsHamiltonicity
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

In 1962 Erdős determined the maximum number of edges an n-vertex graph with minimum degree at least k can have without containing a Hamilton cycle. This paper extends that classical result into a common framework that covers both the ordinary edge count and spectral parameters (such as the largest eigenvalue) under the same degree constraint. The authors work with a general extremal quantity: the maximum of a graph parameter P over n-vertex graphs of minimum degree at least k that fail a prescribed property H. Their first theorem recovers Erdős’s original bound and the known spectral versions of it from one argument. As direct applications they completely settle several open problems raised since 2016 and improve nearly all earlier quantitative results in the same circle of ideas. A sympathetic reader cares because the same extremal constructions now serve both combinatorial and spectral questions, replacing a patchwork of separate theorems with one transparent template.

What carries the argument

The degree-constrained extremal function ex_P(n, H; δ ≥ k) and its extremal families EX_P, realized by classical join constructions of the form H1 ∨ H2. That single template is shown to optimize both edge number and spectral parameters for non-Hamiltonian graphs of minimum degree at least k, carrying the unified argument.

What would settle it

An explicit n-vertex non-Hamiltonian graph of minimum degree at least k whose spectral radius (or other targeted spectral parameter) strictly exceeds that of the classical Erdős join construction would refute the claimed common extremal family.

Watch

Extended reading notes

Core claim

The authors prove a common generalization of Erdős’s 1962 theorem on the maximum number of edges in a non-Hamiltonian n-vertex graph with minimum degree at least k and of the spectral analogues of that theorem. In the language of the extremal quantities ex_P(n, H; δ ≥ k), a single family of constructions simultaneously extremizes both the classical edge count and the spectral parameters under study.

Load-bearing premise

The argument assumes that the same classical join-type constructions that maximize the number of edges also maximize the spectral parameters under the minimum-degree constraint, so one template covers both settings.

Editorial extensions

If this is right

  • Open problems on spectral extremal non-Hamiltonian graphs raised since 2016 receive complete solutions.
  • Nearly all earlier quantitative bounds in this degree-constrained spectral direction are improved by the new common theorem.
  • The same extremal families serve both combinatorial edge counts and spectral parameters for non-Hamiltonicity under δ ≥ k.
  • The framework supplies a reusable template for other feasible graph parameters under a minimum-degree constraint.

Reading between the lines

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

  • The same join constructions may remain extremal for other spectral invariants (for example Laplacian or signless-Laplacian radii) under the same degree constraint.
  • The unified template suggests a systematic route to degree-constrained spectral Turán-type problems for forbidden properties beyond non-Hamiltonicity.
  • If extremal families stay join-based across a wider class of parameters, small-order computer searches for extremal examples become less necessary.
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.

Referee Report

3 major / 1 minor

Summary. The manuscript claims to extend Erdős’s 1962 theorem on the maximum number of edges in an n-vertex non-Hamiltonian graph with minimum degree at least k. It introduces the extremal quantities ex_P(n, H; δ ≥ k) and the corresponding families EX_P, and asserts that a single result simultaneously generalizes the classical edge-extremal theorem and its spectral analogues (via the same join-type constructions H1 ∨ H2). Direct applications are said to resolve open problems raised since 2016 and to improve nearly all related prior results. The supplied full-text body, however, is an unrelated hep-ex paper on Blobel’s Regularized Unfolding (arXiv:2604.01069) and contains none of the combinatorial statements, constructions, or proofs.

Significance. If the claimed common generalization were correctly proved, it would be a substantial contribution to extremal and spectral graph theory: a single extremal template that simultaneously optimizes edge count and spectral parameters under a minimum-degree constraint would unify several lines of work and close multiple open problems. The abstract’s framing in terms of feasible parameters (ALNS2023) is natural and potentially influential. Because the body of the submission is a completely different manuscript, none of these claims can be verified or credited.

major comments (3)
  1. The full manuscript text provided is not the paper announced by the title, abstract, and arXiv identifier 2604.01068. It is instead the complete text of “Blobel’s Regularized Unfolding” (arXiv:2604.01069, hep-ex). Consequently every mathematical claim of the abstract—existence of a common generalization of Erdős’s 1962 theorem and its spectral analogues, the identity of the extremal families EX_P, and the resolution of post-2016 open problems—is unsupported by any theorem, construction, or proof in the submitted body.
  2. The load-bearing modeling premise of the abstract (that the same classical join constructions H1 ∨ H2 realize the extremal families for both the edge count and the spectral parameters under the constraint δ ≥ k) cannot be checked. Without the constructions, eigenvalue comparisons, or extremal-family arguments, it is impossible to confirm that the maximizers coincide, and therefore impossible to confirm that a single theorem yields the claimed complete solutions.
  3. No statements, proofs, or numerical tables corresponding to the combinatorial claims appear anywhere in the supplied text. The paper as submitted therefore fails the most basic requirement of a research article: that the body substantiate the abstract.
minor comments (1)
  1. Even the abstract alone contains no explicit statement of the main theorem, no definition of the spectral parameters under consideration, and no list of the open problems claimed to be solved; these omissions would need correction in any future resubmission of the correct manuscript.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity can be exhibited: the supplied full text is an unrelated hep-ex manuscript (Blobel unfolding), and the Erdős abstract alone shows only standard extremal definitions with no self-definitional or fitted-as-prediction loop.

full rationale

The target abstract defines the usual extremal quantities ex_P(n, H; δ ≥ k) and EX_P, recalls Erdős’s 1962 edge-extremal theorem for non-Hamiltonian graphs of minimum degree k, and claims a common generalization that also covers spectral analogues, with applications to open problems since 2016. Those statements are ordinary extremal-graph-theory language; nothing in the abstract equates a claimed prediction to a fitted input, defines a quantity in terms of itself, or rests a uniqueness claim solely on an unverified self-citation by the present authors. The CACHEABLE full-text blob is an entirely different paper (Blobel’s Regularized Unfolding, arXiv:2604.01069), so no derivation chain, construction, or eigenvalue comparison from 2604.01068 is available to inspect. Under the rule that circularity may be flagged only when a specific reduction can be quoted and exhibited, the only honest finding is score 0 with empty steps. Residual dependence on the classical Erdős join template is ordinary citation of prior work, not circularity.

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

Abstract-only review of a pure extremal graph theory claim. No free numerical parameters appear. Background axioms are the classical Erdős 1962 non-Hamiltonian edge bound under minimum degree, standard spectral graph theory comparisons, and the join/disjoint-union extremal constructions usual in this area. No new physical entities. The main uncheckable load is that the same extremal families optimize both edge and spectral parameters under δ ≥ k.

assumptions (4)
  • domain assumption Erdős’s 1962 theorem: maximum edges in an n-vertex non-Hamiltonian graph with minimum degree at least k is achieved by a standard join-type construction.
    Stated as the classical starting point in the abstract; all claimed extensions rest on this baseline.
  • domain assumption Spectral analogues of the Erdős bound (eigenvalue versions of non-Hamiltonian extremal problems under degree constraints) are valid comparison points that a common generalization should recover.
    Abstract claims a common generalization of the edge theorem and its spectral analogues; those analogues are taken as established prior work.
  • standard math The extremal quantity ex_P(n, H; δ ≥ k) and families EX_P are well-defined for the parameters P and properties H under study (including non-Hamiltonicity).
    Definitional setup in the abstract; standard in extremal graph theory.
  • domain assumption Open problems raised in the literature since 2016 in this direction are correctly stated and remain open prior to this work.
    Abstract claims complete solutions to those problems; their status is external to the abstract text.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Extensions of Erd\H{o}s's 1962 theorem on non-Hamiltonian graphs." pith.science (2026). https://pith.science/paper/MBJNLWTA

@misc{pith2026260401068,
  author       = {Pith},
  title        = {Pith review of: Extensions of Erd\Hos's 1962 theorem on non-Hamiltonian graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MBJNLWTA}},
  note         = {Machine review of arXiv:2604.01068}
}
abstract

For a positive integer $k$, a graph property $\mathcal{H}$, and a graph parameter $\mathcal{P}$, let $\operatorname{ex}_{\mathcal{P}}(n, \mathcal{H}; \delta \geq k)$ denote the maximum value of $\mathcal{P}$ over all $n$-vertex graphs with minimum degree at least $k$ that do not possess the property $\mathcal{H}$. The corresponding extremal families are denoted by $\operatorname{EX}_{\mathcal{P}}(n, \mathcal{H}; \delta \geq k)$. For two disjoint graphs $H_1$ and $H_2$, let $H_1 \cup H_2$ denote their disjoint union, and let $H_1 \vee H_2$ denote their join. In 1962, Erd\H{o}s established a classical theorem on the maximum number of edges in a non-Hamiltonian graph with prescribed order and minimum degree. Motivated by recent work on feasible graph parameters in \cite{ALNS2023}, we prove several extensions of Erd\H{o}s's 1962 theorem on non-Hamiltonian graphs. The first result gives a common generalization of the extremal theorem due to Erd\H{o}s and its spectral analogues. As direct applications, we obtain complete solutions to open problems raised in the literature since 2016, thereby improving nearly all related prior results in this direction.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

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

    math.CO 2026-07 accept novelty 5.0 of 10

    The spectral Moon–Moser thresholds for non-Hamiltonian balanced bipartite graphs and non-traceable nearly balanced bipartite graphs remain sharp in the linear range n ≥ 2k (resp. n ≥ 2k+1), with unique extremal graphs.

Reference graph

Works this paper leans on

19 extracted references · cited by 1 Pith paper

  1. [1]

    Bayesian-based iterative method of i mage restoration

    W. H. Richardson. “Bayesian-based iterative method of i mage restoration”. In: �� ���� ���� ��� 62 (1972), pp. 55–59. 14

    1972

  2. [2]

    An iterative technique for the rectification of observed distributions

    L. B. Lucy. “An iterative technique for the rectification of observed distributions”. In: ������� ��79 (1974), pp. 745–754

    1974

  3. [3]

    A multidimensional unfolding method ba sed on Bayes’ theorem

    G. D’Agostini. “A multidimensional unfolding method ba sed on Bayes’ theorem”. In: ����� �������� ����� � 362 (1995), pp. 487–498

    1995

  4. [4]

    Solution of incorrectly formulated pro blems and the regularization method

    A. N. Tikhonov. “Solution of incorrectly formulated pro blems and the regularization method”. In: ������ ����� �����4 (1963), pp. 1035–1038

    1963

  5. [5]

    TUnfold: an algorithm for correcting migra tion effects in high energy physics

    S. Schmitt. “TUnfold: an algorithm for correcting migra tion effects in high energy physics”. In: ����� 7 (2012), T10003. arXiv: ��������� �����������������

    2012

  6. [6]

    V. Blobel. ��������� ������� �� ����������� ������� �����������. Tech. rep. DESY 84-118. 1985

    1985

  7. [7]

    An unfolding method for high energy physics e xperiments

    V. Blobel. “An unfolding method for high energy physics e xperiments”. In: �������� ����������� ���������� �� �������� �������. Ed. by M. R. Whalley and L. Sherpa. 2002, pp. 258–267. arXiv: ��������������

    2002

  8. [8]

    C. de Boor. � ��������� ����� �� �������. Vol. 27. Applied Mathematical Sciences. New York: Springer-Verlag, 1978

    1978

Show all 19 references
  1. [9]

    V. Blobel. ���� ���������. Lectures at the Terascale Statistics School, DESY, Ham- burg. 2010. ��� : ��������������������������������������������������� ����

    2010

  2. [10]

    P. C. Hansen. �������� ������� ��������� ������� ��� ����������. Fundamentals of Algorithms. Philadelphia: SIAM, 2010

    2010

  3. [11]

    Statistical inverse probl ems: discretization, model reduction and inverse crimes

    J. Kaipio and E. Somersalo. “Statistical inverse probl ems: discretization, model reduction and inverse crimes”. In: �� ������� ����� ����� 198 (2007), pp. 493– 504

    2007

  4. [12]

    Comparison of unfolding methods usin g RooFitUnfold

    L. Brenner et al. “Comparison of unfolding methods usin g RooFitUnfold”. In: ���� �� ���� ����� � 35 (2020), p. 2050145. arXiv: ���������� �����������������

    2020

  5. [13]

    Uncertainty quantification in unfolding e lementary particle spectra at the Large Hadron Collider

    M. Kuusela. “Uncertainty quantification in unfolding e lementary particle spectra at the Large Hadron Collider”. PhD thesis. EPFL, 2016

    2016

  6. [14]

    The L-curve and its use in the numerical tr eatment of inverse prob- lems

    P. C. Hansen. “The L-curve and its use in the numerical tr eatment of inverse prob- lems”. In: ������������� ������� �������� �� �����������������. Ed. by P. Johnston. WIT Press, 2001, pp. 119–142

    2001

  7. [15]

    Unfolding algorithms and tests using RooUnfo ld

    T. Adye. “Unfolding algorithms and tests using RooUnfo ld”. In: ����������� �� ��� ������� ���� �������� . Ed. by H. B. Prosper and L. Lyons. 2011, pp. 313–318. arXiv: ��������� �����������������

    2011

  8. [16]

    Statistical unfolding of elementary particle spec- tra: empirical Bayes estimation and bias-corrected uncert ainty quantification

    M. Kuusela and V. M. Panaretos. “Statistical unfolding of elementary particle spec- tra: empirical Bayes estimation and bias-corrected uncert ainty quantification”. In: ���� ����� �����9 (2015), pp. 1671–1705

    2015

  9. [17]

    Fully Bayesian unfolding

    G. Choudalakis. “Fully Bayesian unfolding”. In: (2012 ). arXiv: ��������� ��������

    2012

  10. [18]

    OmniFold: a method to simultaneou sly unfold all observables

    A. Andreassen et al. “OmniFold: a method to simultaneou sly unfold all observables”. In: ����� ���� �����124 (2020), p. 182001. arXiv: ���������� ��������

    2020

  11. [19]

    Croft and Y

    V. Croft and Y. Haddad. ����������� ������������������ ����������� ���������. Ver- sion 0.2.3. 2018. ���: ���������������������� . 15

    2018

Pith tools

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