Hitting time for Hamilton cycles in pseudorandom graphs

This paper proves that for sufficiently pseudorandom graphs, the hitting time for the appearance of a Hamilton cycle (and $k$ edge-disjoint Hamilton cycles) coincides with the hitting time for reaching minimum degree 2 (or $2k$), thereby resolving long-standing questions by Alon, Krivelevich, and Frieze and establishing sharp thresholds for these properties.

The Gist

Imagine you are building a massive, intricate city out of a specific set of blueprints. This city has $n$ intersections (vertices) and a fixed number of potential roads (edges) that could be built between them. However, you don't build the whole city at once. Instead, you have a giant, shuffled deck of cards, where each card represents one of those potential roads. You draw cards one by one and build the road on the card.

The big question mathematicians have been asking is: At what exact moment does this city become "connected" enough to have a perfect tour?

A "perfect tour" (called a Hamilton Cycle) is a route that starts at your house, visits every single intersection in the city exactly once, and returns home without retracing any steps. It's the ultimate road trip.

For a long time, mathematicians knew that for a completely random city (where any road could exist), the moment you get a perfect tour is exactly the same moment the last "lonely" intersection gets its second road. In other words, as soon as every intersection has at least two roads connected to it, the city is ready for the tour.

The Problem:
This paper tackles a harder version of the problem. Instead of a completely random city, imagine you are building a city based on Pseudorandom Blueprints. These are cities that look random but are actually built with a strict, mathematical structure (called $(n, d, \lambda)$-graphs). They are "expander" graphs, meaning they are very well-connected, like a super-efficient subway system where you can get anywhere quickly.

The question was: Does the rule still hold for these structured cities? Does the perfect tour appear exactly when the last intersection gets its second road?

The Big Discovery:
The authors (Chen, Chen, Im, and Wang) say YES.

They proved that for these structured, "pseudorandom" cities, as long as the city is sufficiently well-connected (a condition they call $d/\lambda \ge C$), the moment the city becomes Hamiltonian (ready for the tour) is exactly the moment the last intersection gets its second road.

The Analogy: The "Lonely Intersection" Party

Think of the construction process as a party where intersections are guests.

1. The Goal: Everyone needs to be part of a giant circle dance (the Hamilton Cycle).
2. The Obstacle: If an intersection (guest) has only 0 or 1 road (friend), they can't be part of a circle. They are stuck.
3. The Turning Point: The moment the very last "lonely" guest gets their second friend, everyone suddenly has at least two friends.
4. The Result: The authors proved that in these well-structured cities, the moment the last lonely guest gets a second friend, the giant circle dance immediately becomes possible. There is no waiting period. The city doesn't need to grow any bigger or add any more roads to form the tour; the structure was already there, just waiting for that final connection.

Why is this a big deal?

Before this paper, we only knew this "instant tour" rule worked for:

• Completely random cities.
• Very dense, highly connected cities.
• Specific shapes like hypercubes (think of a 3D cube extended to many dimensions).

But for "pseudorandom" cities that are sparse (not super dense) but still well-structured, this was a mystery. The authors solved a 20-year-old question posed by famous mathematicians Frieze and Krivelevich. They showed that even if the city isn't super crowded, as long as the connections are "well-mixed" (pseudorandom), the rule holds.

The "Edge-Disjoint" Bonus: Multiple Tours

The paper goes even further. Imagine you don't just want one tour, but $k$ different tours that never share a single road (edge-disjoint).

• The Rule: To have $k$ tours, you generally need every intersection to have at least $2k$ roads.
• The Discovery: The authors proved that for these pseudorandom cities, you can have $k$ separate tours at the exact moment the last intersection gets its $2k$-th road.
• The Limit: They showed this works for a surprisingly large number of tours (up to about $\log n$), which is a massive improvement over previous limits.

The "Sharp Threshold" (The Tipping Point)

The paper also calculates the exact tipping point for when these cities become tour-ready.

• Think of it like a light switch. Before a certain point, the city is dark (no tour). After that point, it's bright (tour exists).
• The authors figured out exactly where that switch is for different types of cities. If the city is very sparse, the switch is at one specific probability. If it's denser, the switch moves. They mapped out the entire landscape of when these tours become possible.

The Secret Weapon: "Robustness"

How did they prove this? They used a powerful concept called Robustness.
Imagine the city is a fortress. Even if you remove a few roads (or even a whole tour path), the fortress remains strong enough to build a new tour.

• They proved that these pseudorandom cities are so well-connected that even if you strip away the "bad" parts (intersections with low degrees), the remaining core is still a super-strong "expander."
• They then used a clever trick: they temporarily removed the "problematic" intersections, built a tour in the remaining strong core, and then "stitched" the removed parts back in to complete the full tour.

In Summary

This paper is like finding the final piece of a puzzle that mathematicians have been staring at for decades. It confirms that for a huge class of structured, well-connected networks, nature is efficient: the moment the network becomes "locally" ready (everyone has two connections), it instantly becomes "globally" ready (a perfect tour exists). It's a beautiful example of how order and randomness can dance together to create perfect structures.

Technical Summary

Here is a detailed technical summary of the paper "Hitting Time for Hamilton Cycles in Pseudorandom Graphs" by Chen, Chen, Im, and Wang.

1. Problem Statement and Context

The paper addresses the hitting time problem for Hamiltonicity in the context of pseudorandom graphs, specifically $(n, d, \lambda)$-graphs.

• The Process: Consider a base graph $G$ with $n$ vertices. A random subgraph process is defined by taking a uniformly random ordering of the edges of $G$ and adding them one by one to an initially empty graph $G_0$.
• The Question: Let $\tau_2(G)$ be the hitting time when the minimum degree of the evolving graph reaches 2, and let $\tau_{HC}(G)$ be the hitting time when the graph becomes Hamiltonian (contains a Hamilton cycle). The central question is whether $\tau_2(G) = \tau_{HC}(G)$ holds with high probability (whp).
• Historical Context:
  • For the complete graph $K_n$ (Erdős-Rényi process), this equality was famously proven by Ajtai, Komlós, Szemerédi, and Bollobás.
  • For pseudorandom graphs ($(n, d, \lambda)$-graphs), previous results required strong spectral gap conditions (e.g., $\lambda = o(d^{5/2}/(n \log n)^{3/2})$) or high degrees ($d = \Omega(n \log \log n / \log n)$).
  • Open Problem: Alon and Krivelevich (2019) and Frieze and Krivelevich (2002) asked for the weakest possible spectral gap condition ($d/\lambda$) that guarantees this hitting time property, particularly for sparse graphs where $d$ is small.

2. Key Contributions and Main Results

The authors resolve these open questions by proving that the hitting time equality holds under a constant spectral gap condition, which is optimal up to a constant factor.

Theorem 1.2 (Main Result)

There exists a constant $C > 0$ such that if $G$ is an $(n, d, \lambda)$-graph with $d/\lambda \ge C$, then:
$$\tau_2(G) = \tau_{HC}(G) \quad \text{whp.}$$

• Significance: This result removes the requirement for $d$ to be polynomially large in $n$. It holds even when $d$ is a large constant (provided $d/\lambda$ is sufficiently large), covering both sparse and dense regimes.

Corollaries on Sharp Thresholds

As a consequence of Theorem 1.2, the authors determine the sharp threshold for Hamiltonicity in $(n, d, \lambda)$-graphs.

• Corollary 1.3: Identifies the threshold probability $p_0$ for the random subgraph $G_p$ to be Hamiltonian. The threshold behavior transitions based on the magnitude of $d$:
  • If $d = o(\log n)$, the threshold is near 1.
  • If $d = \Omega(\log n)$, the threshold is approximately $\log n / d$.
  • The paper provides refined asymptotic formulas for different regimes ($d = c \log n$, $d = \omega(\log n)$, etc.), showing that the behavior mimics the complete graph case only when $d = \Omega(\log^2 n)$.

Theorem 1.5 (Generalization to $k$ Cycles)

The result is extended to $k$ edge-disjoint Hamilton cycles.

• Let $\tau_{2k}$ be the hitting time for minimum degree $2k$, and$\tau_{kHC}$be the hitting time for the existence of$k$ edge-disjoint Hamilton cycles.
• The authors prove $\tau_{2k} = \tau_{kHC}$ whp for $k \le c \cdot \min\{d, \log n\}$, provided $d/\lambda \ge C$.
• This advances a question by Frieze regarding the growth of $k$ with $n$.

3. Methodology and Proof Strategy

The proof is a sophisticated combination of probabilistic analysis, spectral graph theory, and structural graph theory.

A. Structural Analysis of the Hitting Time Graph ($G_{\tau_2}$)

The core difficulty is that the graph at the exact moment $\tau_2$ (minimum degree 2) contains vertices of degree 2, which prevents it from being a standard expander (expanders require high expansion, often implying higher minimum degree).

• Decomposition: The authors show that $G_{\tau_2}$ can be decomposed into:
  1. A massive core ($G_{\tau_2} \setminus X$) that is a strong $C$-expander.
  2. A small set of "bad" vertices $X$ (low-degree vertices) that are far apart (distance $\ge 5$).
• Expansion Properties: They prove that for both sparse ($d \le 10 \log n$) and dense ($d > 10 \log n$) cases, the graph satisfies specific expansion properties (vertex and edge expansion) whp.

B. Robust Hamiltonicity of Expanders (Theorem 1.7)

To handle the low-degree vertices in $X$, the authors prove a new structural result:

• Theorem 1.7: If $G$ is a $C$-expander and $E_0$ is a set of edges with $|E_0| \le n^{0.12}$ such that any two edges in $E_0$ are at distance $\ge 3$, then $G$ contains a Hamilton cycle containing all edges in $E_0$.
• Technique: This is proven using Posá rotations and sorting networks (inspired by Draganić et al., 2024). The authors adapt these techniques to ensure that the "forced" edges in $E_0$ are not destroyed during the rotation process.
• Application: In the hitting time graph, the low-degree vertices in $X$ are "contracted" by adding auxiliary edges between their neighbors. These auxiliary edges form the set $E_0$. The theorem guarantees a Hamilton cycle in the contracted graph containing $E_0$, which translates back to a Hamilton cycle in the original graph.

C. Extension to $k$ Edge-Disjoint Cycles

For Theorem 1.5, the authors show that even after removing $k-1$ edge-disjoint Hamilton cycles from $G_{\tau_{2k}}$, the remaining graph retains sufficient edge expansion properties to apply the same structural decomposition and robust Hamiltonicity argument. This requires proving that the "bad" set $X$ remains small and well-separated even after edge deletions.

D. Sharp Threshold Derivation

The sharp thresholds are derived by combining the hitting time result with Proposition 3.3, which analyzes the expected number of vertices with degree $\le 1$ in random subgraphs $G_p$. The authors perform precise moment calculations to identify the exact transition points for different regimes of $d$.

4. Significance and Impact

1. Optimality: The result establishes the optimal spectral gap condition ($d/\lambda \ge C$) for the hitting time property. Previous results required much stronger conditions (e.g., $d$ polynomial in $n$).
2. Unification: It unifies the behavior of random subgraphs across sparse and dense regimes, showing that the "minimum degree 2 implies Hamiltonian" phenomenon is robust in pseudorandom graphs as long as the spectral gap is constant.
3. Methodological Advance: The introduction of Theorem 1.7 (Hamiltonicity of expanders with forced edges) is a significant technical contribution. It provides a powerful tool for proving Hamiltonicity in graphs with local irregularities, which may have applications beyond hitting times.
4. Resolution of Open Problems: It definitively answers questions posed by Alon, Krivelevich, and Frieze regarding the minimal spectral requirements and the behavior of $k$ edge-disjoint cycles.
5. Counterexamples: The paper also provides a counterexample (Proposition 7.1) showing that the result does not hold for general expanders that are not regular, highlighting the necessity of the $(n, d, \lambda)$ structure (specifically regularity) for the hitting time property.

In summary, this paper represents a major breakthrough in the theory of pseudorandom graphs, establishing that the structural rigidity required for Hamiltonicity emerges exactly when the minimum degree constraint is satisfied, provided the graph has a constant spectral gap.