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?

  • $\begingroup$ 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. $\endgroup$ Apr 17 '18 at 16:10
  • 6
    $\begingroup$ 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. $\endgroup$ Apr 17 '18 at 16:13
  • $\begingroup$ 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. $\endgroup$ Apr 17 '18 at 16:48
  • $\begingroup$ Random permutations would correspond to labelled objects. $\endgroup$
    – Ben Barber
    Apr 17 '18 at 18:01
  • 2
    $\begingroup$ 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$. $\endgroup$ 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!

expectation value of C_n vs n

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$:

n=100 estimated distribution of maximum component sizes

For $n=1000$:

n=1000 estimated distribution of maximum component sizes

For $n=10000$:

n=1000 estimated distribution of maximum component sizes

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:

Pn vs n

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


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])
  • 2
    $\begingroup$ The probability that $C_n=n$ is $(1+o(1)) \sqrt{\pi/(4n)}\,e^{3/4}$. Proof as in my "answer". $\endgroup$ Apr 19 '18 at 0:39
  • $\begingroup$ @BrendanMcKay Thanks! I'll see if I can work it out when I have some time. $\endgroup$
    – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.