2 formatting

Consider the complete, directed graph on $n$ vertices. Let the edge lengths ${X_{ij}: 1 \leq i, j \leq n}$ be i.i.d standard normal, with the constraint $X_{ij} = -X_{ji}$. The value of a \textbf{normalized normalized cycle} is the sum of the edges involved, divided by the cycle length. We want to know:

For any fixed $k$ and large $n$, (of particular interest are $k = 3$ and $k = n/2$), what is the probability that the maximum normalized cycle is of length $k$?

Some thoughts: Note that $3 \leq k \leq n$. There are $\binom{n}{k}(k-1)!$ directed cycles of length $k$ (except for $k =2$, in which we have $\binom{n}{k}$ such cycles), and each normalized cycle of length $k$ is Gaussian with variance $\frac{1}{\sqrt{k}}$. For small $k$ and large $n$, the number of directed cycles of length $k$ is approximately $n^k$. For $k = n/2$, this number is approximately $\sqrt{2}(\frac{2n}{e})^k$. Therefore, cycles of small length has the advantage of having larger variance, cycles of longer length has the advantage that there are many more of them.

To see that the dependency between cycles really matter, suppose that all cycles are independent. Since max of $m$ i.i.d Gaussian is $\sqrt{2\pi \log m}$, for small $k$, we have $$E(\max \mbox{cycle of length k}) \approx \frac{2\sqrt{2\pi k \log(n)}}{\sqrt{k}} = 2\sqrt{2\pi \log(n)}$$. For $k = n/2$, we have $$E(\max \mbox{cycle of length n/2}) \approx \frac{2\sqrt{2\pi k (\log(n) + \log(2/e)}}{\sqrt{k}} = 2\sqrt{2\pi (\log(n) + \log(2/e))}$$. But the max of $m$ i.i.d Gaussians with variance $\frac{1}{k}$ has variance $\approx \frac{1}{k}$ (Borell's inequality), therefore the difference of $\sqrt{\log (2/e)}$ will not get picked up.

Another naive approach: consider an easy union bound to get an upper bound on $E(\max \mbox{cycle of length k})$. Let $Z$ denotes the standard normal. Then $$P(\exists \mbox{ a k-cycle } > m) \leq \binom{n}{k}(k-1)!\cdot P(Z > \sqrt{k} m) \leq \exp(k\log n - k\log C - \frac{1}{2}\log(k) - \log(m) - \frac{km^2}{2})$$ where $C$ is some fixed constant. Solve for $m$ so that the RHS is $1$, we see that $m \approx \sqrt{2\log n}$, so this is an uninformative bound.

So one needs to take into account the dependency between cycles. But I'm quite stuck on what to do here. A quick literature search didn't return anything useful. Any ideas will be appreciated.

Thanks!

1

# what is the cycle length of the maximum normalized cycle in the directed complete graph?

Consider the complete, directed graph on $n$ vertices. Let the edge lengths ${X_{ij}: 1 \leq i, j \leq n}$ be i.i.d standard normal, with the constraint $X_{ij} = -X_{ji}$. The value of a \textbf{normalized cycle} is the sum of the edges involved, divided by the cycle length. We want to know:

For any fixed $k$ and large $n$, (of particular interest are $k = 3$ and $k = n/2$), what is the probability that the maximum normalized cycle is of length $k$?

Some thoughts: Note that $3 \leq k \leq n$. There are $\binom{n}{k}(k-1)!$ directed cycles of length $k$ (except for $k =2$, in which we have $\binom{n}{k}$ such cycles), and each normalized cycle of length $k$ is Gaussian with variance $\frac{1}{\sqrt{k}}$. For small $k$ and large $n$, the number of directed cycles of length $k$ is approximately $n^k$. For $k = n/2$, this number is approximately $\sqrt{2}(\frac{2n}{e})^k$. Therefore, cycles of small length has the advantage of having larger variance, cycles of longer length has the advantage that there are many more of them.

To see that the dependency between cycles really matter, suppose that all cycles are independent. Since max of $m$ i.i.d Gaussian is $\sqrt{2\pi \log m}$, for small $k$, we have $$E(\max \mbox{cycle of length k}) \approx \frac{2\sqrt{2\pi k \log(n)}}{\sqrt{k}} = 2\sqrt{2\pi \log(n)}$$. For $k = n/2$, we have $$E(\max \mbox{cycle of length n/2}) \approx \frac{2\sqrt{2\pi k (\log(n) + \log(2/e)}}{\sqrt{k}} = 2\sqrt{2\pi (\log(n) + \log(2/e))}$$. But the max of $m$ i.i.d Gaussians with variance $\frac{1}{k}$ has variance $\approx \frac{1}{k}$ (Borell's inequality), therefore the difference of $\sqrt{\log (2/e)}$ will not get picked up.

Another naive approach: consider an easy union bound to get an upper bound on $E(\max \mbox{cycle of length k})$. Let $Z$ denotes the standard normal. Then $$P(\exists \mbox{ a k-cycle } > m) \leq \binom{n}{k}(k-1)!\cdot P(Z > \sqrt{k} m) \leq \exp(k\log n - k\log C - \frac{1}{2}\log(k) - \log(m) - \frac{km^2}{2})$$ where $C$ is some fixed constant. Solve for $m$ so that the RHS is $1$, we see that $m \approx \sqrt{2\log n}$, so this is an uninformative bound.

So one needs to take into account the dependency between cycles. But I'm quite stuck on what to do here. A quick literature search didn't return anything useful. Any ideas will be appreciated.

Thanks!