Pith. sign in

REVIEW 5 minor 18 references

The minimum degree that forces k edge-disjoint Hamilton cycles under a bipartite-hole bound is Theta of a + k + a k / log(k+2).

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 · grok-4.5

2026-07-11 09:51 UTC pith:46A65727

load-bearing objection Clean order-of-magnitude answer to McDiarmid–Yolov’s packing question; the log term is real and the proofs check out.

arxiv 2607.05027 v1 pith:46A65727 submitted 2026-07-06 math.CO

Edge-disjoint Hamilton cycles under a bipartite-hole condition

Yanan Hu , Chengli Li , Feng Liu This is my paper
classification math.CO MSC 05C4505C0705C69
keywords Hamilton cyclesbipartite holesminimum degreeedge-disjoint packingbipartite-hole-numbergreedy packing
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.

McDiarmid and Yolov showed that minimum degree at least the bipartite-hole number forces a single Hamilton cycle, and gave a stronger linear condition that packs many edge-disjoint ones. They left open whether that packing condition is sharp. This paper defines f(a,k) as the smallest degree that works for every graph whose bipartite-hole number is at most a, and proves that f(a,k) is on the order of a + k + a k / log(k+2). The upper bound is obtained by repeatedly deleting a 2-regular spanning subgraph (a Hamilton cycle) and controlling how much the bipartite-hole number can grow; the McDiarmid–Yolov theorem then produces the next cycle. The matching lower bound comes from three explicit constructions, the strongest of which uses a sparse random graph with no prescribed bipartite hole to force a logarithmic factor into the mixed term. The result therefore answers the 2017 question at the level of order of magnitude: the packing threshold can be relaxed by a log factor, and that improvement is best possible up to constants.

Core claim

For every integers a,k ≥ 2 the function f(a,k)—the least d such that every graph with bipartite-hole number at most a and minimum degree at least d contains k edge-disjoint Hamilton cycles—satisfies c(a+k+ak/log(k+2)) ≤ f(a,k) ≤ C(a+k+ak/log(k+2)) for absolute constants c,C>0.

What carries the argument

The deletion lemma (Lemma 2.1) and the auxiliary function Φ(a,D): after removing a spanning subgraph of maximum degree D the bipartite-hole number grows by at most a controlled logarithmic factor, which is then fed into a greedy packing that invokes the McDiarmid–Yolov Hamiltonicity theorem at each step.

Load-bearing premise

The probabilistic existence of a sparse random graph on N vertices that has no prescribed bipartite hole yet contains fewer edges than k times the number required by any Hamilton cycle, which holds only after absolute constants are chosen large or small enough to make a union bound positive for all a and k.

What would settle it

Either exhibit a single pair a,k ≥ 2 for which some graph with bipartite-hole number a and minimum degree o(ak/log k) still packs k edge-disjoint Hamilton cycles, or prove that every such graph fails to pack them once the degree drops below c ak/log k for a concrete positive c.

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

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

0 major / 5 minor

Summary. The paper determines the order of magnitude of the minimum-degree threshold f(a,k) for packing k edge-disjoint Hamilton cycles in graphs with bipartite-hole number at most a. McDiarmid and Yolov had shown that δ(G)≥k α̃(G)+3(k-1) is sufficient and asked whether the condition is sharp. The authors prove that f(a,k)=Θ(a+k+ak/log(k+2)). The upper bound proceeds from a deletion lemma controlling how α̃ grows under deletion of a bounded-degree spanning subgraph, the McDiarmid–Yolov Hamiltonicity theorem, and a greedy packing argument that yields an explicit sufficient condition in terms of an auxiliary function Φ(a,D). The matching lower bound is assembled from three constructions: a complete bipartite graph, a split graph, and a probabilistic construction of a sparse graph with no prescribed bipartite hole that is then embedded into a larger host graph.

Significance. The result answers, at the level of asymptotic order, an explicit open question of McDiarmid and Yolov on the sharpness of their packing condition. The logarithmic improvement in the mixed term is shown to be best possible by a clean first-moment construction, and the upper bound is obtained by a transparent deletion-plus-greedy argument that also supplies a more explicit sufficient condition (Theorem 1.5). The proofs are elementary, self-contained once the McDiarmid–Yolov Hamiltonicity theorem is taken as a black box, and free of circularity. Absolute constants are not optimised, but the order-of-magnitude determination is complete and of clear interest to the Hamiltonicity and packing communities.

minor comments (5)
  1. In the definition of Φ(a,D) (Definition 1.4) the range of the outer max is written 1≤s≤⌊(a+1)/2⌋; a short parenthetical remark that the case s>t is covered by symmetry would make the subsequent appeal in Lemma 2.2 completely transparent.
  2. Lemma 3.1 invokes an absolute constant C1 such that (D+2)^{1/4}≤C1(1+D/ℓ). The inequality is elementary but the reader must enlarge C1 for small D; a one-line verification for D=1,…,16 would remove any residual doubt.
  3. In Claim 4.3 the bound N/a≤k is used to replace (3eN/a)^{a+1} by (3ek)^{a+1}. Since N=⌊γM⌋ and γ is chosen small, the inequality is correct, but writing N≤γ ak/log(k+2) explicitly before the estimate would make the chain easier to check.
  4. The notation eα(G) is used throughout for the bipartite-hole number; the abstract and introduction also write α̃(G). A single consistent symbol (preferably the tilde version of the original paper) would improve readability.
  5. Page 7, line after “Finally, the probability that both required properties hold…”: the arithmetic 1-1/4-1/10=13/20 is correct, but a brief remark that the two bad events are not independent is unnecessary yet would forestall a pedantic objection.

Circularity Check

0 steps flagged

No significant circularity: self-contained combinatorial argument using external black-box Hamiltonicity plus original deletion lemma and extremal constructions.

full rationale

The derivation of the Theta bound on f(a,k) proceeds by an original deletion lemma (Lemma 2.1, proved by direct probabilistic sampling of an s-set inside a putative hole of G-F) that controls the increase of the bipartite-hole number after removing a bounded-degree spanning subgraph, followed by a greedy application of the external McDiarmid–Yolov Hamiltonicity theorem (Theorem 1.1) and an elementary estimate of the auxiliary function Phi (Lemma 3.1). The matching lower bound is obtained from three explicit constructions (complete bipartite, split graph, and a random auxiliary graph R shown to exist by a uniform first-moment union bound with absolute constants CR, gamma). No quantity is defined in terms of the target threshold and then re-derived; the absolute constants c,C are not fitted to data; self-citations appear only in the related-work paragraph and are not load-bearing. The argument is therefore independent of its own conclusions.

Axiom & Free-Parameter Ledger

1 free parameters · 3 axioms · 1 invented entities

The paper rests on standard finite graph theory, the classical McDiarmid–Yolov Hamiltonicity theorem (cited as a black box), and elementary probabilistic method. Absolute constants arising in the random-graph existence proof are chosen large/small enough for the union bound; they are not fitted to external data. No new physical or combinatorial entities are postulated beyond the auxiliary function Φ used for bookkeeping.

free parameters (1)
  • absolute constants c,C,C0,CR,γ
    Chosen sufficiently large or small so that the union-bound and Markov estimates succeed uniformly for all a,k≥2; their precise numerical values are never needed and are not fitted to any data set.
axioms (3)
  • domain assumption McDiarmid–Yolov Hamiltonicity theorem: δ(G)≥ã(G) implies G is Hamiltonian (for |V|≥3).
    Invoked repeatedly as a black box in the greedy packing argument (proof of Theorem 1.5).
  • standard math Standard first-moment and Markov inequalities for binomial random graphs.
    Used in Claim 4.3 to guarantee existence of the sparse auxiliary graph R.
  • domain assumption Definition of bipartite-hole number ã(G) as the least r=s+t-1 such that G has no (s,t)-bipartite hole.
    Taken from McDiarmid–Yolov and used throughout as the governing parameter.
invented entities (1)
  • auxiliary function Φ(a,D) no independent evidence
    purpose: Upper-bounds the bipartite-hole number after deletion of a D-regular spanning subgraph; used to obtain an explicit sufficient degree condition.
    Defined purely for bookkeeping in the upper-bound argument; no independent existence claim is made for it outside the paper.

pith-pipeline@v1.1.0-grok45 · 13670 in / 2522 out tokens · 20694 ms · 2026-07-11T09:51:45.003516+00:00 · methodology

0 comments
read the original abstract

In 2017, McDiarmid and Yolov introduced the bipartite-hole-number $\widetilde{\alpha}(G)$ and proved that $\delta(G)\ge \widetilde{\alpha}(G)$ forces a Hamilton cycle. They also gave a sufficient condition for packing edge-disjoint Hamilton cycles, and asked whether this condition is sharp or can be relaxed. For integers $a,k\ge 2$, let $f(a,k)$ be the least integer $d$ such that every graph $G$ on at least three vertices with $\widetilde{\alpha}(G)\le a$ and $\delta(G)\ge d$ contains $k$ pairwise edge-disjoint Hamilton cycles. We prove that $f(a,k)=\Theta\left(a+k+\frac{ak}{\log(k+2)}\right).$ The upper bound uses a deletion lemma for the bipartite-hole-number together with the McDiarmid--Yolov Hamiltonicity theorem and a greedy packing argument. The lower bound is obtained from three extremal constructions, the logarithmic one using a sparse random auxiliary graph with no prescribed bipartite hole.

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

18 extracted references · 2 linked inside Pith

  1. [1]

    Alon and J

    N. Alon and J. H. Spencer,The Probabilistic Method, 4th ed., Wiley, Hoboken, 2016

    2016

  2. [2]

    Bollobás,Random Graphs, 2nd ed., Cambridge University Press, Cambridge, 2001

    B. Bollobás,Random Graphs, 2nd ed., Cambridge University Press, Cambridge, 2001

    2001

  3. [3]

    Chen, Hamilton-connected, vertex-pancyclic and bipartite holes,Discrete Math.345(2022), no

    M. Chen, Hamilton-connected, vertex-pancyclic and bipartite holes,Discrete Math.345(2022), no. 12, Paper 113158

    2022

  4. [4]

    Cheng and Y

    K. Cheng and Y. Tang, Extending two results on hamiltonian graphs involving the bipartite-hole- number, arXiv:2511.16099, 2025

    arXiv 2025

  5. [5]

    Christofides, D

    D. Christofides, D. Kühn and D. Osthus, Edge-disjoint Hamilton cycles in graphs,J. Combin. Theory Ser. B102(2012), no. 5, 1035–1060

    2012

  6. [6]

    Chvátal and P

    V. Chvátal and P. Erdős, A note on Hamiltonian circuits,Discrete Math.2(1972), 111–113

    1972

  7. [7]

    G. A. Dirac, Some theorems on abstract graphs,Proc. London Math. Soc. (3)2(1952), 69–81

    1952

  8. [8]

    Draganić, D

    N. Draganić, D. Munhá Correia and B. Sudakov, A generalization of Bondy’s pancyclicity theorem, Combin. Probab. Comput.33(2024), no. 5, 554–563

    2024

  9. [9]

    Ellingham, Y

    M. Ellingham, Y. Huang and B. Wei, Bipartite holes, degree sums and Hamilton cycles, arXiv:2511.00616, 2025

    arXiv 2025

  10. [10]

    F. Knox, D. Kühn and D. Osthus, Edge-disjoint Hamilton cycles in random graphs,Random Struc- tures Algorithms46(2015), no. 3, 397–445. 8

    2015

  11. [11]

    Krivelevich and W

    M. Krivelevich and W. Samotij, Optimal packings of Hamilton cycles in sparse random graphs, SIAM J. Discrete Math.26(2012), no. 3, 964–982

    2012

  12. [12]

    Kühn and D

    D. Kühn and D. Osthus, Hamilton decompositions of regular expanders: applications,J. Combin. Theory Ser. B104(2014), 1–27

    2014

  13. [13]

    Li and F

    C. Li and F. Liu, An Ore-type condition for hamiltonicity in graphs, arXiv:2504.04493, 2025

    Pith/arXiv arXiv 2025

  14. [14]

    C. Li, F. Liu and Y. Tang, Cycles and paths through vertices whose degrees are at least the bipartite- hole-number, arXiv:2506.09750, 2025

    Pith/arXiv arXiv 2025

  15. [15]

    Graph Theory 86(2017), no

    C.McDiarmidandN.Yolov, Hamiltoncycles, minimumdegree, andbipartiteholes,J. Graph Theory 86(2017), no. 3, 277–285

    2017

  16. [16]

    C. St. J. A. Nash-Williams, Edge-disjoint Hamiltonian circuits in graphs with vertices of large valency, inStudies in Pure Mathematics, Academic Press, London, 1971, 157–183

    1971

  17. [17]

    Ore, Note on Hamilton circuits,Amer

    O. Ore, Note on Hamilton circuits,Amer. Math. Monthly67(1960), 55

    1960

  18. [18]

    Q. Zhou, H. Broersma, L. Wang and Y. Lu, A note on minimum degree, bipartite holes, and Hamiltonian properties,Discuss. Math. Graph Theory44(2024), no. 2, 717–726. 9

    2024