Post Undeleted by Louigi Addario-Berry
3 Added Noga's argument.

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 useless 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 deleted itthink 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.

2 Deleted answer as it was nonsense.

Here is another rough argument for a lower bound, hopefully I'm not making a silly mistake. Also, I would hope there is a slicker argument then this, but here goes.

We're going to construct the permutation iteratively. First, build a random function $f:[n]\to [n]$ as follows.First fix a uniformly random permutation $\sigma$, then, for $i=1,\ldots,n$, select $f(\sigma(i))$ uniformly from among $\{\sigma(i),\ldots,\sigma(i)+n/2-1\}$, independently for each $i$. Say that $i$ is bad if there is $j < i$ such that $f(\sigma(j))=f(\sigma(i))$.

Not hard to check using standard concentration bounds that the proportion of bad guys is very close to $1/e$, except with extremely small probability (don't count bad guys, count the total number of indices $k$ for which $|f^{-1}(k)| \geq 2$).

Similarly, in every interval $[k,k+n/2)$ (mod n), the proportion of empty spaces is very close to $1/e$, except with extremely small probability. (Here you can take "very close" to mean, say, up to a multiplicative error of $O(n^{-1/3})$ except with probability $e^{-Cn^{1/3}}$ for some $C > 0$. I want strong bounds

Edit: my answer was useless so that I can guarantee structure after the procedure is finished, because we are going to iterate.)

Similarly, at each step $i$ of the process for building $f$, in every interval $[k,k+n/2)$ (mod n), the number of good choices for $f(k)$ is very close to $(n/2)e^{-i/n}$.

It follows straightforwardly from the above that when the $i$'th good choice was made, the number of available good choices was very close to $(n/2)(1-i/n)$ for all $i$ (note that there whp be a total of around $n(1-1/e)$ good choices made.

Now suppress the bad values $k$ from the domain of $f$ to obtain a partial permutation. It follows from the above that the number of distinct partial permutations that can arise is very close to $\prod_{i=1}^{n-n/e} \frac{n-i}{2}.$By the above concentration bounds, we know that when we finish the above, with high probability there are about $n/e$ values missing from the domain (and from the range) of our partial permutation. Furthermore, these missing values (in both the domain and the range) are uniformly distributed in every interval of the form $[k,k+n/2)$.

Repeat the procedure on the unchosen values of the partial permutation. This will allow you to fill in all but about $n/e^2$ of the remaining unchosen values, while maintaining the required concentration. Keep doing this until there are $u = o(n/\log n)$ unchosen values. The total number of partial permutations that can arise to this point is very close to $\prod_{i=1}^{n-u} \frac{n-i}{2} = \frac{n!}{u! 2^{n-u}} = \frac{n!}{2^{n(1+o(1)}},$since $u!=o(2^n)$ for $u$ this small.

It is not completely obvious that we can finish building the permutation at this point, but deleted itwould suffice if, for all $k$ missing from the domain of $f$, we could choose $f(k) \leq n/2$ when $k \leq n/2$ and $f(k) > n/2$ when $k > n/2$. For this, we need that the number of empty spaces in $[1,n/2]$ is the same for the domain as for the range, which might not quite be true.

However, if instead of maintaining that empty spaces in intervals of length $n/2$ are well distributed, we maintain this property for intervals of length $n/4$, then we can fix this problem by first matching some unmatched elements of $[n/4,n/2]$ to elements of $[n/2,3n/4]$, in order to ensure that the number of empty spaces on each side of $n/2$ is the same for the domain as for the range. Having done this, we can complete the permutation while maintaining the required property.

Post Deleted by Louigi Addario-Berry
1