Connected components in random regular graphs

Question

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.

Answer 1

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