Question

In http://www.springerlink.com/content/y19u81675243r237/fulltext.pdf, the author states the following without proof (equation 3.1):

"Consider a random permutation $\pi$ of $\mathbb{Z}_n$. What is the probability that $\pi(i+1)−\pi(i) \mod{n} < n/2$ for all $i$?"

The claim is that this is $(2+o(1))^{−n}$, which makes sense and seems like it should be a standard argument. However, I have not been able to come up with a short proof, nor have I been able to find a proof in the literature.

Does anyone know of a complete proof?

Answer 1

I emailed Noga to ask him; here is his response (touched up slightly for MO; any errors in what I post are probably mine rather than Noga's). The only details not present are the required applications of Stirling's formula.

As far as I recall the argument I had in mind was as follows (I am not trying to optimize the error term). Let $k$ be an even integer, much smaller than $n$ but much bigger than $\log n$, I guess $k=n^{0.01}$ or so should be ok. Split the set of vertices $[n]$ of the cyclic tournament to $k$ blocks of consecutive vertices, each of size $n/k$. Call the blocks $B_1,..,B_k$. We will count only Hamilton cycles in the tournament in which all edges go between distinct blocks, say from $B_i$ to $B_j$, with $j \lt i+k/2$ for each such edge, and with exactly $n/(k(k-2)/2)$ edges between each such pair of blocks.

To count those you use the so called BEST theorem to count the number of Euler circuits in the digraph on the $k$ vertices $B_1,\ldots,B_k$ with $n/(k(k-2)/2)$ directed edges from $B_i$ to $B_j$ for $i \neq j$, $j\lt i+(k-2)/2$ (and divide by $([n/(k(k-2)/2)]!)^{n/(k(k-2)/2)}$ to make sure all edges from B_i to B_j are considered the same.)

In the BEST theorem ignore the determinant corresponding to the number of arborecences, which is not needed here (we are anyway only proving a lower bound) and is negligible. This gives $[(n/k-1)!]^{k}$ divided by the term above. Now this has to be multiplied by $[(n/k)!]^k$, because inside each block B_i we can decide on the order in which we take the $n/k$ vertices (we enter the block represented by a vertex $(n/k)$ times, so we can decide which vertex we enter in each such step). Now take the resulting product, use Stirling and choose the optimal $k$: this should give the claim (not sure with which error term). It may well be that some stronger lower bounds are known, and in fact I think that a similar bound holds for any regular tournament (I believe there is a paper by Bill Cuckler about that in CPC 2007). Hope this makes sense, please feel free to mention whatever you see fit in Mathoverflow.

Answer 2

For odd $n$ the answer to your question (as stated!) can be found in Noga Alon's paper. Namely, the number of permutations in your question equals the permanent of an $n\times n$ matrix $A$ in which each row and each column has $(n-1)/2$ ones and $(n+1)/2$ zeros. Therefore $2/(n-1)*A$ is doubly stochastic, so by van der Waerden's conjecture (proved by Egorichev and Falikman in 1981) the requested probability is $\geq n!^{-1}((n-1)/2)^n n!/n^n=(1/e+o(1))2^{-n}$.

For even $n$ the answer is similar. Then the number of permutations in your question equals the permanent of an $n\times n$ matrix $A$ in which each row and each column has $n/2$ ones and $n/2$ zeros. Therefore $2/n*A$ is doubly stochastic, so similarly as before the requested probability is $\geq n!^{-1}(n/2)^n n!/n^n=2^{-n}$.

On the other hand, for all $n$ the considered permanent is $\ll \sqrt{n} n!/2^n$ by Noga Alon's main theorem in the paper, hence the requested probability is $\ll \sqrt{n}2^{-n}$.

Of course this does not explain why (3.1) in Noga Alon's paper holds. This is a statement about random cyclic permutations $\pi$ satisfying $\pi(i+1)−\pi(i) \mod{n} < n/2$ for all $i$.