Random Eulerian Circuits

A finite connected balanced directed graph has a Eulerian circuit, so on such a graph one can consider a uniform random Eulerian circuit \(\mathcal{C}\). There is a simple algorithm -- see e.g. Kandel - Matias - Unger - Winkler Shuffling biological sequences -- for simulating \(\mathcal{C}\). Use the random walk method for simulating a uniform spanning tree, and regard that tree as directed toward an arbitrary root. This specifies the final exit the circuit will make from each non-root vertex. Now start the circuit at the root, and at each step choose uniformly from the possible edges not previously used, saving the pre-specified exit for last.

But it is not easy to extract properties of \(\mathcal{C}\) from this construction, and there is essentially no literature on properties of \(\mathcal{C}\). Here is one of many special cases one might study. Take the \(d\)-dimensional discrete torus \(Z^d_N\) and change each edge to two directed edges, giving \(2dN^d\) dirccted edges. A uniform random Eulerian circuit will have \(2d\) excursions from the origin: write the lengths of these excursions in increasing order as \(L_1 \le L_2 \le \ldots \le L_{2d}\).

Conjecture. Fix \(d \ge 3\). Each \(L_i\) is either \(O(1)\) or \(\Omega(N^d)\). More precisely, for \(\omega_N \to \infty\) arbitrarily slowly, \[ P ( \mbox{ some } L_i \in (\omega_N, N^d/\omega_N) )\to 0 \mbox{ as } N \to \infty . \] The conjecture arises by analogy with simple RW on the torus, whose excursion lengths are either \(O(1)\) or \(\Omega(N^d)\). For \(d=2\) the analogy suggests that the short lengths in the random Eulerian circuit might be \(O(\log N)\) instead of \(O(1)\).