On the hitting time of Hamiltonicity in bipartite Dirac graphs

Yiting Wang

On the hitting time of Hamiltonicity in bipartite Dirac graphs

T0 review · 0 major / 2 minor · reviewed 2026-06-27 · grok-4.3

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

Pith's one-line read In dense balanced bipartite graphs, the hitting time for minimum degree 2 equals the hitting time for Hamiltonicity with high probability.

desk verdict The paper states a clean bipartite extension of the hitting-time result for Hamiltonicity under a fixed Dirac-type host graph. read the letter →

arxiv 2606.11992 v1 pith:PP5YHFZD submitted 2026-06-10 math.CO

Yiting Wang This is my paper · ORCID

classification math.CO

keywords bipartitegraphsHamiltonicityhittingtimerandomgraphprocessminimumdegreeDiracconditionthreshold

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 establishes that for any fixed ε between 0 and 1/2, a balanced bipartite graph on 2n vertices whose minimum degree is at least (1/2 + ε)n becomes Hamiltonian at the same moment in the random edge-addition process when its minimum degree first reaches 2. This coincidence holds with high probability. The result extends an earlier theorem of Bollobás and Kohayakawa and supplies the bipartite counterpart to Johansson's hitting-time theorem for Hamiltonicity. As a direct consequence it yields a sharp threshold for the appearance of Hamilton cycles in this family of graphs.

What carries the argument

The uniform random edge-addition process on balanced bipartite graphs that are conditioned to satisfy the minimum-degree lower bound at every step; the argument shows that the first time this process produces a vertex of degree 2 is also the first time a Hamilton cycle appears.

What would settle it

A sequence of balanced bipartite graphs with minimum degree (1/2 + ε)n for which, in the uniform random edge-addition process, there is positive probability that a Hamilton cycle appears strictly after the minimum degree first reaches 2.

Watch

Extended reading notes

Core claim

Let ε∈(0,1/2] and let G be a balanced bipartite graph on 2n vertices with minimum degree at least (1/2 + ε)n. Then, in the random bipartite graph process, the hitting time for minimum degree 2 coincides with the hitting time for Hamiltonicity, with high probability. This immediately implies a sharp threshold result for Hamiltonicity in such graphs.

Load-bearing premise

The random process must add edges uniformly while the minimum-degree condition is enforced throughout; any deviation in how the process or the conditioning is defined can break the equality of the two hitting times.

Editorial extensions

If this is right

The hitting time of Hamiltonicity is governed exactly by the appearance of the second incident edge at any vertex.
Hamiltonicity has a sharp threshold at the moment minimum degree becomes 2 in this model.
The result supplies the bipartite analogue of the corresponding non-bipartite hitting-time theorem.
Any property that is known to appear at the minimum-degree-2 threshold in the same process is automatically Hamiltonian at that threshold.

Reading between the lines

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

Similar hitting-time coincidences may hold for other spanning structures such as perfect matchings or disjoint cycles once the minimum-degree barrier is crossed.
The technique could be adapted to show that Hamiltonicity is resilient under further random edge deletions after the hitting time.
Computational checks on moderate n could test whether the equality of hitting times already appears for small ε and n.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

The main thing to know is that the paper claims that for any balanced bipartite G on 2n vertices with minimum degree at least (1/2 + ε)n, the random edge-addition process on G hits Hamiltonicity at the same moment it hits minimum degree 2, with high probability. It also records the immediate sharp-threshold corollary for Hamiltonicity in such graphs.

What is actually new is the explicit statement of this bipartite hitting-time equality. The abstract frames it as an extension of Bollobás–Kohayakawa together with a bipartite version of Johansson’s theorem, and the claim is not already present in the works it cites. The fixed host graph G with the degree lower bound supplies the density that lets the usual coupling or exposure arguments apply, and the result avoids any visible reduction to fitted parameters.

The paper does well at organizing the threshold behavior under the minimum-degree condition and at keeping the statement direct. The random process is the standard uniform one restricted to the host, which matches the setup in the earlier non-bipartite results.

Soft spots are minor and mostly technical. The abstract alone does not let me inspect the concentration or the handling of bipartite matchings, so any new obstacles that arise from bipartiteness (parity or matching obstructions) cannot be checked here. The stress-test note finds no internal gap in the logical structure, and the weakest assumption listed—the standard process definition—looks consistent with prior work rather than a deviation that would invalidate the claim. If the full proof follows the usual lines, the extension should hold.

This is for people working on hitting times and Hamiltonicity in random graph processes. A reader already familiar with the Bollobás–Kohayakawa and Johansson results will see the value in the bipartite organization and the corollary. It deserves a serious referee because the statement is new, the setup is natural, and the evidence structure (fixed dense host plus standard process) is reproducible in principle.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that for ε ∈ (0,1/2] and any balanced bipartite graph G on 2n vertices with minimum degree at least (1/2 + ε)n, in the random edge-addition process on G the hitting time for minimum degree 2 coincides with the hitting time for Hamiltonicity, with high probability. This extends the Bollobás–Kohayakawa theorem and supplies a bipartite analogue of Johansson’s theorem, from which a sharp threshold for Hamiltonicity in such graphs is deduced as a corollary.

Significance. If the result holds, it supplies a precise hitting-time characterization for Hamiltonicity in the random process on any fixed dense bipartite host satisfying a Dirac-type condition. This strengthens the literature on phase transitions in random graphs by showing that the minimum-degree-2 threshold is already sufficient for Hamiltonicity under the given density assumption on G, and the corollary yields an immediate sharp-threshold statement that is useful for extremal and probabilistic combinatorics.

minor comments (2)

[Abstract, §1] In the abstract and §1, the probability space for the random process (uniform random edge additions restricted to the edges of the fixed host G) should be stated explicitly on first use to avoid any ambiguity about conditioning.
[§1] The citation to Bollobás–Kohayakawa and to Johansson’s theorem should include the precise bibliographic references in the introduction so that the extension is immediately traceable.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, assessment of significance, and recommendation to accept the manuscript.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity

full rationale

The paper states a direct probabilistic theorem on the coincidence of hitting times for minimum degree 2 and Hamiltonicity in a random edge-addition process on fixed balanced bipartite graphs satisfying a Dirac-type minimum-degree condition. No equations, fitted parameters, self-definitional reductions, or load-bearing self-citations appear in the abstract or claim structure. The result is framed as an extension of Bollobás--Kohayakawa and a bipartite analogue of Johansson's theorem, with the host-graph degree condition supplying the necessary density for standard coupling arguments; this is an independent probabilistic statement rather than a renaming or construction that reduces to its own inputs.

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

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; the degree lower bound (1/2 + ε)n is an input hypothesis rather than a fitted quantity.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the hitting time of Hamiltonicity in bipartite Dirac graphs." pith.science (2026). https://pith.science/paper/PP5YHFZD

@misc{pith2026260611992,
  author       = {Pith},
  title        = {Pith review of: On the hitting time of Hamiltonicity in bipartite Dirac graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PP5YHFZD}},
  note         = {Machine review of arXiv:2606.11992}
}

abstract

Let $\varepsilon\in (0,1/2]$ and let $G$ be a balanced bipartite graph on $2n$ vertices with minimum degree at least $(1/2 + \varepsilon)n$. Then, whp, the hitting time for minimum degree 2 coincides with the hitting time for Hamiltonicity. This extends Bollob\'{a}s--Kohayakawa and gives a bipartite analogue of Johansson's theorem. As an immediate corollary, we deduce a sharp threshold result for Hamiltonicity in such graphs.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 2 canonical work pages

[1]

Ajtai, J

M. Ajtai, J. Komlós, and E. Szeraerédi,First occurrence of hamilton cycles in random graphs, North-Holland Math- ematics Studies115(1985), no. C, 173–178

1985
[2]

Alon and M

Y. Alon and M. Krivelevich,Hitting time of edge disjoint hamilton cycles in random subgraph processes on dense base graphs, SIAM Journal on Discrete Mathematics36(2022), no. 1, 728–754

2022
[3]

Balogh, R

J. Balogh, R. Morris, W. Samotij, and L. Warnke,The typical structure of sparseK r+1-free graphs, Trans. Amer. Math. Soc.368(2016), no. 9, 6439–6485

2016
[4]

Bollobás,The evolution of sparse graphs, Graph theory and combinatorics (Cambridge, 1983) (1984), 35–57

B. Bollobás,The evolution of sparse graphs, Graph theory and combinatorics (Cambridge, 1983) (1984), 35–57

1983
[5]

Bollobás and Y

B. Bollobás and Y. Kohayakawa,The hitting time of hamilton cycles in random bipartite graphs, Graph Theory, Combinatorics, Algorithms and Applications,(Y. Alavi, FRK Chung, R. Graham and DF Hsu, Eds.) (1991), 26–41. 12

1991
[6]

Y. Chen, Y. Chen, S. Im, and Y. Wang,Hitting time for hamilton cycles in pseudorandom graphs, arXiv preprint arXiv:2603.05269 (2026)

work page arXiv 2026
[7]

Condon, A

P. Condon, A. Espuny Díaz, A. Girão, D. Kühn, and D. Osthus,Hamiltonicity of random subgraphs of the hypercube, vol. 304, American Mathematical Society, 2024

2024
[8]

Draganić, J

N. Draganić, J. Kim, H. Lee, D. M. Correia, M. Pavez-Signé, and B. Sudakov,Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions, arXiv preprint arXiv:2507.22807 (2025)

work page arXiv 2025

Show all 17 references

[9]

Frieze and M

A. Frieze and M. Krivelevich,Hamilton cycles in random subgraphs of pseudo-random graphs, Discrete Mathematics 256(2002), no. 1-2, 137–150

2002
[10]

Janson, T

S. Janson, T. Luczak, and A. Rucinski,Random graphs, John Wiley & Sons, 2011

2011
[11]

Johansson,On hamilton cycles in erdős-rényi subgraphs of large graphs, Random Structures & Algorithms57 (2020), no

T. Johansson,On hamilton cycles in erdős-rényi subgraphs of large graphs, Random Structures & Algorithms57 (2020), no. 1, 132–149

2020
[12]

R. M. Karp,Reducibility among combinatorial problems, 50 Years of Integer Programming 1958-2008: from the Early Years to the State-of-the-Art, Springer, 2009, pp. 219–241

1958
[13]

D. Kühn, A. Lo, D. Osthus, and K. Staden,The robust component structure of dense regular graphs and applications, Proceedings of the London Mathematical Society110(2015), no. 1, 19–56

2015
[14]

Montgomery,Hamiltonicity in random graphs is born resilient, Journal of Combinatorial Theory, Series B139 (2019), 316–341

R. Montgomery,Hamiltonicity in random graphs is born resilient, Journal of Combinatorial Theory, Series B139 (2019), 316–341

2019
[15]

Moon and L

J. Moon and L. Moser,On hamiltonian bipartite graphs, Israel Journal of Mathematics1(1963), no. 3, 163–165

1963
[16]

Pósa,Hamiltonian circuits in random graphs, Discrete Mathematics14(1976), no

L. Pósa,Hamiltonian circuits in random graphs, Discrete Mathematics14(1976), no. 4, 359–364

1976
[17]

Sudakov,Robustness of graph properties., BCC, 2017, pp

B. Sudakov,Robustness of graph properties., BCC, 2017, pp. 372–408. Institute of Science and Technology Austria, Klosterneuburg, 3400, Austria. Email address:yiting.wang@ist.ac.at 13

2017

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.

[1] [1]

Ajtai, J

M. Ajtai, J. Komlós, and E. Szeraerédi,First occurrence of hamilton cycles in random graphs, North-Holland Math- ematics Studies115(1985), no. C, 173–178

1985

[2] [2]

Alon and M

Y. Alon and M. Krivelevich,Hitting time of edge disjoint hamilton cycles in random subgraph processes on dense base graphs, SIAM Journal on Discrete Mathematics36(2022), no. 1, 728–754

2022

[3] [3]

Balogh, R

J. Balogh, R. Morris, W. Samotij, and L. Warnke,The typical structure of sparseK r+1-free graphs, Trans. Amer. Math. Soc.368(2016), no. 9, 6439–6485

2016

[4] [4]

Bollobás,The evolution of sparse graphs, Graph theory and combinatorics (Cambridge, 1983) (1984), 35–57

B. Bollobás,The evolution of sparse graphs, Graph theory and combinatorics (Cambridge, 1983) (1984), 35–57

1983

[5] [5]

Bollobás and Y

B. Bollobás and Y. Kohayakawa,The hitting time of hamilton cycles in random bipartite graphs, Graph Theory, Combinatorics, Algorithms and Applications,(Y. Alavi, FRK Chung, R. Graham and DF Hsu, Eds.) (1991), 26–41. 12

1991

[6] [6]

Y. Chen, Y. Chen, S. Im, and Y. Wang,Hitting time for hamilton cycles in pseudorandom graphs, arXiv preprint arXiv:2603.05269 (2026)

work page arXiv 2026

[7] [7]

Condon, A

P. Condon, A. Espuny Díaz, A. Girão, D. Kühn, and D. Osthus,Hamiltonicity of random subgraphs of the hypercube, vol. 304, American Mathematical Society, 2024

2024

[8] [8]

Draganić, J

N. Draganić, J. Kim, H. Lee, D. M. Correia, M. Pavez-Signé, and B. Sudakov,Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions, arXiv preprint arXiv:2507.22807 (2025)

work page arXiv 2025