5
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • $\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$
    – Gerhard Paseman
    Commented Apr 17, 2018 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$
    – Richard Stanley
    Commented Apr 17, 2018 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$
    – Gerhard Paseman
    Commented Apr 17, 2018 at 16:48
  • $\begingroup$ Random permutations would correspond to labelled objects. $\endgroup$
    – Ben Barber
    Commented Apr 17, 2018 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$
    – Richard Stanley
    Commented Apr 17, 2018 at 18:15

2 Answers 2

Reset to default
4
$\begingroup$

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).

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

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .