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
- Alper Ferudun
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