A minimum-degree threshold for colour-biased Hamilton cycles in hypergraphs

Felix Christian Clemen; Joseph Hyde; Natalie Behague; Natasha Morrison

REVIEW 2 major objections 4 minor 1 cited by

A minimum-degree threshold for colour-biased Hamilton cycles in hypergraphs

T0 review · 2 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

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

Pith's one-line read Two-coloured 3-graphs with minimum vertex degree above three-quarters of all pairs must contain a tight Hamilton cycle in which one colour appears on a linear surplus of edges.

desk verdict Solid proof of a plausible conjecture, but two load-bearing lemmas are handed over from [18] by 'inspection' — worth a serious referee, conditional on those transfers being written out. read the letter →

arxiv 2607.29628 v2 pith:3N3OD4EH submitted 2026-07-31 math.CO

Natalie Behague , Felix Christian Clemen , Joseph Hyde , Natasha Morrison This is my paper · ORCID

classification math.CO MSC 05C6505C4505C15

keywords colourbiastightHamiltoncycleminimumvertexdegree3-uniformhypergraphswitcherdiscrepancytheoryperfectmatchingthresholdextremal

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

This paper determines the asymptotically optimal minimum vertex degree that forces a two-coloured 3-graph to contain a tight Hamilton cycle with a linear surplus of edges of one colour. The threshold is (3/4 + o(1)) times binom(n,2), coinciding with the threshold for colour-biased perfect matchings and confirming a conjecture from prior work. The proof splits into two regimes: when many 'switchers' exist—pairs of path collections on the same vertices with different colour sums—they can be embedded into a Hamilton cycle and used to tip the colour balance; when switchers are rare, the colouring is shown to be almost determined by a bipartition with one of three simple colour patterns, from which a biased cycle still follows. The degree bound is asymptotically best possible, witnessed by a balanced bipartition construction.

What carries the argument

The proof's central object is the switcher: a pair of collections of vertex-disjoint tight paths that occupy the same vertex set, share the same initial and final pairs, but have different edge-colour sums (Definition 2.7). A Hamilton cycle containing one collection can be locally 'switched' to the other, shifting the colour sum by a fixed amount. The authors show that if the hypergraph contains many ζ-connectable, 7ℓ-bounded switchers, these can be glued into a single tight path via an absorbing-reservoir method adapted from the uncoloured threshold theorem, yielding a biased Hamilton cycle. If switchers are few, a Key Lemma (Lemma 4.1) states that the colouring is almost consistent with on

What would settle it

Try to construct a two-coloured 3-graph on n vertices with minimum vertex degree at least (3/4+α) binom(n,2) for some fixed α>0 in which every tight Hamilton cycle has colour sum O(1) (i.e., no linear surplus of either colour). The paper claims no such graph exists; its own balanced-bipartition example reaches only asymptotically 3/4, so any example strictly above 3/4 would disprove the threshold.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.2: for every α>0 there are δ and n0 such that any red/blue colouring of a 3-uniform hypergraph H on n≥n0 vertices with minimum vertex degree δ1(H) ≥ (3/4+α) binom(n,2) contains a tight Hamilton cycle with at least (1/2+δ)n edges of the same colour. The constant 3/4 is asymptotically best possible: in a balanced partition of the vertices into two parts of equal size, taking all triples that meet both parts as edges and colouring them red when they contain exactly two vertices of the first part and blue otherwise, the minimum vertex degree is asymptotically 3/4 binom(n,2) yet every tight Hamilton cycle has colour sum bounded by a constant. Hence the colour-biased

Load-bearing premise

The proof's success in the 'many switchers' case depends on two absorbing-path constructions from the uncoloured threshold theorem still working when a set of linearly many vertices is avoided; the paper asserts this by inspection rather than proving it, so the whole case rests on that transfer being valid.

Editorial extensions

If this is right

Any two-coloured 3-graph with minimum vertex degree at least (3/4+α) binom(n,2) contains a tight Hamilton cycle with at least (1/2+δ)n edges of one colour, for some δ>0 depending only on α.
The asymptotic thresholds for colour-biased tight Hamilton cycles and colour-biased perfect matchings coincide in two-coloured 3-graphs, resolving a conjecture in the literature.
The degree condition is best possible: the balanced-bipartition construction asymptotically attains 3/4 binom(n,2) while keeping every tight Hamilton cycle colour-balanced up to a constant.
For uniformities k≥4 the thresholds diverge: the paper exhibits a construction showing the colour-biased Hamilton cycle threshold lies strictly above the perfect matching threshold, and conjectures the exact constant d_k.

Reading between the lines

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

The 'few switchers ⇒ structural colouring, many switchers ⇒ local flips' dichotomy is likely a general template for discrepancy problems in dense hypergraphs; analogues may hold for r-colourings with r>2 or for other spanning structures.
A concrete next test is the loose Hamilton cycle: the authors conjecture that the uncoloured minimum vertex degree threshold of (7/16+α) binom(n,2) for 3-graphs should force a colour-biased loose Hamilton cycle; the switcher machinery might transfer because loose cycles can be decomposed into edge-disjoint tight paths.
The proof leaves one technical transfer open: two auxiliary lemmas (an absorbing path and an almost-spanning path) are asserted to hold with a linearly sized additional avoided set by 'inspection of the proof' of the uncoloured case; a reader who wants to rely on Theorem 1.2 should verify that transfer, since the many-switchers branch depends on it.
The structural Key Lemma may be reusable: a switcher-free two-coloured 3-graph of density above 3/4 is nearly a 'blow-up' of one of three extremal colour patterns, which could help attack related subgraph counts or algorithmic discrepancy questions.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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 result is real: the asymptotically optimal minimum vertex degree threshold for a colour-biased tight Hamilton cycle in two-coloured 3-graphs, confirming the Hàn et al. conjecture and showing that the min-vertex-degree thresholds for colour-biased perfect matchings and tight Hamilton cycles coincide. That is a worthwhile theorem in extremal combinatorics, and the proof strategy is coherent: adapt the Reiher–Rödl–Ruciński–Schacht–Szemerédi robust-link machinery to the minimum vertex degree setting, handle the few-switchers case with a strong structural Key Lemma, and build a colour-biased cycle from many switchers. The paper is mostly well-written, and the Key Lemma argument in Section 4 is genuinely new and detailed. The concluding remarks also contain a useful construction for k ≥ 4, which sharpens the earlier example from [14].

The soft spots are concentrated in Section 3. Lemmas 3.3 and 3.4 are asserted to follow from [18, Prop 2.9] and [18, Lemma 7.1] by 'inspection of the proof' after forbidding an additional set of vertices. That is not a proof as written. The avoided sets are linearly large in n — up to 2ϑ∗²n and 100δℓ²n — and the reservoir and absorbing arguments in [18] typically rely on random choices over the whole vertex set, so it is not automatic that the constructions survive when those vertices are removed. The connecting path count in Lemma 2.10 does show that there is room to avoid the switcher vertices, but the absorbing path itself is the load-bearing black box. Similarly, Proposition 2.4(iii) is deferred to [18, Prop 2.3], even though the appendix proves a more general version of (i) and (ii). This is a smaller gap because the robustness property is quite standard, but it is still deferred.

If those transfers fail, the many-switchers branch collapses. I would be surprised if they fail — the paper's overall structure suggests the modifications are straightforward — but the authors need to write them out. This is a paper that deserves peer review, not a desk rejection, precisely because the central claim is important and the rest of the proof is careful. I would send it to a referee with the instruction to focus on Section 3 and the deferred robustness proof. If those gaps are filled, the result stands.

Referee Report

2 major / 4 minor

Summary. The paper determines, asymptotically, the minimum vertex degree that forces a colour-biased tight Hamilton cycle in a two-coloured 3-graph. Theorem 1.2 states that for every α>0 there exist δ,n0>0 such that every red/blue coloured 3-graph H on n≥n0 vertices with δ1(H) ≥ (3/4+α) binom(n,2) contains a tight Hamilton cycle with at least (1/2+δ)n edges of one colour. The constant 3/4 is shown best possible by a two-partite construction. The proof splits into a 'many switchers' case, where reservoir, absorbing-path and almost-spanning-path tools adapted from Reiher–Rödl–Ruciński–Schacht–Szemerédi are used to build a Hamilton cycle whose colour sum can be switched, and a 'few switchers' case, where a Key Lemma (Lemma 2.9 / Lemma 4.1) classifies almost all robust edges into one of three bipartite colour patterns; Theorem 1.1 then supplies a nearly unbiased Hamilton cycle avoiding the exceptional edges. An appendix proves a generalised robust-link-graph proposition.

Significance. If the missing proof details are supplied, the result confirms a conjecture of Hàn, Lang, Marciano, Pavez-Signé, Sanhueza-Matamala, Treglown and Zárate-Guerén and gives the asymptotically optimal minimum-vertex-degree threshold for colour-biased tight Hamilton cycles in 3-graphs. The sharpness construction and the substantial self-contained proof of the Key Lemma are valuable, and there is no circularity: the theorem is derived from external results and does not assume the conjecture it confirms. The main caveat is that three load-bearing components are not proved in the manuscript: Lemmas 3.3 and 3.4 are transferred from [18] by 'inspection of the proof', and Proposition 2.4(iii) is explicitly deferred to [18, Prop. 2.3].

major comments (2)

[Section 3, Lemmas 3.3 and 3.4] Lemma 2.10, the many-switchers case, rests on Lemmas 3.3 and 3.4. Lemma 3.3 is asserted to follow from [18, Prop. 2.9] by 'inspection of the proof' when an additional set R' of size at most 2ϑ_*^2 n is avoided, and Lemma 3.4 from [18, Lemma 7.1] when an additional linearly sized set W is avoided. These avoided sets are not vanishingly small, and the original reservoir/absorbing constructions in [18] select vertices over the whole vertex set; forbidding such sets can interfere with robustness and connectability guarantees. No modified proof or detailed verification is supplied. Since the many-switchers branch collapses without these lemmas, this is load-bearing and must be fixed before the proof can be considered complete.
[Appendix A, Proposition 2.4(iii)] The robustness property (iii) is used throughout the paper (Definitions 2.3 and 2.6, Lemma 4.13, Lemma 3.1). The appendix proves only properties (i) and (ii) and explicitly says that property (iii) is 'defer[red] to the proof of [18, Prop. 2.3]'. Because Proposition A.1 is proved by a different partition argument, it is not automatic that the produced subgraphs are (β,ℓ)-robust with the stated parameters. Please include the missing proof or a precise reference with a parameter verification.

minor comments (4)

[Section 5, Proof of Theorem 1.2] The sentence 'First, apply Lemma 2.10 to obtain δ' is imprecise: δ is already fixed by Setup 2.5. Rephrase to say that Lemma 2.10 is applied with the δ from the hierarchy.
[Definition 4.7] The term 'non-agreeable' is defined positively (a component is non-agreeable if there exists a labelling with the stated properties). An explicit definition of 'agreeable component' would improve readability and avoid confusion in Lemma 4.9.
[Proof of Lemma 2.10] The letter W is used both for the tight path containing the switchers and for the vertex set to be avoided in Lemma 3.4. Since |V(W)| is the quantity that matters, a notational clarification would help.
[Appendix A, Proposition A.1] The sentence 'The proof follows the exact same approach as [18, Prop. 2.3]' is misleading because the appendix then proves only (i) and (ii). Please state explicitly which parts are proved and which are imported.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof derives Theorem 1.2 from external results and independent structural lemmas.

full rationale

The paper's central claim (Theorem 1.2) is a new asymptotic threshold for colour-biased tight Hamilton cycles. The proof splits into regimes: if there are many switchers, Lemma 2.10 builds a colour-biased Hamilton cycle using the switchers' colour sums; if there are few switchers, the Key Lemma (Lemma 2.9) gives a structural bipartition of the robust-edge colouring. Neither regime assumes the target threshold. The main external inputs are results from Reiher, Rödl, Ruciński, Schacht, and Szemerédi [18], an independent published paper, used both for the uncoloured Hamilton-cycle threshold (Theorem 1.1) and for the reservoir/absorbing-path framework (Lemmas 3.1–3.4). The paper does defer proofs of Lemmas 3.3 and 3.4 to 'inspection of the proof' of [18, Prop. 2.9] and [18, Lemma 7.1] when avoiding an extra vertex set. This is a real verification gap and a robustness risk, but it is not circularity: the cited results are external, not authored by the present authors, and they do not encode the colour-bias conclusion being proved. Likewise, Proposition 2.4 is modelled on [18, Prop. 2.3] and defers the robustness property to the same external source; again this is reliance on independent work, not self-citation or fitting. No parameter is fitted to the target quantity, no prediction is a renamed input, and no load-bearing step reduces by definition to the threshold or to a self-citation chain. The lower-bound construction in the introduction is standard and does not enter the proof. The manuscript asserts a conjecture of [14] and proves it; proving a conjecture is not circular unless the proof assumes the conjecture, which it does not. Overall, the derivation chain is independent of its conclusions, with the caveat that some transferred lemmas from [18] are not fully re-proved in the modified settings.

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

The proof builds on external theorems, primarily from [18], and standard extremal graph theory. No ad hoc parameters are fitted to data and no new entities are postulated. The main contribution is a careful combination of existing tools to handle the minimum vertex degree setting.

assumptions (5)

domain assumption Theorem 1.1 (Reiher, Rödl, Ruciński, Schacht, Szemerédi): every 3-graph with δ1 ≥ (5/9+α) C(n,2) contains a tight Hamilton cycle.
Used in Section 5 to find a Hamilton cycle in the robust subgraph G after deleting bad edges.
domain assumption Robust link subgraphs exist (Proposition 2.4 / [18, Prop. 2.3]) satisfying the stated vertex/edge bounds and (β,ℓ)-robustness.
Stated as Proposition 2.4. Properties (i) and (ii) are proved in Appendix A, but property (iii) is deferred to [18, Prop 2.3]. The robust subgraphs R_v are the foundation of the connectability and switcher arguments.
domain assumption Connecting, reservoir, absorbing and almost-spanning lemmas from [18] (Prop 2.6, 2.7, 2.9, Lemma 7.1) extend to the modified settings used in Lemma 2.10.
Section 3 uses these black-box results. The paper claims by 'inspection of the proof' that they hold when an extra set of vertices is avoided, but does not provide the modified proofs.
standard math Erdős–Stone–Simonovits theorem implies a dense graph contains any fixed tree T.
Used in Lemma 4.9 to find a connected component of hat(R_u)∩hat(R_v) containing a copy of T.
domain assumption Fact 4.3 from [18]: at most ρ n^3 triples (x,y,z) have xy ∈ R_z and xy fails to be ρ-connectable.
Used in Section 4 to bound non-extendable vertices and ε-good edges.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A minimum-degree threshold for colour-biased Hamilton cycles in hypergraphs." pith.science (2026). https://pith.science/paper/3N3OD4EH

@misc{pith2026260729628,
  author       = {Pith},
  title        = {Pith review of: A minimum-degree threshold for colour-biased Hamilton cycles in hypergraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3N3OD4EH}},
  note         = {Machine review of arXiv:2607.29628}
}

abstract

We determine the asymptotically best possible minimum vertex degree condition forcing a two-coloured $3$-graph to contain a colour-biased tight Hamilton cycle. This confirms a conjecture of H\`an, Lang, Marciano, Pavez-Sign\'e, Sanhueza-Matamala, Treglown and Z\'arate-Guer\'en.

Figures

Figures reproduced from arXiv: 2607.29628 by the authors.

**Figure 2.** Illustration of the majority of the robust edges in the three cases from Lemma 2.9. [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** A ‘short’ switcher where each of S and S ′ contains two tight 3-paths on three edges. The second type of switcher is a ‘long’ switcher, where each of S and S ′ contains one long path on 3 2 (ℓ + 3) edges and ℓ short paths on three edges (see [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

Figures from the paper (5 more)

**Figure 4.** Figure 4: A ‘long’ switcher. There are 1 2 (ℓ + 3) highlighted (in red) vertices on each of the long paths P1 and P ′ 1 , which each contain 3 2 (ℓ+ 3) edges. Note that, although the figure does not show it, for 2 ≤ i ≤ ℓ + 1, corresponding short paths Pi , P′ i only differ in t…

**Figure 5.** Figure 5: The tree T on ten vertices Claim 4.9.3. Let C be a connected component of Rˆ u ∩ Rˆ v containing a copy of T . Then f(e) = f(e ′ ) for all e, e′ ∈ E(C). Proof of Claim. Let T be a copy of T in C. Applying Claim 4.9.2, for the edges of T eight times gives f(z3z4) = f(z6…

**Figure 6.** Figure 6: The vertices and edges that must be present in [PITH_FULL_IMAGE:figures/full_fig_p017_6.png]

**Figure 7.** Figure 7: The 3-uniform path Q⃗u built from the path Q in T u∈U Rˆ u. We define two potential switchers for each tuple ⃗u = (u1, . . . , u(ℓ+3)/2) of (ℓ+3)/2 distinct vertices in U. First consider the following two sets of paths: S⃗u = (w0w1xyP x′w ′ )⃗u ∪ Q ′ y ∪ [ 1≤i≤ℓ−1 Q ′ …

**Figure 8.** Figure 8: The vertices and edges that must be present in [PITH_FULL_IMAGE:figures/full_fig_p021_8.png]

Discussion (0). Continue with ORCID 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

Layer barriers for colour-biased tight Hamilton cycles
math.CO 2026-08 accept novelty 8.0 of 10

A new family of layer barriers for colour-biased tight Hamilton cycles gives a counterexample to the recent conjecture of Behague, Clemen, Hyde and Morrison on minimum vertex degree thresholds.

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.