# expected length of a largest cycle in regular graph

Consider a simple random regular graph $G_d(n)$ with $d=2$ (that is, I select a $2-$regular graph from the set of all $2-$regular graphs on $n$ vertices, uniformly at random).

It is clear that this graph consists of (not-intersecting) cycles only; and asymptotically a.s., it does not contain a cycle of length $n$.

My question is: Can we characterize the length of its largest cycle?

• If you "subtract 2" from each cycle, you get a not great map from your graph space to partitions of n-2k with k parts. Even though this is not ideal, it should be clear that as k gets large (maybe around k=n/e?) a lot more graphs will be present, and that you can still get asymptotic by fixing one of these values of k and showing it dominates any smaller cases (say k less than n/10). I would not be surprised if the answer turns out to be log n. Gerhard "Even Not Great Can Work" Paseman, 2018.04.17. Apr 17 '18 at 16:10
• If we ask the analogous question for disjoint unions of directed cycles (equivalently, random permutations of $1,2,\dots,n$) then by a result of Lloyd and Shepp (ams.org/journals/tran/1966-121-02/S0002-9947-1966-0195117-8/…) the expected length of the longest cycle is asymptotic to $cn$, where $c= \int_0^\infty \exp\left( -x-\int_x^\infty \frac{e^-y}{y}\,dy\right)\,dx$ $= 0.6243\cdots$. Presumably a similar argument will work for undirected cycles. Apr 17 '18 at 16:13
• Is the Lloyd and Shepp result for labelled graphs or unlabelled? My intuition says for unlabelled graphs that cn result is rather large. Gerhard "Maybe Has A Confused Intuition" Paseman, 2018.04.17. Apr 17 '18 at 16:48
• Random permutations would correspond to labelled objects. Apr 17 '18 at 18:01
• For unlabelled (undirected) graphs of degree two, we are asking for the largest part of a random partition (uniform distribution) of $n$. Husimi and Erdős-Lehner showed that this is asymptotic to $\frac{\sqrt{6}}{2\pi}\sqrt{n}\log n$. Apr 17 '18 at 18:15

Let $C_n$ denote the (random) size of the maximum cycle in a (uniform) simple random 2-regular graph on $n$ (labeled) vertices; $\langle C_n\rangle$ will denote its expectation value.

No theorems below, but here are the results of some experiments performed with SageMath (code below); they seem to suggest $\langle C_n\rangle\approx 0.76 n$, in line with Richard Stanley's first comment above. I can't be sure whether the values of $n$ I considered were large enough, so caveat lector!

I generated $10^4$, 5000 and 1000 random 2-regular graphs of size $n$ using SageMath's graphs.RandomRegular function (see link for citations for the algorithm) for $100\leq n<1000$, $1000\leq n<5000$, $5000\leq n\leq10100$, respectively. The above figure shows the mean size of the largest component as a function of $n$.

Next, I show the number of occurrences of each value of $C_n$ (an estimated probability distribution function) in the sampled $n$-vertex random graphs.

For $n=100$:

For $n=1000$:

For $n=10000$:

In all cases, there is a relatively large spike at $C_n=n$, and 0 occurrences of $C_n=n-1,n-2$ (since the graphs must be simple); this isn't always visible in the plots above due to the binning.

Since a large fraction of the distribution seemed to be concentrated at $n$, I also decided to check the probability $P_n$ of the event $C_n=n$. Here's a log-log plot:

Brendan McKay has commented that his technique shows that $P_n=(1+o(1))e^{3/4}\sqrt{\frac{\pi}{4n}}$ (drawn in red).

Code:

runs=1000
means = [0]*51
nummax = [0]*51
numruns = [0]*51

for ind,n in enumerate(range(100,10101,200)):
runs = 1000
if n < 5000:
runs = 5000
if n < 1000:
runs = 10000
data = [0]*runs
for j in range(runs):
G = graphs.RandomRegular(2,n)
data[j] = G.connected_components_sizes()[0]
numruns[ind] = runs
means[ind] = mean(data)
nummax[ind] = len([k for k in range(len(data)) if data[k]==n])

• The probability that $C_n=n$ is $(1+o(1)) \sqrt{\pi/(4n)}\,e^{3/4}$. Proof as in my "answer". Apr 19 '18 at 0:39
• @BrendanMcKay Thanks! I'll see if I can work it out when I have some time.
– j.c.
Apr 19 '18 at 1:06

I'm not going to do this calculation, but here is how it can be done. Any interval which contains the length of the longest cycle with probability tending to 1 will also contain the length of the longest cycle of a random pairing (configuration) with probability tending to 1. And vice-versa. With a random pairing you can easily calculate the expectation of the number of sequences of cycles with given lengths. From this the distribution of the number of cycles longer than a given length will follow. I'm not sure how messy the details will be, but it's easier than usual calculations in the pairing model because cycles cannot partially overlap.