# Connected components in random regular graphs

Suppose we take a random regular graph $$G_{2n, r}$$, where $$n$$ is large. Let us also assume that $$r$$ is fixed, (not dependent on $$n$$). Let's say that half of the vertices of the graph are colored black and the other half are colored white.

Let $$a_{n, r}$$ be the number of vertices of the "largest connected subgraph", where all vertices are of the same colour. Clearly, $$a_{n, r}$$ is a random variable. Is there a function $$f(n, r)$$ such that $$a_{n, r}$$ is asymptotically $$f(n, r)$$ with high probability? Is this in the $$\log n$$ regime? If an answer is known in the regime where $$r$$ is large (dependent on $$n$$), I would love to hear about that as well.

Since my question is not too technical at first glance, I am guessing that such problems are probably already well-studied in the random graph community. In that case, this is mainly a reference request.

• Is $r$ the degree of the random graph? I think if $r>2$, the size of the largest component is close to $n$. If $r=2$, this is the same as a random derangement. I think the statistics of the cycle lengths are known there too. Commented May 30, 2023 at 5:10
• @AnthonyQuas $r$ is indeed the degree of the random graph. Don't have a specific aim in mind, but let's assume that $r > 2$. Do you know of a reference? Thanks!
– SMS
Commented May 30, 2023 at 7:18

Not a definitive answer, but some pointers which are too long for a comment.

Let me just check I'm correctly interpreting the question. You take a uniformly random $$r$$-regular graph on $$2n$$ vertices. Then (independently of the edges) you uniformly colour $$n$$ vertices white, and consider the subgraph spanned by those $$n$$ vertices. Now you want to look at the largest component of that graph on $$n$$ vertices.

In that white graph, consider a typical vertex, and consider its neighbours, the neighbours of those neighbours, etc. As $$n\to\infty$$, what you see locally converges to a branching process with offspring distribution Binomial($$r-1, 1/2$$) (except for the first generation which is Binomial($$r,1/2$$)).

For $$r\geq 4$$ this branching process is supercritical -- the mean family size is $$(r-1)/2>1$$. In this case one would expect a "giant" component in the white subgraph, of size $$\sim \theta_r n$$ for some constant $$\theta_r$$. In fact $$\theta_r$$ should be the survival probability for a branching process of the type described in the previous paragraph. The second-largest component should be of order $$\log n$$.

For $$r=3$$ the process is critical. By analogy with other familiar classes of critical random graphs, one would expect the largest component to be on the order of $$n^{2/3}$$. (Also the $$k$$th largest component will be on the order of $$n^{2/3}$$ as $$n\to\infty$$ for any fixed $$k$$.)

I think this should all be doable within the context of known results for "configuration models". The empirical degree distribution of the white subgraph converges to Binomial($$r$$, $$1/2$$), and given the degree sequence, the graph is uniform among all possibilities -- i.e. it's a configuration model conditioned to be simple. You can find copious information and references about the structure of configuration models (including questions about large components) in volume 2 of Remco van der Hofstad's book Random Graphs and Complex Networks. An example of a reference to cover the critical ($$r=3$$) case might be Critical window for the configuration model: finite third moment degrees by Dhara, van der Hofstad, van Leeuwaarden and Sen (but that might also be overkill -- perhaps there are earlier and simpler results which would already do the job).

• One quick question while I digest the main answer: for $n = 3$, do you still expect the second largest component to be of order $\log n$?
– SMS
Commented May 30, 2023 at 12:52
• @SMS Hi SMS! - I actually mentioned that! For $r=3$, the $k$th largest component should be of order $n^{2/3}$ as $n\to\infty$, for every fixed $k$. Commented May 30, 2023 at 12:53