Layer barriers for colour-biased tight Hamilton cycles

Caihong Yang; Qinfei Tang; Zijian Deng

REVIEW 1 major objections 3 minor 13 references

Layer barriers for colour-biased tight Hamilton cycles

T0 review · 1 major / 3 minor · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read A one-parameter family of red-blue $k$-graphs forces every tight Hamilton cycle to be perfectly colour-balanced, and at $k=17$ the minimum vertex degree exceeds the conjectured threshold $d_{17}$.

desk verdict A clean, checkable counterexample to a conjectured vertex-degree threshold; the only caveat is that the refutation hinges on the exact wording of the quoted conjecture. read the letter →

arxiv 2608.12013 v2 pith:VY5AGQL7 submitted 2026-08-12 math.CO

Zijian Deng , Qinfei Tang , Caihong Yang This is my paper · ORCID

classification math.CO MSC 05C6505C3805C15

keywords uniformhypergraphstightHamiltoncyclescolourdiscrepancyminimumvertexdegreelayerbarriersred-blueedge-colouringcolour-balancedcounterexample

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 constructs, for every uniformity $k\ge 3$ and every parameter $a\in\{0,\dots,k-1\}$, arbitrarily large red-blue $k$-uniform hypergraphs that contain a tight Hamilton cycle yet have every tight Hamilton cycle perfectly colour-balanced: exactly $n/2$ red and $n/2$ blue edges. The construction is a layer barrier: the vertex set is split into two parts, and edges whose intersection with the smaller part has one of two forbidden sizes are deleted. The asymptotic minimum vertex degree of the $a$-th barrier is $d_{k,a}$ as in (2), and the boundary case $a=0$ reproduces the previously known extremal example with degree $d_k$. The paper's main point is that interior layers are strictly denser: at $k=17$, $a=8$ gives $d_{17,8}=5761/8192\approx0.703247$, exceeding the conjectured $d_{17}\approx0.699277$, so Conjecture 1.1, quoted from Conjecture 6.1 of the cited reference [3], is false. For large $k$, choosing $a\approx k/2$ makes the barrier density $1-O(k^{-1/2})$, far above the limit of $d_k$.

What carries the argument

The layer barrier: fix two forbidden intersection sizes, $a-1$ and $a+2$, where the type of a $k$-set is its intersection size with $B$. Consecutive edges of a tight cycle are consecutive windows of length $k$ in a cyclic vertex order, so their types differ by at most 1; the forbidden layers therefore confine all types of any tight cycle to one of the three intervals $\{0,\dots,a-2\}$, $\{a,a+1\}$, $\{a+3,\dots,k\}$. Since the average type over all $n$ edges equals $k|B|/n=a+1/2$, the cycle cannot live in the lower or upper interval, so every edge has type $a$ or $a+1$; counting edges of type $a+1$ against the average gives exactly $n/2$ blue edges and $n/2$ red edges. Hamiltonicity is supplied by a $2k$-periodic binary sequence with $2a+1$ ones per period.

What would settle it

Compare the statement of Conjecture 6.1 in the cited reference [3] with the version quoted here as Conjecture 1.1; if the original carries any extra hypothesis (a different degree notion, a restriction on $n$, or an additional structural condition), then the $k=17$, $a=8$ construction may not be a counterexample. If the statements match exactly, the computation $d_{17,8}-d_{17} = \frac{8}{17}(\frac{33}{34})^{15} - \frac{2431}{8192} > \frac{39}{10000}$ settles it.

Watch

Extended reading notes

Core claim

Fix $k\ge3$, $a\in\{0,\ldots,k-1\}$, and let $n$ be divisible by $2k$. Partition the vertex set into $A\cup B$ with $|B|=(2a+1)n/(2k)$, and put a $k$-set $e$ into the hypergraph exactly when its type $|e\cap B|$ is neither $a-1$ nor $a+2$; colour type-$a$ edges red and type-$a+1$ edges blue. The paper proves that every tight Hamilton cycle in this $k$-graph has all edge types in $\{a,a+1\}$, which by an averaging count forces exactly $n/2$ edges of each type, hence colour sum zero, while a $2k$-periodic binary word with $2a+1$ ones per period exhibits a genuine tight Hamilton cycle. The asymptotic relative minimum vertex degree equals $d_{k,a}=1-\max\{P(X_{k,a}\in\{a-1,a+2\}),P(X_{k,a}\in\{a-2,a+1\})\}$ with $X_{k,a}\sim\operatorname{Bin}(k-1,(2a+1)/(2k))$. For $k=17$, $a=8$, binomial symmetry gives $d_{17,8}=5761/8192$, and the paper verifies $d_{17,8}-d_{17}>39/10000$, so with $\alpha=3/1000$ arbitrarily large counterexamples to Conjecture 1.1 exist. As $k\to\infty$ the interior choice $a\approx k/2$ gives $1-d_{k,a}=O(k^{-1/2})$.

Load-bearing premise

The counterexample refutes Conjecture 1.1 only if that conjecture is exactly as quoted from the cited reference [3]: same definition of minimum vertex degree $\delta_1$, same constant $d_{17}$, and no hidden condition excluding the case $n$ divisible by 34.

Editorial extensions

If this is right

Conjecture 1.1, quoted from Conjecture 6.1 of the cited reference [3], is false: for $k=17$ any threshold forcing a colour-biased tight Hamilton cycle must lie at least at $5761/8192\approx0.703247$, above the conjectured $d_{17}\approx0.699277$.
For every $k\ge3$ and every $a$, the layer barrier $H_{k,a}(n)$ shows that relative minimum vertex degree $d_{k,a}$ is compatible with perfect colour balance, so a true sufficient threshold must exceed every $d_{k,a}$ for the corresponding $k$.
For large $k$, any sufficient threshold must be at least $1-O(k^{-1/2})$, approaching 1, whereas the boundary threshold $d_k$ tends only to $1-e^{-1/2}/2$.
The construction contains a tight Hamilton cycle, so the obstruction is genuinely about colour discrepancy rather than about the failure of Hamiltonicity.

Reading between the lines

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

The two-forbidden-layer mechanism might carry over to $r$-colourings or to other spanning structures such as perfect matchings, where deleting further layers could yield even denser colour-balanced barriers; this is a testable extension, not a claim of the paper.
The large-uniformity gap suggests that for red-blue $k$-graphs the true threshold for colour-biased tight Hamilton cycles is asymptotically much closer to 1 than to the uncoloured Hamiltonicity threshold, a contrast that could be probed in random hypergraphs.
The binomial symmetry at $k=17$, $a=8$ makes $d_{17,8}=1-2^{-16}(\binom{16}{7}+\binom{16}{10})$ a closed rational; searching other uniformities for a similar symmetry might produce an even larger gap over $d_k$.

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

Solid, short paper. It constructs a one-parameter family of red-blue k-uniform hypergraphs that are layer barriers: every tight Hamilton cycle is perfectly colour-balanced, yet the construction contains at least one tight Hamilton cycle. The boundary case a=0 reproduces the Behague-Clemen-Hyde-Morrison obstruction; the new interior layers are genuinely denser, and at k=17, a=8 the relative minimum vertex degree is ~0.7032473, above the conjectured d_17 ~0.6992772. That refutes the quoted Conjecture 6.1.

The mathematics is clean and checkable. Lemma 2.1 uses the one-vertex slide between consecutive windows to show a cycle cannot cross the forbidden types. Proposition 2.2 double-counts vertex-edge incidences to force all window types to be a or a+1, then forces exactly n/2 red edges. Proposition 2.3 gives an explicit binary word and verifies the construction actually is Hamiltonian. The degree formulas in Proposition 3.1 are standard inclusion-exclusion, the falling-factorial asymptotics are fine, and the k=17 arithmetic is correct: d_{17,8}=5761/8192, d_17=1-(8/17)(33/34)^15, and the gap exceeds 0.003. The large-k bound 1 - max_a d_{k,a} = O(k^{-1/2}) follows from Stirling, and the choice of a depending on parity is valid.

The one soft spot is external: the disproof is only as strong as the quoted statement of Conjecture 6.1 in [3]. If the original conjecture has extra hypotheses or a different normalization for d_k, the specific numbers would need rechecking. That is a reference-dependency caveat, not a mathematical gap in this paper. I also note the paper does not treat k=3, but the conjecture is only for k>=4, so this is not a problem.

This is a worthwhile counterexample, clearly written, with no self-citations and no parameter fitting. It deserves a serious referee; I would support acceptance after the reference check. I'd cite it for the layer-barrier family and the O(k^{-1/2}) behaviour.

Referee Report

1 major / 3 minor

Summary. This paper introduces a one-parameter family of red–blue coloured k-uniform hypergraphs H_{k,a}(n), called layer barriers, obtained by deleting edges whose intersection with a small part B has size a−1 or a+2 and colouring the surviving layers a and a+1 red and blue. The authors prove that every tight Hamilton cycle in H_{k,a}(n) is perfectly colour-balanced (Proposition 2.2), that the construction nevertheless contains a tight Hamilton cycle (Proposition 2.3), and that its asymptotic relative minimum vertex degree equals d_{k,a} (Proposition 3.1). At k=17 and a=8, this degree exceeds the conjectured threshold d_17 of Behague, Clemen, Hyde and Morrison, giving a counterexample to Conjecture 6.1 of that paper (Corollary 1.3). The authors also show that interior choices of a make the best barrier have asymptotic relative minimum degree 1−O(k^{-1/2}), in contrast to d_k→1−e^{-1/2}/2 (Corollary 1.4).

Significance. The contribution is a clean, explicitly checkable construction with a concrete numerical counterexample to a published conjecture. The proofs are short and self-contained: Lemma 2.1 gives a sharp window-confinement argument, Proposition 2.2 uses a double-counting incidence identity to force exact colour balance, and Proposition 3.1 computes the degree with standard binomial asymptotics. The counterexample is falsifiable and the constants are explicit. The main caveat is that the refutation depends on the exact wording of Conjecture 6.1 in the cited preprint [3]; the internal mathematics is sound. The paper also gives a new large-uniformity phenomenon, showing that interior layer barriers achieve asymptotic relative minimum degree 1−O(k^{-1/2}), which is substantially denser than the boundary construction.

major comments (1)

[Section 1, Conjecture 1.1] The counterexample in Corollary 1.3 refutes Conjecture 1.1 as stated, but the paper's central claim depends on this quotation being an exact reproduction of Conjecture 6.1 in [3]. The authors should verify the original statement and either reproduce it verbatim in the introduction or add a remark confirming that the degree normalization (minimum vertex degree as a count of (k−1)-sets), the formula (1) for d_k, and the quantifier order (α before δ and n0) match [3]. If the original conjecture carries any additional hypothesis, the computation in §3.1 would need to be checked against that version. This is a verification requirement rather than an error in the paper's internal derivation.

minor comments (3)

[Section 2, equation (3)] The phrase 'colour all remaining edges arbitrarily' is slightly imprecise because the proof of Proposition 2.2 shows that no tight Hamilton cycle uses any edge of these types; a one-sentence remark to that effect would help the reader.
[Section 3.1, after (9)] The inequality in (9) is asserted to follow by clearing denominators; displaying the exact integer inequality or stating the verified rational value would make the margin check fully transparent.
[References] Reference [3] is an arXiv preprint; the authors should ensure they cite the latest version, since the exact statement of Conjecture 6.1 could change between versions.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the construction is explicit and its degree is computed, not fitted.

full rationale

The paper's central claim is a counterexample to Conjecture 1.1 of Behague et al. The layer-barrier construction H_{k,a}(n) is defined explicitly by deleting edge types {a-1, a+2} and colouring types a and a+1 red and blue. The proofs that every tight Hamilton cycle is perfectly colour-balanced (Lemma 2.1 and Proposition 2.2) and that the construction contains a tight Hamilton cycle (Proposition 2.3) are self-contained combinatorial arguments. The minimum vertex degree is computed directly in Proposition 3.1 by counting excluded edges, and the asymptotic formula is obtained from binomial approximations, not by fitting any parameter to the conjectured threshold. The quantity d_{k,a} is defined independently as a binomial probability and then shown to equal the asymptotic relative degree; d_{k,0} is verified to reduce algebraically to the known d_k. The comparison d_{17,8} > d_{17} is a numerical inequality against an external benchmark, so the refutation is not circular. The only caveat is that the counterexample relies on the exact wording of Conjecture 6.1 of [3] as quoted in Conjecture 1.1, but this is an external-reference dependency, not a circular step.

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

The central claims rest on the quoted conjecture from Behague et al. (external reference), standard binomial asymptotics, and the explicit construction. No entities are invented and no data are fitted. The integer parameter a is a construction parameter, not a fitted constant; the counterexample uses a=8 and the large-k result uses a near k/2.

assumptions (3)

domain assumption The quoted Conjecture 6.1 of Behague et al. (Conjecture 1.1 here) is an accurate statement of the conjecture being disproved.
The counterexample (Corollary 1.3) refutes this exact statement. The paper quotes it in Section 1, but we cannot cross-check the original source; if the original had extra hypotheses, the refutation might not transfer.
standard math Standard falling-factorial asymptotics for binomial products with linear-sized arguments (equations (7)-(8)).
Used in Proposition 3.1 to pass from exact degree formulas to the limiting binomial probabilities. The error term O_{k,a}(n^{-1}) is standard.
standard math Stirling's approximation for binomial point probabilities with parameter p = 1/2 + O(1/k), giving max_j P(X=j) = O(k^{-1/2}).
Used in the proof of Corollary 1.4 for the large-uniformity behaviour.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Layer barriers for colour-biased tight Hamilton cycles." pith.science (2026). https://pith.science/paper/VY5AGQL7

@misc{pith2026260812013,
  author       = {Pith},
  title        = {Pith review of: Layer barriers for colour-biased tight Hamilton cycles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VY5AGQL7}},
  note         = {Machine review of arXiv:2608.12013}
}

abstract

We construct a family of layer barriers for colour-biased tight Hamilton cycles in uniform hypergraphs. For every $k\ge 3$ and every $a\in\{0,\ldots,k-1\}$, we give a red--blue coloured $k$-graph that contains a tight Hamilton cycle, while every tight Hamilton cycle in the construction is perfectly colour-balanced. The construction underlying the higher-uniformity threshold conjectured by Behague, Clemen, Hyde and Morrison corresponds to the boundary case $a=0$ of this family. We show that interior choices of $a$ can yield strictly denser barriers. In particular, for $k=17$ and $a=8$, the asymptotic relative minimum vertex degree of our construction is \[ \frac{5761}{8192}\approx 0.703247, \] which exceeds the conjectured value $d_{17}\approx 0.699277$. This provides a counterexample to the proposed higher-uniformity threshold in Conjecture~6.1 of Behague, Clemen, Hyde and Morrison. Moreover, by choosing the layer appropriately as $k\to\infty$, the family contains barriers whose asymptotic relative minimum vertex degree is \[ 1-O\bigl(k^{-1/2}\bigr). \] Thus the interior members of the layer-barrier family exhibit substantially different behaviour from the previously considered boundary construction in large uniformity.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[3]

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

N. Behague, F. C. Clemen, J. Hyde, and N. Morrison. A minimum-degree threshold for colour- biased Hamilton cycles in hypergraphs.arXiv preprint arXiv:2607.29628, 2026

work page Pith review arXiv 2026
[1]

Balogh, B

J. Balogh, B. Csaba, Y. Jing, and A. Pluh´ ar. On the discrepancies of graphs.Electronic Journal of Combinatorics, 27(2):P2.12, 2020

work page 2020
[2]

Balogh, A

J. Balogh, A. Treglown, and C. Z´ arate-Guer´ en. A note on colour-bias perfect matchings in hypergraphs.SIAM Journal on Discrete Mathematics, 38(4):2543–2552, 2024

work page 2024
[4]

Bradaˇ c

D. Bradaˇ c. Powers of Hamilton cycles of high discrepancy are unavoidable.Electronic Journal of Combinatorics, 29(3):P3.22, 2022

work page 2022
[5]

Bradaˇ c, M

D. Bradaˇ c, M. Christoph, and L. Gishboliner. Minimum degree threshold forH-factors with high discrepancy.Electronic Journal of Combinatorics, 31(3):P3.33, 2024

work page 2024
[6]

W. Chen, M. Rong, and Z. Xu. Optimal stability results on color-biased hamilton cycles.arXiv preprint arXiv:2507.17739, 2025

work page Pith review arXiv 2025
[7]

Freschi, J

A. Freschi, J. Hyde, J. Lada, and A. Treglown. A note on colour-bias Hamilton cycles in dense graphs.SIAM Journal on Discrete Mathematics, 35(2):970–975, 2021

work page 2021
[8]

Gishboliner, S

L. Gishboliner, S. Glock, and A. Sgueglia. Tight Hamilton cycles with high discrepancy.Combi- natorics, Probability and Computing, 34(4):565–584, 2025

work page 2025

Show all 13 references

[9]

Gishboliner, M

L. Gishboliner, M. Krivelevich, and P. Michaeli. Colour-biased Hamilton cycles in random graphs. Random Structures & Algorithms, 60(3):289–307, 2022

2022
[10]

Gishboliner, M

L. Gishboliner, M. Krivelevich, and P. Michaeli. Discrepancies of spanning trees and Hamilton cycles.Journal of Combinatorial Theory, Series B, 154:262–291, 2022

2022
[11]

H` an, R

H. H` an, R. Lang, J. P. Marciano, M. Pavez-Sign´ e, N. Sanhueza-Matamala, A. Treglown, and C. Z´ arate-Guer´ en. Colour-bias perfect matchings in hypergraphs.SIAM Journal on Discrete Mathematics, 39(3):1894–1916, 2025

1916
[12]

Lang and N

R. Lang and N. Sanhueza-Matamala. Minimum degree conditions for tight Hamilton cycles. Journal of the London Mathematical Society, 105(4):2249–2323, 2022

2022
[13]

Reiher, V

C. Reiher, V. R¨ odl, A. Ruci´ nski, M. Schacht, and E. Szemer´ edi. Minimum vertex degree condition for tight Hamiltonian cycles in 3-uniform hypergraphs.Proceedings of the London Mathematical Society, 119(2):409–439, 2019. 8

2019

Pith tools

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

[1] [3]

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

N. Behague, F. C. Clemen, J. Hyde, and N. Morrison. A minimum-degree threshold for colour- biased Hamilton cycles in hypergraphs.arXiv preprint arXiv:2607.29628, 2026

work page Pith review arXiv 2026

[2] [1]

Balogh, B

J. Balogh, B. Csaba, Y. Jing, and A. Pluh´ ar. On the discrepancies of graphs.Electronic Journal of Combinatorics, 27(2):P2.12, 2020

work page 2020

[3] [2]

Balogh, A

J. Balogh, A. Treglown, and C. Z´ arate-Guer´ en. A note on colour-bias perfect matchings in hypergraphs.SIAM Journal on Discrete Mathematics, 38(4):2543–2552, 2024

work page 2024

[4] [4]

Bradaˇ c

D. Bradaˇ c. Powers of Hamilton cycles of high discrepancy are unavoidable.Electronic Journal of Combinatorics, 29(3):P3.22, 2022

work page 2022

[5] [5]

Bradaˇ c, M

D. Bradaˇ c, M. Christoph, and L. Gishboliner. Minimum degree threshold forH-factors with high discrepancy.Electronic Journal of Combinatorics, 31(3):P3.33, 2024

work page 2024

[6] [6]

W. Chen, M. Rong, and Z. Xu. Optimal stability results on color-biased hamilton cycles.arXiv preprint arXiv:2507.17739, 2025

work page Pith review arXiv 2025

[7] [7]

Freschi, J

A. Freschi, J. Hyde, J. Lada, and A. Treglown. A note on colour-bias Hamilton cycles in dense graphs.SIAM Journal on Discrete Mathematics, 35(2):970–975, 2021

work page 2021

[8] [8]

Gishboliner, S

L. Gishboliner, S. Glock, and A. Sgueglia. Tight Hamilton cycles with high discrepancy.Combi- natorics, Probability and Computing, 34(4):565–584, 2025

work page 2025