Excursion Lengths in a Uniform Eulerian Circuit of the Complete Graph: Aldous's Conjecture Holds if and only if i = o(n^(3/2))

Let N_i be the number of excursions of length i from a fixed vertex in a uniformly random Eulerian circuit of the complete graph K_n in which every edge is replaced by two opposite arcs. Aldous and Yu (Open Problems in Mathematics, 2014) stated as the natural conjecture that E N_i is asymptotic to e^(−i/n). We prove that for every fixed K, uniformly in 2 ≤ i ≤ K n^(3/2), E N_i = exp(−i/n − i²/(2n³))(1 + O(n^(−1/2) log n)), and that E N_i e^(i/n) → 0 when i/n^(3/2) → ∞. Consequently E N_i ∼ e^(−i/n) holds if and only if i = o(n^(3/2)). This range contains fixed i, the scale i ∼ xn and essentially all excursions, and the length of a uniformly chosen excursion, divided by n, converges in distribution to the standard exponential law. At the scale i ∼ y n^(3/2) the ratio E N_i/e^(−i/n) tends to e^(−y²/2), so the conjecture read literally for all i is false. The proof is elementary. It combines the construction of a uniform Eulerian circuit from a uniform spanning tree (the BEST theorem, in the form used by Kandel, Matias, Unger and Winkler) with a hazard representation of the first excursion and a convexity bound. Exact computations for n ≤ 6 confirm the hazard representation and the closed forms for E N_2 and E N_3, and Monte Carlo simulations up to n = 6400 are consistent with the asymptotic results. This is an unrefereed note. Version 1.1 (30 September 2026) revises version 1.0 after an independent referee round. The theorems are unchanged, and the proofs change only in two wording clarifications. Main changes: a numerical remark in Section 7 on the deviation from the limit at the scale i ∼ y n^(3/2), which the proofs do not use, is corrected; the text now says that all circuits were enumerated only for n ≤ 5 and that the values for n = 6 come from the exact formula of Remark 2.5; the related work of Hu–Lyons–Tang and Farrell–Levine is cited; bibliographic data are corrected; and the verification record and the reproducibility package are updated. Unrefereed preprint released for independent mathematical scrutiny. Publication on Zenodo does not constitute peer review. AI-assisted tools supported research, computation, proof development, and manuscript preparation. The author remains responsible for all claims and the final text. Corpus identifier: AMR-096-0015 (UnsolvedMath; Aldous–Yu, "Random Eulerian circuits", example (a)).

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-09-30
DOI
https://doi.org/10.5281/zenodo.23051216
Primary Topic
Stochastic processes and statistical mechanics
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
preprint

Excursion Lengths in a Uniform Eulerian Circuit of the Complete Graph: Aldous's Conjecture Holds if and only if i = o(n^(3/2))

Alper Ferudun
Zenodo (CERN European Organization for Nuclear Research)
Stochastic processes and statistical mechanics
preprint

Excursion Lengths in a Uniform Eulerian Circuit of the Complete Graph: Aldous's Conjecture Holds if and only if i = o(n^(3/2))

Alper Ferudun
preprint en

Abstract

Let N_i be the number of excursions of length i from a fixed vertex in a uniformly random Eulerian circuit of the complete graph K_n in which every edge is replaced by two opposite arcs. Aldous and Yu (Open Problems in Mathematics, 2014) stated as the natural conjecture that E N_i is asymptotic to e^(−i/n). We prove that for every fixed K, uniformly in 2 ≤ i ≤ K n^(3/2), E N_i = exp(−i/n − i²/(2n³))(1 + O(n^(−1/2) log n)), and that E N_i e^(i/n) → 0 when i/n^(3/2) → ∞. Consequently E N_i ∼ e^(−i/n) holds if and only if i = o(n^(3/2)). This range contains fixed i, the scale i ∼ xn and essentially all excursions, and the length of a uniformly chosen excursion, divided by n, converges in distribution to the standard exponential law. At the scale i ∼ y n^(3/2) the ratio E N_i/e^(−i/n) tends to e^(−y²/2), so the conjecture read literally for all i is false. The proof is elementary. It combines the construction of a uniform Eulerian circuit from a uniform spanning tree (the BEST theorem, in the form used by Kandel, Matias, Unger and Winkler) with a hazard representation of the first excursion and a convexity bound. Exact computations for n ≤ 6 confirm the hazard representation and the closed forms for E N_2 and E N_3, and Monte Carlo simulations up to n = 6400 are consistent with the asymptotic results. This is an unrefereed note. Version 1.1 (30 September 2026) revises version 1.0 after an independent referee round. The theorems are unchanged, and the proofs change only in two wording clarifications. Main changes: a numerical remark in Section 7 on the deviation from the limit at the scale i ∼ y n^(3/2), which the proofs do not use, is corrected; the text now says that all circuits were enumerated only for n ≤ 5 and that the values for n = 6 come from the exact formula of Remark 2.5; the related work of Hu–Lyons–Tang and Farrell–Levine is cited; bibliographic data are corrected; and the verification record and the reproducibility package are updated. Unrefereed preprint released for independent mathematical scrutiny. Publication on Zenodo does not constitute peer review. AI-assisted tools supported research, computation, proof development, and manuscript preparation. The author remains responsible for all claims and the final text. Corpus identifier: AMR-096-0015 (UnsolvedMath; Aldous–Yu, "Random Eulerian circuits", example (a)).

Zenodo (CERN European Organization for Nuclear Research)
Peace, Justice and strong institutions
Stochastic processes and statistical mechanics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.