# 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 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!

-
Sounds interesting - what is the role of edge directions? How do you determine the orientation of edges - do you randomize these as well? shouldn't all directed cycles on the same k nodes have the same value? wouldn't it be more natural to look at the undirected case? –  Or Zuk May 16 '11 at 22:16
One thought: For any $k$ you can get a simple upper bound on the heaviest cycle by looking at the average of the $k$ heaviest edges. If $k$ tends to infinity fast enough (e.g. like a constant fraction of $n$), this should be $o(\log n)$. Conversely, there's likely to be at least one edge of weight $C \log n$ if $C$ is small. If you take the best (or even a random) triangle containing that edge, you'll still be order $\log n$. –  Kevin P. Costello May 16 '11 at 22:51
To Kevin: Sorry I don't see why it's $\log n$. Shouldn't it be of order $\sqrt{\log n}$? (max of n i.i.d Gaussians?) To Or Zuk: the edge directions are fixed. You can think about this as being an undirected graph, allowing edges with negative edge length, with the condition $X_{ij} = -X_{ji}$. No, not all directed cycles on the same $k$ nodes have the same value: the order of the edge tranversal matter: for instance, the cycle 1 -> 2 -> 3 -> 4 -> 1 has value: 12 + 23 + 34 + 41, while the cycle 1 -> 3 -> 2 -> 4 -> 1 has value: 13 + 32 + 24 + 41 = 13 - 23 + 34 + 41. –  Ngoc Mai Tran May 17 '11 at 13:40
One approach I considered was to take the largest edge, then the second largest edge, etc. until these edges form a cycle. This will form a cycle whose maximum normalization is relatively large. What is the distribution of lengths of this cycle? However, the cycle with the greatest normalized weight does not need to be of this form. –  Douglas Zare Mar 19 '13 at 5:21
By the way, there is a related question about random matrices. Consider a random matrix with lognormal $\exp(N(0,\sigma^2))$ entries off the diagonal so that $a_{ij} = 1/a_{ji}$. As $\sigma^2\to \infty$, how does the largest eigenvalue behave? The largest eigenvalue is closely related to the maximum normalized cycle in this question. –  Douglas Zare Apr 16 '13 at 4:07
show 1 more comment

I wrote a program to collect some data.

For $n=8$, and $10^5$ trials, here are statistics on the longest cycles of length $k$ and the counts of the times that the cycle with the greatest normalized weight had length $k$.

k  count         avg            std_dev
3  50415  1.40995707256456 0.277702203891974
4  30427  1.3675029633889 0.248163593506348
5  13738  1.32184789116913 0.229675012490759
6   4428  1.26765935699902 0.215218146521779
7    916  1.20083001890189 0.202927859960246
8     76  1.11148487469463 0.190259341168933


In a few cases I inspected, the largest weight cycle of length $k+1$ often shared a directed chain of $k$ vertices with the largest weight cycle of length $k$, but of course this did not always happen. There seemed to be a high correlation between the largest weights of cycles of different lengths.

For $n=10, 12, 20$, I did a restricted optimization over the cycles of length at most $6$.

        n=10, 10^5 trials
k  count         avg            std_dev
3  44788 1.56377702460182 0.258071707092035
4  30386 1.53787677069062 0.228885384830286
5  16974 1.50659766688642 0.212244752764919
6   7852 1.4715247336037 0.199249497688295

n=12, 10^5 trials
k  count         avg            std_dev
3  41207 1.67848840347225 0.244485830656911
4  29722 1.66261483794121 0.21443274525213
5  18687 1.64098125565814 0.198203806693267
6  10384 1.61519351038532 0.186681888604542

n=20, 2000 trials
k  count         avg            std_dev
3    667 1.97010656830871 0.212728229010943
4    584 1.97273614009628 0.18001851348712
5    418 1.96707199503644 0.16332139093596
6    331 1.95442360307882 0.154839166051771

-

This was too long for a comment. (I ignored edge directionality - not sure it matters)

Taking the maximum of i.i.d. variables reduces the variance. As $k$ is increased, you take the maximum of a larger number of r.v.s., each already with a smaller variance, so the overall variance is further reduced. Say $y_N$ is the maximum of $m$ i.i.d. Gaussians each $N(0,\sigma^2)$, you have $E[y_N] \sim \sigma \sqrt{2\log m}$ and $V[y_N] \sim \sigma/\sqrt{2\log m}$. Using a (very) crude approximation $\binom n k = n^k$ you can approximate the mean and variance of the maximal cycle of length $k$: the mean is $E_k \sim \sqrt{2 \log n}$ so independent of $k$ (similar to what you've got), but the variance $V_k \sim \frac{1}{k \sqrt{2 \log n}}$ does depend on $k$. Therefore, at least under the i.i.d approximation, larger cycles give a smaller variance thus smaller $k$'s are more likely to give the maximum ($k=2$ the most likely).

-
Note that 2-cycles have value 0 due to the constraint $X_{ij} = -X_{ji}$, for $k \geq 3$. Why is the more concentrated cycle more likely to win? In general, if we have two random variables $X$ and $Y$ of the same mean, but $Var(X) < Var(Y)$, I don't think it's true that $P(X > Y) > 1/2$. (For example, take two independent R.V. symmetric about 0, then this probability is exactly 1/2 regardless of what the variance of $X$ and $Y$ are). –  Ngoc Mai Tran May 17 '11 at 13:43
Thanks for the clarification on directionality, so yes k≥3, but if you fix k and take n→∞, the asymptotics still doesn't change (nk becomes an even better approximation). Of course the independence approximation is more questionable (since many cycles use the same set of edges). I meant that the LESS concentrated cycle is more likely to win. This isn't true for just 2 variables, but if you've got many variables all with the same mean, the higher the variance is, the more likely you're to be the maximum (I didn't try to quantify it - the effect might be small). –  Or Zuk May 17 '11 at 20:23
Yes sorry, I meant the less concentrated cycle. I agree that the effect is probably small. For concreteness, take m independent Gaussians $X_1, \ldots, X_m$, all have mean 0 but different variance. Then $X_1$ would win if the $m-1$-dimensional Gaussian $Y := (Y_2, \ldots, Y_m) = (X_1 - X_2, \ldots, X_1 - X_m)$ is elementwise positive. That is, $X_1$ wins with probability $P(Y_i > 0 \forall i)$. Now $Cov(Y_i, Y_j) = Var(X_1)$, so by Slepian's lemma $X_i$ with largest variance is most likely to win. (I'll have to think about how to quantify this though) –  Ngoc Mai Tran May 18 '11 at 8:53