Tiling Random Regular Graphs Efficiently

Let $G$ be an $n$-vertex graph and $H$ be an $s$-vertex graph. An $H$-factor in $G$ is a union of $\lfloor \frac{n}{s}\rfloor$ vertex-disjoint isomorphic copies of $H$ in $G$.

There has been an extensive study into the threshold of appearance of $H$-factors in the binomial random graph $G(n,p)$. The case where $H=K_2$ corresponds to finding a perfect matching in $G(n,p)$. The sharp threshold for appearence of a perfect matching was established by Erdős and Rényi [10]. Early results for general $H$ were obtained by Alon and Yuster [2] and Ruciński [26]; they determined the threshold up to a constant factor for a specific family of graphs and gave bounds for the general case. For the case where $H$ is a tree, Łuczak and Ruciński [19] characterised “pendant” structures, and proved that in the random graph process (that is, when edges are added one after the other uniformly at random), the hitting time of the appearance of an $H$-factor is the same as the hitting time of the disappearance of these forbidden “pendant” structures. In particular, one is able to infer the precise threshold for the appearance of an $H$-factor in this case. In 2008, Johansson, Kahn and Vu [16] determined the threshold (up to a multiplicative constant) for the existence of an $H$-factor for every strictly-1-balanced¹¹1A graph $H$ is strictly-1-balanced if $\frac{|E(H)|}{|V(H)|-1}>\frac{|E(J)|}{|V(J)|-1}$ for every proper subgraph $J⊊H$ with $|V(J)|\ge 2$. graph $H$ and determined the threshold up to a logarithmic factor for an arbitrary graph $H$. In the case of cliques $K_s$, Heckel (for $s=3$) [12] and Riordan (for $s\ge 4$) [24] determined the sharp threshold for the appearance of a $K_s$-factor. Recently, a hitting time result for the appearance of a $K_s$-factor was proved [13], and the sharp threshold for the appearance of an $H$-factor for every strictly-1-balanced graph $H$ was determined [6].

Much less is known in the case of random $d$-regular graphs. The random $d$-regular graph $G(n,d)$ is a graph chosen uniformly at random among all simple $d$-regular graphs on the vertex set $⟦n⟧:=\{1,\mathrm{\dots },n\}$ (throughout the paper, we treat $d$ as fixed and consider the asymptotics in $n$). Since, for every pair of integers $d\ge 2$ and $k\ge 3$, the number of cycles of length $k$ in $G(n,d)$ is asymptotically distributed as a Poisson random variable with mean ${(d-1)}^k/(2k)$ (see [28]), whp²²2With high probability, that is, with probability tending to one as $n$ tends to infinity. there are $o(n)$ cycles of length $k$ in $G(n,d)$. Thus, we may (and will) restrict our attention to tree factors.

For the case of $H=K_2$, Bollobás [4] proved that whp there exists an $H$-factor (that is, a perfect matching) in $G(n,d)$ for every $d\ge 3$. There has been some research on the more general case of stars. Naturally, one cannot hope for a $K_{1,t}$-factor for $t>d$, since the graph is $d$-regular. For $d\ge 3$, using a first moment argument, one can show that whp $G(n,d)$ does not contain a $K_{1,d}$-factor (see [3, Corollary 2]). Robinson and Wormald [25] showed that for $d\ge 3$, whp $G(n,d)$ contains a Hamilton cycle, and thus a $K_{1,2}$-factor. In a subsequent work, Assiyatun and Wormald [3] showed that for $d\ge 4$, whp $G(n,d)$ contains a $K_{1,3}$-factor. One may then suspect that for any $d\ge 3$, typically $G(n,d)$ contains a $K_{1,d-1}$-factor. However, using first moment calculations, one can show that this is not the case for $d\ge 5$.

There are then two natural avenues to venture into: first, for sufficiently large $d$, to determine all $k$ such that whp $G(n,d)$ contains a factor of stars on $k$ vertices; second, more ambitiously, one could try to find all trees $T$ for which whp $G(n,d)$ contains a $T$-factor.

Considering a related but slightly different problem, Alon and Wormald [1] showed that for any $d$-regular graph $G$, there exists an absolute constant $c^{\prime }$, such that $G$ contains a star-factor, in which every star has at least $c^{\prime }d/\log d$ vertices (not necessarily all of the same size). They further noted that this is optimal up the choice of the constant $c^{\prime }>0$. Indeed, the existence of a factor of stars on at least $k$ vertices implies the existence of a dominating set of size at most $\frac{n}{k-1}$, and for any $ϵ>0$ and sufficiently large $d$, whp the smallest dominating set in $G(n,d)$ is of size at least $\frac{(1-ϵ)n\log d}{d}$ (see [1, page 3]). Let us note here that if one only assumes that $G$ is $d$-regular, then one cannot hope to obtain a factor of stars of size exactly $k$ for any $3\le k=O(d/\log d)$. Indeed, consider for example a $d$-regular graph $G$ formed by a collection of vertex disjoint copies of $K_{d+1}$ and vertex disjoint copies of complete bipartite graphs $K_{d,d}$. Then, since $\text{gcd}(d+1,2d)\in \{1,2\}$, for any choice of $k>2$, one cannot find a factor of stars of size $k$.

Our first main result shows that typically a random $d$-regular graph $G$ contains a star-factor with the asymptotically optimal possible size. In fact, we extend this result to factors of any tree (not necessarily a star).

We note that throughout the paper, we will assume that $|V(G)|$ is divisible by $|V(T)|$, to avoid unnecessary technical details, however all proofs can be directly extended to the general case. Further, we note that we may fix the tree $T$ and show that whp there is a $T$-factor in $G(n,d)$; since there are at most $d^2\cdot 4^d$ such trees (see [22]) and $d$ is fixed, by the union bound the statement then holds for every tree $T$.

A detailed sketch of the proof of Theorem 1 is presented in Section 2. Let us briefly recap the main strategy here. We show that whp, there exists a balanced partition of $|V(G)|$ into $|V(T)|$ parts so that, for every pair of parts $V_i,V_j$ where $\{i,j\}\in E(T)$, every vertex in $V_i\cup V_j$ has the number of neighbours in the other part concentrated around the mean $d/|V(T)|$. We say that such a partition is nice. We obtain this nice partition through four different applications of the algorithmic version of the Lovász Local Lemma, due to Moser and Tardos [21]. In particular, this allows us to find such a nice partition which is close to a random partition; further, this gives us a randomised algorithm to find this partition whose average running time is $\tilde{O}(n)$ whp (see Theorem 4 and Corollary 5). In fact, we show that, in any $d$-regular graph, which does not have short cycles close to each other, a fraction of the possible partitions are close to nice partitions. Utilising a description of the distribution of edges in random graphs with specified degree sequences ([11], see also [20, Theorem 2.2]), we conclude that whp almost all partitions of a random regular graph induce multipartite graphs with good expansion properties. This allows us to find a partition with such expansion properties which is also close to a nice partition, ensuring the existence of a perfect matching between pairs of sets. Using an algorithm as in [7], we can find these perfect matchings in time $n^{1+o(1)}$. This gives us our second main result.

Since the events that we consider in our applications of the algorithmic version of the Lovász Local Lemma are determined by $\text{poly}(d)$ random variables over domains of size at most $d$, [21, Theorem 1.4] shows that there exists a deterministic algorithm that whp finds these $T$-factors in polynomial in $n$ time in $G(n,d)$.

Let us make some additional remarks.

• $\mathrm{■}$

  It is not hard to verify that our proof follows through for a uniformly chosen graph on $n$ vertices with a given degree sequence, whose degrees lie in the interval $[d,(1+\delta )d]$ for some small $\delta >0$. We believe slight modifications of our technique, specifically in Section 5, should allow us to obtain the same result for such graphs whose degrees are between $d$ and $O(d)$.

• $\mathrm{■}$

  We stress that in order to show the existence of a perfect matching between relevant sets in the partition, we need our partition to be close to a random partition, and thus the application of the algorithmic version of the Lovász Local Lemma is crucial, even if we do not aim to get Theorem 2.

A possible simplification, which allows using a non-constructive version of the Lovász Local Lemma, is applying “sprinkling” due to the contiguity result from [15] instead of applying the direct estimation of probabilities in $G(n,d)$. As soon as a nice partition is obtained, we add independently edges of $G(n,{ϵ}^{\prime }d)$, where ${ϵ}^{\prime }\ll ϵ$. Although it simplifies the proof, it does not allow deriving Theorem 2 and the generalisation to non-regular random graphs with specified degree sequences. Moreover, this does not allow obtaining any probability bounds, in contrast to our approach. Indeed, our proof gives that the probability a random $d$-regular graph has a $T$-factor (for any tree $T$ with $|V(T)|\le (1-ϵ)d/\log d$) is at least $1-n^{-{\mathrm{\Theta }}_d(1)}$. In fact, the latter probability bound is tight. Indeed, consider the vertices $\{1,\mathrm{\dots },10d\}\in ⟦n⟧$, say. The probability they form a connected component without a $T$-factor in $G(n,d)$ is at least $n^{-100d^2}$. We thus obtain the following corollary.

One key complication that arises when using any variant of the Lovász Local Lemma to prove Theorem 1 is that it is impossible to directly apply it, as every “bad” event has too many dependencies. A similar issue was addressed independently in the paper by Draganić and Krivelevich [9] on connected dominating sets, where they proposed a (significantly different and shorter) proof strategy to show that a $d$-regular graph without short close cycles has a nice partition. Notably, their method requires $\mathrm{\Theta }(n)$ applications of the Lovász Local Lemma (and consequently $O(n^2)$ resamples in the algorithmic version), which precludes a linear time reduction to finding perfect matchings. In contrast, our approach applies the Lovász Local Lemma only a constant number of times, enabling such a reduction.

Let us finish this section with several avenues for future research. While in this general setting Theorem 1 is asymptotically best possible, there are specific cases (such as when $T$ is a path [25], or in fact any $T$ of bounded degree [23, 14]) where one can whp obtain a $T$-factor for trees of size significantly larger than $\frac{d}{\log d}$ in $G(n,d)$. It would be interesting to try characterising for every value of $k=k(n)$ families of trees $T$ on $k$ vertices for which one can whp obtain a $T$-factor in $G(n,d)$. Another possible direction would be to consider $(n,d,\lambda )$-graphs, with $\lambda \ll d$, instead of $G(n,d)$ – see [17] for background, and [18, 23, 14] for related results on spanning subgraphs in such graphs that, in particular, imply the existence of $T$-factors for trees $T$ of bounded maximum degree.

Unsurprisingly, finding a tree factor is much harder when the size of the tree is close to the optimal size (that is, $d/\log d$). In this section, we will present the proof outline for Theorem 1 in the case when $k\ge \frac{d}{10\log d}$. We will further point out the steps where the proof becomes simpler for trees of smaller size.

Let $T$ be a tree on $k$ vertices and let us label these vertices by $V(T)≔⟦k⟧$. The overall strategy for finding a $T$-factor in $G\sim G(n,d)$ is quite intuitive. We will find $k$ disjoint sets $V_1,\mathrm{\dots },V_k\subseteq V(G)$ of equal size and show that whp there exists a perfect matching between every $V_i$ and $V_j$ such that $\{i,j\}\in E(T)$. To do so, our proof proceeds in two main steps. In the first step, we find “good” sets $V_1,\mathrm{\dots },V_k$ (in fact, we show such a partition typically exists in any $d$-regular graph $G$ without two short cycles close to each other). In the second step, we show the typical existence of a perfect matching between every relevant pair of these sets. The properties achieved in the first step facilitate the execution of the second step.

The first step of the proof, presented in Section 4, is perhaps the most involved and novel part. In this step, we establish key properties of the sets $V_1,\mathrm{\dots },V_k$ which will be crucial in verifying the typical existence of perfect matchings in the second step. First, we show that for every $\{i,j\}\in E(T)$, the degree of every $v\in V_i$ into $V_j$ is around $d/k$. Notice that, this property alone does not suffice to establish the existence of a perfect matching between $V_i$ and $V_j$. To that end, we will also make sure that the sets $V_1,\mathrm{\dots },V_k$ are “close” to uniformly chosen sets. More specifically, we will require that a large proportion of each set satisfies a few typical properties.

In the second step (Section 5), we show that whp, for every $\{i,j\}\in E(T)$, there exists a perfect matching between $V_i$ and $V_j$ by showing that Hall’s condition is satisfied. That is, we will show that whp, for every $W\subseteq V_i$, we have $|N(W,V_j)|\ge |W|$. To that end, we utilise a useful bound given by Gao and Ohapkin (see [11, Corollary 8], and also [20]). First, we will show that whp for every two “small” sets $U,W\subseteq V(G)$ with $|U|=|W|$, there are not too many edges going from $U$ to $W$. Moreover, since the sets $V_1,\mathrm{\dots },V_k$ were constructed in the first step in a way such that the degree of every vertex $v\in V_i$ to appropriate $V_j$’s is not too small, we obtain a lower bound on $e(W,V_j)$ for every $W\subseteq V_i$. In particular, if , we will get a contradiction for small sets $W\subseteq V_i$. In the same spirit, [11, Corollary 8] together with the properties of the sets $V_1,\mathrm{\dots },V_k$ allows us to bound $|N(W,V_j)|$ for every “large” $W\subseteq V_i$ if the sets $V_1,\mathrm{\dots },V_k$ were chosen uniformly at random. Indeed, given randomly chosen disjoint sets $A$ and $B$ (that is, sets formed without first exposing $G(n,d)$), the graph $G[A,B]$, given its degree sequence, has a uniform distribution. Our first step ensures that these sets behave similarly to uniformly chosen sets.

Let us return to the first step of the proof and describe the strategy of showing the typical existence of the “good” sets $V_1,\mathrm{\dots },V_k$. We begin with a random partition of the vertices into $k$ parts, $S_1,\mathrm{\dots },S_k$. A key tool in establishing the existence of such sets $V_1,\mathrm{\dots },V_k$ is the Lovász Local Lemma. Since we want our sets to be close to the initial random sets $S_1,\mathrm{\dots },S_k$ (so that we may later be able to apply [11, Corollary 8], we will in fact utilise the algorithmic version of the Lovász Local Lemma, due to Moser and Tardos (see Theorem 4 in Section 3). Utilising the algorithmic version of the Lovász Local Lemma, we can show that in each step of the algorithm we resample a small number of random variables assigned to vertices, and thus the initial random sets $S_1,\mathrm{\dots },S_k$ will not be “far” from $V_1,\mathrm{\dots },V_k$. Let us note here that when applying the algorithmic version of the Lovász Local Lemma, in the initial step of the algorithm one evaluates all “bad” events (requires $\tilde{O}(n)$ time), and then, at each “resampling” step, one re-evaluates only those $O(1)=O_d(1)$ events that depend on the resampled random variables. Since the expected number of steps of the algorithm of Moser and Tardos is $O(n)$, this gives the overall expected running time $\tilde{O}(n)$.

Now, for every vertex $v\in V(G)$, denote by $X_v$ a uniform random variable on $⟦k⟧$. For every $i\in ⟦k⟧$, set $S_i≔\{v\in V(G):X_v=i\}$. Moreover, for every vertex $v\in V(G)$, denote by $B_v$ the event that there exists $\{i,j\}\in E(T)$ such that $v\in S_i$ and $d(v,S_j)\notin [\delta d/k,Cd/k]$ where $\delta >0$ is a sufficiently small constant and $C>0$ is a sufficiently large constant. Notice that if $\neg B_v$ occurs for every $v\in V(G)$, then we get the desired bounds on the degrees which is the first key point in the first step.

Note that, for every vertex $v\in V(G)$ and $j\in ⟦k⟧$, we have $d(v,S_j)\sim \text{Bin}(d,1/k)$. This distribution is the heart of the obstacle concerning “large” trees. The reason for it is that whenever $k\le \frac{d}{10\log d}$, then the probability that the degree of $v$ into $S_j$, for some $j\in ⟦k⟧$, is not in the interval $[\delta d/k,Cd/k]$ is at most $d^{-8}$. Furthermore, the event $B_v$ is determined by $d+1$ random variables $X_u$, and $B_v$ is independent of all but at most $d^2$ other events $B_u$. Therefore, we can apply the Lovász Local Lemma. It is worth noting here that if $k\le \frac{d}{10\log d}$, we may omit the requirement that $\{i,j\}\in E(T)$ in the definition of $B_v$. Then, if for every vertex $v\in V(G)$ we have that $\neg B_v$ holds, then $d(v,S_j)\in [\delta d/k,Cd/k]$ for every vertex $v\in V(G)$ and index $j\in ⟦k⟧$.

However, as $k$ gets closer to $\frac{(1-ϵ)d}{\log d}$, the probability that is not smaller than $d^{-1-{ϵ}^{\prime }}$, for some ${ϵ}^{\prime }>0$ tending to zero as $ϵ$ tends to zero. Thus, the treatment of this case is much more delicate and involves several rounds of applications of the algorithmic version of the Lovász Local Lemma, in order to refine the initial random partition. In the rest of this section, we describe these rounds.

Notice that, for every $i\in ⟦k⟧$, the event $B_v$ conditioned on $v\in S_i$ is more likely to occur as the degree of the $i$-th vertex in $T$ gets larger. For this reason, we will treat vertices of small degree and vertices of large degree in $T$ differently (this treatment is in Section 4.1). Assume that $⟦h⟧$ is the set of vertices of $T$ with “large” degrees. We slightly decrease the probability that $X_v=i$, for every $i\in ⟦h⟧$. Then, after one application of the Lovász Local Lemma we will be able to get rid of vertices which have more than $Cd/k$ neighbours into $S_j$, for some $j\in ⟦h⟧$. Next, we consider the neighbourhood of the vertices which have degree less than $\delta d/k$ into $S_j$, for some $j\in ⟦h⟧$. We “resample” the vertices in this neighbourhood outside of $S_1,\mathrm{\dots },S_h$ into $S_1,\mathrm{\dots },S_h$, that is, we move them into one of the sets $S_1,\mathrm{\dots },S_h$ uniformly at random. In this way, once again using the Lovász Local Lemma, we will have that $d(v,S_j)\in [\delta d/k,Cd/k]$ for every $v\in V(G)$ and $j\in ⟦h⟧$.

Next, in Section 4.2, we partition the remaining vertices among $S_{h+1},\mathrm{\dots },S_k$. In this third application of the Lovász Local Lemma, we will ensure that after the resampling we have the property that, for every vertex $v\in V(G)$ and for all but at most ${ϵ}^{-2}$ indices $j\in ⟦k⟧$, we have $d(v,S_j)\in [\delta d/k,Cd/k]$. At this point, there will still be vertices $v\in S_i$ which have less than $\delta d/k$ neighbours into some $S_j$ where $\{i,j\}\in E(T)$. After the fourth application of the Lovász Local Lemma, we will be able to obtain a partition with no such vertices (that is, $d(v,S_j)\in [\delta d/k,Cd/k]$ for every $v\in S_i$ and $\{i,j\}\in E(T)$).

Finally, in Section 4.4, we adjust the sets $S_1,\mathrm{\dots },S_k$ to be of size $n/k$ each. This is the purpose of the fifth and final round of the Lovász Local Lemma. In this round, we will move vertices from sets of size bigger than $\frac{n}{k}$ to sets of size smaller than $\frac{n}{k}$ in a random manner. We will do so while ensuring the vertices $v$ we move satisfy that $d(v,S_j)\in [\delta d/k,Cd/k]$ for every $j\in ⟦k⟧$. After this round, while keeping the bounds over the degrees of the vertices, we will be able to make each set $S_i$ to be close to $n/k$ up to and additive $n/d^{100}$ error term. Finally, to make the sets exactly of size $\frac{n}{k}$, we introduce a deterministic argument adjusting the sets $S_1,\mathrm{\dots },S_k$ while changing the degree of every vertex to every set $S_i$ by at most one. We thus obtain the required sets $V_1,\mathrm{\dots },V_k$.

We will make extensive use of the algorithmic version of the Lovász Local Lemma, due to Moser and Tardos [21].

In fact, we will utilise the following corollary, whose proof appears in [8].

As mentioned in Section 2, the proof of Theorem 1 consists of two main steps. In order to find a $T$-factor in $G(n,d)$, we will partition the vertices of $G(n,d)$ into $|V(T)|$ sets of the same size, each set represents a different vertex in the tree $T$, and find a perfect matching between the $i$-th set and the $j$-th set for every $\{i,j\}\in E(T)$. In this section, we prove the first step of the proof. That is, we find a partition of the vertices into $|V(T)|$ sets which satisfies two crucial properties, which in turn will allow us to find the desired perfect matchings in the second step in Section 5.

For every pair of integers $d$ and $n$, let ${𝒢}_d$ be the family of all $d$-regular graphs on $n$ vertices, such that there are no two cycles of length at most $10$ at distance less than $10$ from each other. Recall that we treat $d$ as fixed, and consider the asymptotic as $n\to \mathrm{\infty }$. Note that whp $G(n,d)\in {𝒢}_d$ (see, for example, [27]).

The main result of this section, which is the first step in the proof of Theorem 1, is the following.

The proof of Proposition 6 is composed of four steps. Let us present here the overview of the proof and the organisation of this section.

In the first step of the proof of Proposition 6, appearing in Section 4.1, we construct the sets in the partition of $V(G)$ which correspond to vertices of high degree in $T$, where our treatment of vertices of high degree in $T$ will be separate from those of low degree.

In the second step of the proof of Proposition 6, appearing in Section 4.2, we construct the remaining sets in the partition of $V(G)$ (that is, the sets corresponding to vertices of low degree in $T$). After this step, for every $\{i,j\}\in E(T)$, we will no longer have vertices in the $i$-th set in the partition whose degree into the $j$-th set is greater than $Cd/k$. However, we may still have a small amount of vertices with degree less than $\delta d/k$. In the third step of the proof of Proposition 6, appearing in Section 4.3, we get rid of all such vertices. Lastly, in the final step of the proof of Proposition 6, appearing in Section 4.4, we will balance the sets of the partition to be of size exactly $n/k$ while we ensure that the requested properties are kept.

As discussed in Section 2, the proof is much simpler whenever one assumes $k\le \frac{d}{10\log d}$. Indeed, then some of the above steps may be skipped. We focus on the case where $k\ge \frac{d}{10\log d}$. In Sections 4.1–4.4, we let $T$ be a tree on $⟦k⟧$ and assume that $k\ge \frac{d}{10\log d}$.