Cycles and Unicyclic Components in Random Graphs

Let \(G(n,m)\) denote a graph selected uniformly and at random from all graphs on \(n\) labelled vertices with \(m=m(n)\) edges. We say \(G(n,m)\) has a property \(\wp\) whp if \[ \lim_{n\rightarrow\infty}P\{G(n,m)\text{ has }\wp\}=1. \] Throughout the article under review, \(m=n/2\pm s\) where \(n^{2/3}=o(s)\) and \(s=o(n)\). The aim of the paper is to prove results about the lengths of cycles in such a graph. Let \(C_{1},\dots, C_{N}\) be those cycles in \(G(n,m)\) which belong to unicyclic components (i.e. components with only one cycle) and \(C_{1}^{*},\dots, C_{N^{*}}^{*}\) be those cycles which belong to multicyclic components. It is well known (see e.g. [\textit{S. Janson, T. Łuczak} and \textit{A. Ruciński}, Random graphs (Wiley, New York) (2000; Zbl 0968.05003)]) that if \(m=n/2-s\) then whp there are no multicyclic components, whereas if \(m=n/2+s\) there is whp one multicyclic component (the so-called giant component). \textit{T. Łuczak} [Random Struct. Algorithms 2, 421-440 (1991; Zbl 0755.05089)] showed that if \(m=n/2+s\) then the length of the longest cycle outside the giant component and the shortest cycle inside the giant component, after division by \(n/s\), converge in distribution to strictly positive random variables whose limiting distributions Łuczak gave. This paper makes a more detailed study of cycle lengths in \(G(n,m)\). As several results are proved, only a few are described here. For example, (denoting the length of a cycle \(C\) by \(|C|\)) the author obtains the limiting distribution (as \(n\rightarrow\infty\)) of \[ P\{\max\{|C_{i}|\}\leq an/s\} \] and \[ P\{\max\{|C_{i}^{*}|\}\leq an/s\}. \] In fact there is a joint convergence result, which implies that if \(m=n/2+s\) then the probability that every cycle inside the giant component is longer than every cycle outside it converges to 0.752\dots. Also it is proved that the probability that \(G(n,m)\) has two cycles of the same length, both belonging to unicyclic components, converges to 0.045\dots. The key technique is to use the language of point processes to study the cycle lengths. For example, it is shown that \(\{\frac{s}{n}|C_{i}|\}\) converges in distribution to an (inhomogeneous) Poisson process (on the line) with intensity \(\frac{1}{2x}e^{-2x}\) for \(0<x<\infty\). The approach leads to results about joint distributions: for example, if the cycles are ordered so that their lengths are in decreasing order, then (letting \(L=\sum_{k}|C_{k}|\) be the total length of all cycles in unicyclic components) the sequence of relative lengths \((|C_{1}|/L, |C_{2}|/L,\dots \dots)\) converges in distribution to a Poisson-Dirichelet distribution with parameter \(1/2\). However, if instead they are listed in the order in which they appear in the evolution of the random graph, the sequence of relative lengths converges to a GEM distribution. Turning all this into rigorous mathematics requires the following technical tools (amongst others). Firstly, some precision about point processes and convergence in distribution of sequences of point processes. Secondly, some facts about the distribution of the hitting times \[ T_{a,b}=\inf\{t:B_{t}+bt=a\} \] where \(B_{t}\) is a standard Brownian motion and \(a>0\) and \(b\) is finite. Thirdly, using known results about cycles in components of \(G(n,m)\). The next section contains heuristic arguments based on branching processes which suggest the results proved with the point process technology above. No attempt is made to render these arguments rigorous, though it is seems plausible that this can be done. The link between existence of a giant component in a random graph and whether a branching process is supercritical or not is well known; see e.g. \textit{N. Alon} and \textit{J. H. Spencer} [The probabilistic method (2nd edition) (Wiley, Chichester) (2000; Zbl 0996.05001)] for a nice discussion. (The basic idea is to treat the neighbours of a given vertex as its offspring: then if each vertex has about \(c\) offspring, then if \(c>1\) branching processes suggest there should be a good chance of long-term survival, i.e. a large component, but if \(c<1\) it suggests rapid extinction, so no large components.) Here more sophisticated ideas from the same stable are used -- the technique is to condition on existence of a specific \(k\)-cycle and explore its component. The author then gives further heuristics (which again could probably be made rigorous), based now on Brownian motion, which would yield the distribution of the sizes of the unicyclic components. It has long been known that, for \(s\) as before, \(G(n,n/2+s)\) with its giant component removed looks roughly like \(G(n,n/2-s)\). This is known to be closely related to the fact that a branching process with offspring distribution Poisson with parameter \(\lambda>1\), conditioned on extinction, coincides with a branching process whose offspring distribution Poisson with parameter \(\mu<1\), where \(\mu e^{-\mu}=\lambda e^{-\lambda}\) (see the book by Alon and Spencer). The author adds a third related heuristic based this time on Brownian motion, namely that \(T_{a,-b}\) (defined above), conditioned on being finite, has the same distribution as \(T_{a,b}\) provided both \(a\) and \(b\) are strictly greater than 0. It seems plausible that the point process technology of this paper will lead in time to other results for cycle structure in random graphs with number of edges as above.

Recommendations

Cited in

(13)

This page was built for publication: Cycles and Unicyclic Components in Random Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4796724)