Shortest Eulerian excursion on the Hamming cube

Definitions and mathematical statement

For an integer $d\ge2$, the Hamming cube has vertex set $\{0,1\}^d$ and an undirected edge between binary strings differing in exactly one coordinate. Replace every edge by the two opposite directed arcs. There are $d2^d$ arcs, and each vertex has indegree and outdegree $d$.

Choose a directed Eulerian circuit uniformly, and root the traversal at the all-zero vertex. Each departure from that vertex starts an excursion ending at its next return, so there are exactly $d$ excursions. Order their lengths in directed steps as \[ L_1^{(d)}\ge\cdots\ge L_d^{(d)},\qquad \sum_{j=1}^dL_j^{(d)}=d2^d. \] The problem is to determine the asymptotic behavior of the minimum $M_d=L_d^{(d)}$ as $d\to\infty$, preferably by identifying a scale and a limiting distribution.

A precise asymptotic description could give deterministic normalizations and a limit law, or matching probabilistic estimates on the size of $M_d$. No particular conjectural normalization is stipulated in the source, so selecting and justifying the appropriate scale is part of the task. The probability is over the uniform circuit, not over independent random-walk excursions.

Every arc must occur exactly once in the complete tour, making the excursion lengths dependent. Their arithmetic average is exactly $2^d$, but this alone does not determine the minimum. The shortest excursion is allowed to be a two-step return along opposite arcs of the same undirected edge.

Short English statement

What is the asymptotic size and distribution of the shortest excursion in a uniform Eulerian circuit on the high-dimensional Hamming cube?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 9700016 (AMR-096-0016), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Aldous - Open problems, Random Eulerian Circuits, example (b). Original source indexed by AMR-096-0016. https://www.stat.berkeley.edu/~aldous/Research/OP/index.html.
• S3 D. Aldous and J. Yu, Random Eulerian Circuits (2014), original numbered conjecture and examples. https://www.stat.berkeley.edu/~aldous/Papers/aldous_eulerian.pdf.