UNIVERSALITY AND TOLERANCE AT THE TURN OF THE MILLENNIUM (Extended Abstract)

Noga Alon ^{∗} Michael Capalbo ^{†} Yoshiharu Kohayakawa ^{‡} Vojtěch Rödl ^{§} Andrzej Ruciński ^{¶} Endre Szemerédi ^{∥}

Abstract

For every r ≥ 2 and n > n_{0}(r), we construct explicitly a graph on n vertices with at most n^{2−Ω(1/r log r)} edges that contains every graph on n vertices with maximum degree r as a subgraph. We observe that any such graph must have at least Ω(n^{2−2/r}) edges, and prove that for every ε > 0 there is a graph with ⌈(1+ε)n⌉ vertices and Θ(n^{2−1/r}(log n)^{1/r}) edges containing all graphs on n vertices with maximum degree r (in fact, almost all graphs with the above number of vertices and edges are such). We also show that a typical bipartite random graph G with n vertices in each color class and Θ(n^{2−1/2r}(log n)^{1/2r}) edges contains all bipartite graphs on n vertices in each color class with maximum degree r, and that even after deleting an α fraction of the edges of G, the resulting subgraph contains all bipartite graphs with ⌊n/C(α)⌋ vertices in each color class, and with maximum degree r. The study of these questions is motivated by problems in VLSI circuit design.

∗Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel. Research supported in part by a USA-Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. Email: noga@math.tau.ac.il.

†Department of Mathematical Sciences, The Johns Hopkins University, 3400 N. Charles Street, Baltimore, MD 21218. Supported by NSF grant CCR95085-45 and ARO grant DAAH04-96-1-0013. Email: capalbo@mts.jhu.edu.

‡Instituto de Matemática e Estatística, Universidade de São Paulo, Brazil. Research partially supported by FAPESP (Proc. 96/04505–2), by CNPq (Proc. 300334/93–1), and by MCT/FINEP under PRONEX project 107/97. Email: yoshi@ime.usp.br

§Department of Mathematics and Computer Science, Emory University, Atlanta. Research supported by NSF grant DMS 9704114. Email: rodl@mathcs.emory.edu

¶Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań, Poland. Research supported by KBN grant 2 P03A 032 16. Part of this research was done during the author’s visit to Emory University. Email: rucinski@amu.edu.pl

∥Department of Computer Science, Rutgers University. Email: szemered@cs.rutgers.edu

1 Introduction

For a family H of graphs, a graph G is H-universal if it contains every member of H as a subgraph. For example, the complete graph K_{n} is H_{n}-universal for the family H_{n} of all graphs on at most n vertices. The construction of sparse universal graphs for various families arises in the study of VLSI circuit design, and received a considerable amount of attention, see, e.g., [6],

[7] and their references. Since in some applications the cost of a vertex is higher than that of an edge, one is particularly interested in tight H-universal graphs, i.e., graphs whose number of vertices equals max_{H∈H} |V (H)|.

Most of the previously known constructions of sparse universal graphs for various families are based on the existence of small separators in these families. Since here we deal with families of graphs that do not have small separators we need some novel techniques. These combine the notion of the strong chromatic number of a graph, introduced in [1], various properties of random graphs, an embedding technique based on matching theorems, developed in [3] and [16], a structure result on sparse regular pairs proved in [11], a sparse version of Szemerédi’s regularity lemma, and a hypergraph packing result from [15].

Let H(r, n) denote the family of all (pairwise nonisomorphic) graphs on n vertices in which every degree is at most r. In this paper we study the minimum possible number of edges M = M(r, n) in a graph on n vertices which is H(r, n)-universal. An ultimate lower bound follows from the obvious inequality ∑_{i≤rn/2} \binom{M}{i} ≥ |H(r, n)| and the well known (see e.g. [10], Cor. 9.8, page 239) asymptotic formula for the number L_{r,n} of all labelled r-regular graphs on n vertices, nr even:

L_{r,n} = (1 + o(1))\sqrt{2}e^{−(r^{2}−1)/4} (\frac{r^{r/2}}{e^{r/2}r!})^{n} n^{rn/2}.

Bounding \binom{M}{rn/2} ≤ (\frac{2eM}{rn} )^{rn/2} and |H(r, n)| ≥ L_{r,n}/n! this yields the lower bound

M(r, n) = Ω(n^{2−2/r})

for the number of edges of any H(r, n)-universal graph on n vertices. If rn is odd, simply observe that an H(r, n)-universal graph is also H(r, n − 1)-universal.

It follows from the celebrated Blow-up Lemma [13] that M(r, n) = o(n^{2}). Here we obtain bounds of the form n^{2−a}, for some strictly positive a that depends only on r. Our first result provides an explicit construction, as stated in the following theorem. (Note that M(1, n) = ⌊n/2⌋.)

Theorem 1.1 There exists an absolute positive constant c such that for every r ≥ 2 and n > n_{0}(r) there is an (explicitly described) H(r, n)-universal graph G with n vertices and at most n^{2−c/r log r} edges.

Thus, in view of the ultimate lower bound, the above construction is not too far from being best possible. If we allow G to have more than n vertices, and we do not insist on an explicit construction, we can get the following better estimate realized by “almost all” graphs. We say that a random graph possesses a property asymptotically almost surely, and write a.a.s., if the probability of the event in question tends to 1 as n → ∞.

Theorem 1.2 For every ε > 0 there exists a positive constant c = c(ε) such that for every r ≥ 2 the random graph G(⌈(1 + ε)n⌉, p) with p = cn^{−1/r}(log n)^{1/r} a.a.s. is H(r, n)-universal. Consequently, for n > n_{0}(r) there is an H(r, n)-universal graph G with ⌈(1 + ε)n⌉ vertices and, say, at most (1 + ε)^{2}cn^{2−1/r}(log n)^{1/r} edges.

A related Ramsey theoretic statement is considered by Kohayakawa, Rödl and Szemerédi [12]. With some more work we are able to get rid of the annoying factor of 1 + ε, but only

in the bipartite case and for a slightly higher edge density. For r ≥ 2 let H(r, n, n) be the family of bipartite graphs with n vertices in each vertex class and with maximum degree at most r. Let G(n, n, p) be the random bipartite graph with n vertices in each color class and edge probability p.

Theorem 1.3 There exists an absolute positive constant c such that, for every r ≥ 2, a.a.s. G(n, n, p) is H(r, n, n)-universal, where p = c(log n/n)^{1/2r}. Consequently, for n > n_{0}(r) there is an H(r, n, n)-universal, bipartite graph G with n vertices in each color class and at most 2cn^{2−1/2r}(log n)^{1/2r} edges.

It turns out that the same random graph enjoys a related property. For a real number α, where 0 < α < 1, we say that a graph G is α-fault-tolerant with respect to a family of graphs H, if every subgraph of G with at least a 1 − α fraction of the edges of G is H-universal. In general, restricting to bipartite graphs is unavoidable here, as for any graph G, there is a bipartite subgraph G′ of G with at least half the edges of G.

Theorem 1.4 For every r ≥ 2 and 0 < α < 1 there exist constants c > 0 and C > 0 such that a.a.s. G(n, n, p) is α-fault-tolerant with respect to H(r, h, h), where h < n/C and p = c(log n/n)^{1/2r}. Consequently, for n > n_{0}(r) there is a bipartite graph G with n vertices in each color class and at most 2cn^{2−1/2r}(log n)^{1/2r} edges, which is α-fault-tolerant with respect to H(r, ⌊n/C⌋, ⌊n/C⌋).

The rest of this extended abstract is organized as follows. In Section 2 we sketch the proof of Theorem 1.1. Section 3 contains a brief description of the proofs of Theorems 1.2 and 1.3. Section 4 deals with Theorem 1.4. Finally, Section 5 contains some concluding remarks. Due to space limitations, some of the detailed proofs are given only in the appendix.

2 The strong chromatic number and universal graphs

The techniques in [7] can be used to construct H(r, n)-universal graphs with O(n^{2}/ log^{2} n) edges. To obtain the better construction needed in the proof of Theorem 1.1 we combine a new technique with the main result of [1]. This construction, besides providing graphs with a rather small number of edges, is simple, and supplies an efficient algorithm for embedding any given member of H(r, n) in the graph constructed. The construction is in fact so simple that for r = 3 and any n which is a power of 16, say, n = 16^{s}, it can be described in one (short) sentence, as follows. The vertices are all vectors of length s over the alphabet {1, 2, …, 16}, and two are adjacent if and only if they differ in all coordinates.

Let H be a graph with |V (H)| = n. If k divides n we say that H is strongly k-colorable if for any partition of V (H) into pairwise disjoint sets V_{i}, each of cardinality k precisely, there is a proper k-vertex coloring of H in which each color class intersects each V_{i} in exactly one vertex. If k does not divide n, we say that H is strongly k-colorable if the graph obtained from H by adding to it k⌈n/k⌉ − n isolated vertices is strongly k-colorable. The strong chromatic number of H, denoted by χ_{s}(H), is the minimum k such that H is strongly k-colorable. For example, χ_{s}(C_{6}) = 3. It is not difficult to check that if H is strongly k-colorable, then it is also strongly (k + 1)-colorable.

The notion of strong chromatic number is studied in [1], where the following result is proved. (It is easy to see that if Δ(H) ≤ 1 then χ_{s}(H) ≤ 2.)

Theorem 2.1 ([1]) For every r ≥ 2:

(i) There exists an absolute constant b such that if Δ(H) ≤ r then χ_{s}(H) ≤ br. (ii) If Δ(H) ≤ r then χ_{s}(H) ≤ 2^{r+1}.

The constant b is very large, so that for small values of r the assertion of part (ii) is better than that of part (i). In addition, as mentioned in [1] there is a deterministic, polynomial time algorithm that gets as an input a graph H with maximum degree r and a partition of its set of vertices into pairwise disjoint subsets of cardinality ⌊br⌋ each, and produces a proper vertex coloring of this graph in which every color class contains exactly one element of each of these subsets.

We next show how to apply the above result for the construction of universal graphs. It is easier to describe first the construction when the number of vertices is a power of the maximal strong chromatic number of the graphs with maximum degree ≤ r. The general case if given in the appendix. For two integers k and s, let G(k, s) denote the graph whose n = k^{s} vertices are all vectors of length s over the alphabet {1, 2, …, k}, where two are adjacent if and only if they differ in all coordinates. Note that G(k, s) is (k − 1)^{s}-regular, and hence its number of edges is

\frac{1}{2}n(k − 1)^{s} ≤ n^{2} (\frac{k − 1}{k})^{log n/ log k} ≤ n^{2−1/k log k}.

Proposition 2.2 For every two positive integers k and s, the graph G(k, s) contains every graph H on n = k^{s} vertices with χ_{s}(H) ≤ k.

Proof: Split the vertex set V of H arbitrarily into disjoint subsets of size k each and find a proper coloring of H so that each color class contains precisely one vertex in each of the subsets. This coloring provides a partition of V into k disjoint sets V_{1}, V_{2}, …, V_{k}, each being an independent set in H, where each set V_{i} is of cardinality precisely n/k = k^{s−1}. Next, split each set V_{i} arbitrarily into disjoint sets of size k each, and find another proper coloring of H so that each color class contains precisely one vertex in each of the sets. Let V_{ij} denote the set of all vertices colored i in the first coloring and colored j in the second. Note that each of the k^{2} sets V_{ij} is of cardinality k^{s−2}, and if ij and i′j′ have a common coordinate, then there is no edge of H connecting a member of V_{ij} with a member of V_{i′j′}. Assume, now, that we have already partitioned the vertices of H into k^{j} sets V_{u}, indexed by the set of all vectors u in {1, 2, …, k}^{j}, where j < s and for all u

|V_{u}| = k^{s−j} and there is no edge of H between V_{u} and V_{u′} if u, u′ have a common coordinate.

(1)

Now split each set V_{u} into disjoint subsets of cardinality k each, and find a proper coloring of H so that each color class contains exactly one vertex in each of the subsets. The new coloring splits each set V_{u} into k disjoint sets of equal cardinality according to the last coloring, and the new partition satisfies the condition (1) above, with j replaced by j + 1.

When this process terminates, we obtain a partition of the set of vertices of H into k^{s} sets, each containing a single vertex. By mapping the only vertex in each set V_{u} of this partition, for u ∈ {1, 2, …, k}^{s}, to the vertex u of G(k, s), we obtain the desired embedding.

Notice that by Proposition 2.2 and by Theorem 2.1(ii), the graph G(16, s) contains every graph H on at most n = 16^{s} vertices with maximum degree 3 and has no more than n^{1.9767} edges. Moreover, by the fact that the proof of Theorem 2.1(ii) given in [1] provides a linear time algorithm for the corresponding algorithmic problem, the proof above supplies an O(n log n) algorithm for finding a copy of any such given H in G(16, s). For larger values of r, Proposition 2.2 and Theorem 2.1(i), supply the assertion of Theorem 1.1 if n is a power of ⌊br⌋, and supply an efficient deterministic algorithm for finding the required embeddings as well.

If the number of vertices is not necessarily a power of ⌊br⌋ and we still want an H(r, n)- universal graph with precisely n vertices, the construction has to be slightly modified. The details are given in the appendix.

3 Random graphs as universal graphs

In this section we sketch the proofs of Theorems 1.2 and 1.3, and also lay some ground for the more complicated proof of of Theorem 1.4. The full details are given in the appendix. The proofs are probabilistic, and apply the techniques from [3] and [16] (see also [4].) The proof of Theorem 1.4 requires in addition a sparse version of the Regularity Lemma and related structural results [11] and a new technique of graph embedding based on hypergraph packing [15].

We assume, whenever this is needed, that n is sufficiently large as a function of r, and omit all floor and ceiling signs, to simplify the presentation.

Consider the probability space of all graphs on n labelled vertices in which every pair of vertices forms an edge, randomly and independently, with probability p. We use the notation G(n, p) to denote a graph chosen randomly according to this probability measure; i.e., for any graph G on n labeled vertices and with m edges, P [G(n, p) = G] = p^{m}(1 − p)^{\binom{n}{2}−m}. Similarly, we define the bipartite random graph G(n, n, p). Throughout we designate the bipartition of G(n, n, p) by V_{1} and V_{2}.

To show that a graph G is H-universal, one has to find for each H ∈ H an embedding into G, i.e., a mapping f : V (H) → V (G) such that

(I) f is injective, and

(II) f(x)f(y) ∈ E(G) if xy ∈ E(H). The proofs of Theorems 1.2, 1.3, and 1.4 are all based on the same scheme of constructing the embedding f, which can be outlined in a few steps, as described below. (This scheme was introduced in [3] and later used in a nonrandom context in [14] to provide an alternative proof of the Blow-up Lemma.)

We next describe the scheme. An independent set is two-independent if no two of its vertices have a common neighbor. Suppose we want to embed a graph H ∈ H(r, n) (H ∈ H(r, n, n)) into a random (bipartite) graph G. In the bipartite case the two vertex classes of H are designated by X and Y.

1. Let d = r^{2} + 1. Partition arbitrarily the vertex set of G into sets W_{1}, W_{2}, …, W_{d} of nearly equal size. (In the bipartite case, we only subdivide V_{2}, and only into W_{1}, …, W_{r^{2}}.)

2. Apply the well known theorem of Hajnal and Szemerédi [9] to the square of H and obtain a partition of its vertex set into two-independent sets Y_{1}, …, Y_{d} of nearly equal size. (In the bipartite case, we only subdivide Y, and only into r^{2} sets Y_{1}, …, Y_{r^{2}}.)

3. Construct the embedding f of H into G. The embedding f will map each Y_{i} into W_{i}. We proceed in rounds; during round i we construct f : Y_{i} → W_{i}, so the construction of f takes d rounds. (In the bipartite case, we first randomly map X into V_{1}, then simultanously construct f : Y_{i} → W_{i} for each i = 1, …, r^{2}.)

The construction of the embedding f in Step 3 will heavily rely on finding saturating matchings in some auxiliary bipartite graphs. Step 2 is crucial in order to have probabilistic independence between edges of these auxiliary graphs. Step 1 is performed merely to conform with Step 2. We will expand on Step 3 outlined above in the proofs of Theorems 1.2, 1.3, and 1.4.

In [14] matchings are secured by maintaining the auxiliary graphs sufficiently dense, εregular and with high minimum degree. It is easy to see that such graphs have perfect matchings (this is a special case of Proposition B.2, below). As the density of our random graphs is o(1) this approach does not work here.

In [3] the (perfect) matchings are forced by an old result of Erdős and Rényi [8] (cf. [10], Theorem 4.1, page 83). The auxiliary graphs are genuine random graphs themselves with edge probability at least p^{r}, and as long as p^{r} is bigger than log n/n, there is a.a.s. a perfect matching.

This way it has been shown in [3] that for every fixed graph H ∈ H(r, n), if p = cn^{−1/r}(log n)^{1/r}, for any c > 3, then G(n, p) contains a.a.s. a copy of H (see e.g. [10], Theorem 4.13, page 94). Therefore, by a simple averaging argument, G(n, p) with that p contains a.a.s. almost all such graphs H. To show that G(n, p), or later G(n, n, p), contains a.a.s. all of them, we have to find conditions that hold for a typical random graph, and such that for any graph G satisfying those conditions, the auxiliary graphs we define in the process of embedding contain the required matchings, and consequently G contains each H as a subgraph.

The existence of the required matchings is obtained using Hall’s Theorem. See the appendix for more details.

4 Fault-tolerance of random bipartite graphs

The proof of Theorem 1.4 is based on a combination of a sparse version of the regularity lemma with a hypergraph packing result and several additional ideas. This proof is more complicated than the previous proofs in this paper and requires, besides Proposition B.3 and Lemma B.6, three additional lemmas. We describe these lemmas here and present the actual proof in the appendix. The first lemma is a special case of Lemma 20 in [11] (with α, γ, k, q replaced, resp., by ξ/2, 1/2, r, p). For a bipartite graph F with vertex classes U and W and for any non-empty subsets U′ ⊂ U and W′ ⊂ W, we denote by e_{F} (U′, W′) the number of edges between U′ and W′, and by

d_{p,F} (U′, W′) = \frac{e_{F} (U′, W′)}{p|U′||W′|}  (2)

the p-density of the pair (U′, W′) in F, where 0 < p ≤ 1. In particular, we set d_{F} (U′, W′) = d_{1,F} (U′, W′). We say that the pair (U′, W′) is (p; ε)-regular in F if

|d_{p,F} (U′, W′) − d_{p,F} (U′′, W′′)| < ε  (3)

for all U′′ ⊂ U′ and all W′′ ⊂ W′ for which |U′′| ≥ ε|U′| and |W′′| ≥ ε|W′|. A pair which is not (p; ε)-regular is sometimes called (p; ε)-irregular. If U′ = U and W′ = W, we then also say that F is (p; ε)-regular. For a set R ∈ [U]^{r} (that is, an r-element subset of U), we define its joint degree as

deg_{F} (R) = | ⋂_{x∈R} N_{F} (x)| ,  (4)

that is, deg_{F} (R) is the number of stars (v, R). Finally, G[U, W] stands for the subgraph of G induced by U ∪ W.

Lemma 4.1 ([11]) For all r ≥ 2, ξ > 0, and η > 0, there is ε > 0 such that a.a.s. G = G(n, n, p) with p ≥ n^{−3/5r} satisfies the following property. Suppose U ⊂ V_{1}, W ⊂ V_{2} are sets of size at least n^{2/3}, and F is a (p; ε)-regular subgraph of G[U, W] with e_{F} (U, W) ≥ ξe_{G}(U, W). Then

|\{R ∈ [U]^{r} : deg_{F} (R) < \frac{1}{2}(d_{F} (U, W))^{r}|W |\}| ≤ η\binom{|U|}{r}.  (5)

Our next tool is the following sparse version of Szemerédi’s celebrated Regularity Lemma (see e.g. [10], page 215, Lemma 8.18). For 0 < p < 1, b ≥ 1 and β > 0, call a graph Γ (p; b, β)-bounded if for every pair of disjoint subsets U, W ⊂ V (Γ) with |U|, |W | ≥ β|V (Γ)| we have d_{p,Γ}(U, W) ≤ b. Furthermore, let Π = (Π_{1}, …, Π_{k}) be a partition of V (Γ) and suppose k divides |V (Γ)|. We say that this partition is (p; Γ, ε, k)-regular if |Π_{1}| = |Π_{2}| = … = |Π_{k}| and for all except at most ε\binom{k}{2} choices of the indices 1 ≤ i < j ≤ k, the pairs (Π_{i}, Π_{j}) are (p; ε)-regular in Γ. In the lemma below we begin with a bipartite graph and obtain a partition which subdivides the original bipartition.

Lemma 4.2 For all ε > 0, b ≥ 1 and k_{0} > 0 there exist β > 0 and K such that the following holds. For every choice of the scaling factor p, and a (p; b, β)-bounded bipartite graph Γ on a vertex set V = V_{1} ∪ V_{2}, where |V_{1}| = |V_{2}| is divisible by K!, there exists a subpartition Π = (Π_{1}^{1}, …, Π_{k}^{1}, Π_{1}^{2}, …, Π_{k}^{2}) of (V_{1}, V_{2}) which is (p; Γ, ε, 2k)-regular for some k ≤ K.

We will also need a hypergraph packing result. As a preparation for it, given an r-uniform hypergraph B on m vertices and η > 0, let us define a recursive family of j-uniform hypergraphs B_{j}^{η}, j = r, r−1, …, 1. Set B_{r}^{η} = B and, given B_{j}^{η}, define B_{j−1}^{η} as the family of all (j −1)-tuples J which are contained in more than ηm j-tuples of B_{j}^{η}, or in other words, for which deg_{B_{j}^{η}}(J) > ηm.

Now we are ready to quote a special case of Theorem 2 from [15] with some minor changes in notation. The original theorem was proved only for bijections f, which is the tightest case. However, the proof can be literally repeated step by step also in a more relaxed setting when the hypergraph N has fewer vertices than B. We say that a one-to-one function f : V (N) → V (B) is a packing of N and B, if for every B ∈ B and every N ∈ N we have B ≠ f(N), or shortly, f(N)∩B = ∅, where f(N) denotes the image of the hypergraph N. We say that f′′ is obtained from f′ by a switching if for some v, w, we have f′(v) = f′′(w), f′(w) = f′′(v) and f′(u) = f′′(u) for all u ≠ v, w.

Lemma 4.3 ([15]) For all integers r ≥ 2, and for all σ > 0, there exist η > 0 and m_{0} such that the following holds. If N and B are two r-uniform hypergraphs on, resp., m_{1} and m_{2} vertices, m_{0} ≤ m_{1} ≤ m_{2}, satisfying Δ(N) ≤ r and B_{1}^{(η)} = ∅, then at least half of all (m_{2})_{m_{1}} one-to-one functions f′ : V (N) → V (B) can be turned into a packing f of N and B by a sequence of at most σm_{2} switchings.

The derivation of Theorem 1.4 from these lemmas is given in the appendix.

5 Concluding remarks

It would be interesting to close the gap between the upper and the lower bound for the minimum possible number of edges in an H(r, n)-universal graph on n vertices. Note that the lower bound holds even for the number of edges of any graph that contains a reasonable fraction of all rregular graphs on n vertices (when rn is even).

As mentioned in the introduction, our proof of Theorem 1.1, together with the one in [1], supplies an efficient algorithm for finding an embedding of any given member of H(r, n) in the appropriate universal graph constructed here. The proof in [1] uses the Lovász Local Lemma, and the embedding algorithm thus requires an application of its algorithmic version, given in [5] (see also [2]). With a careful implementation, the running time is n(log n)^{O(1)}, for any fixed r.

The application of the Hajnal-Szemerédi theorem in the proofs of Theorems 1.2–1.4 is not essential, but is convenient. Instead one could use the (algorithmic) packing lemma of Sauer and Spencer [17] (we would pack H and the union of 2r^{2} + 2 cliques of order n/(2r^{2} + 2), doubling the number of rounds). Thus, our proofs can be made algorithmic in the sense that if indeed a graph G satisfies the assertions of Lemma B.4, B.5 or B.6, then one can find an embedding of any member of H(r, n) in G in polynomial time, using some standard matching algorithms. However, the problem of checking whether a given graph G satisfies these assertions does not seem to be solvable by a polynomial time algorithm.

References

[1] N. Alon, The strong chromatic number of a graph, Random Structures and Algorithms 3 (1992), 1–7.

[2] N. Alon, A parallel algorithmic version of the local lemma, Random Structures and Algorithms 2 (1991), 367–378. Also: Proc. 32^{nd} Annual FOCS, IEEE (1991), 586–593.

[3] N. Alon and Z. Füredi, Spanning subgraphs of random graphs, Graphs and Combinatorics 8 (1992), 91–94.

[4] N. Alon and R. Yuster, Threshold functions for H-factors, Combinatorics, Probability and Computing 2 (1993), 137–144.

[5] J. Beck, An algorithmic approach to the Lovász Local Lemma, Random Structures and Algorithms 2 (1991), 343–365.

[6] S. N. Bhatt, F. Chung, F. T. Leighton and A. Rosenberg, Universal graphs for boundeddegree trees and planar graphs, SIAM J. Disc. Math. 2 (1989), 145–155.

[7] M. R. Capalbo and S. R. Kosaraju, Small universal graphs, Proc. STOC (1999), 741–749.

[8] P. Erdős and A. Renyi, On random matrices, Publ. Math. Inst. Hung. Acad. Sci. 8 (1964), 455–461

[9] A. Hajnal and E. Szemerédi, Proof of a conjecture of Erdős, in: Combinatorial Theory and its Applications, Vol. II (P. Erdős, A. Rényi and V. T. Sós eds.), Colloq. Math. Soc. J. Bolyai 4, North Holland, Amsterdam 1970, 601–623.

[10] S. Janson, T. Łuczak and A. Ruciński, Random Graphs, Wiley, New York, 2000.

[11] Y. Kohayakawa and V. Rödl, Regular pairs in sparse random graphs I, preliminary version

available at http://www.ime.usp.br/~yoshi/rpI.ps.gz

[12] Y. Kohayakawa, V. Rödl and E. Szemerédi, in preparation.

[13] J. Komlós, G. Sárközy and E. Szemerédi, The Blow-up Lemma, Combinatorica 17 (1997) 109–123

[14] V. Rödl, A. Ruciński, Perfect matching in ε-regular graphs and the Blow-up Lemma, Combinatorica 19 (3) (1999) 437–452.

[15] V. Rödl, A. Ruciński and A. Taraz, Hypergraph packing and graph embedding, Combinatorics, Probability and Computing 8 (1999) 363–376.

[16] A. Ruciński, Matching and covering the vertices of a random graph by copies of a given graph, Discrete Math. 105 (1992), 185–197.

[17] N. Sauer and J. Spencer, Edge disjoint placement of graphs, J. Combinatorial Theory Ser. B, 25 (1978), 295–302.

A More details for Section 2

Lemma A.1 Let H be a graph, such that the strong chromatic number of any graph obtained from it by adding an arbitrary number of isolated vertices is at most k, and let V_{1}, V_{2}, …, V_{p} be sets that partition V (H), such that, writing |V_{i}| = n_{i}, the inequality n_{i} ≥ k(k + 1) holds for all i. For each 1 ≤ i ≤ p, and 1 ≤ j ≤ k + 1, let n_{ij} be an integer such that ∑_{j=1}^{k+1} n_{ij} = n_{i} and n_{ij} ≤ ⌈n_{i}/(k + 1)⌉ for all i, j. Then there is a partition of the vertices of H into k + 1 pairwise disjoint sets U_{1}, U_{2}, …, U_{k+1}, such that |V_{i} ∩ U_{j}| = n_{ij} for each i and j and such that each of the sets U_{j}, besides, possibly, the last one, U_{k+1}, is an independent set in H.

Proof: Add to each set V_{i} the smallest required number of isolated vertices to obtain a set V′_{i} of cardinality divisible by k. Now split each of these modified sets V′_{i} to subsets of cardinality k each, where all the vertices of V′_{i} which are not in V_{i} lie in the same subset. Next, find a k-coloring so that each color class contains precisely one vertex of each of the subsets. Let W_{1}, …, W_{k} be the color classes. Observe that |V_{i} ∩ W_{j}| ≥ ⌊n_{i}/k⌋ ≥ ⌈n_{i}/(k + 1)⌉ ≥ n_{ij}, for all i and j, where here we used the fact that n_{i} ≥ k(k + 1) in the middle inequality. Now simply let U_{j}, for 1 ≤ j ≤ k, be any subset of W_{j} containing precisely n_{ij} vertices of V_{i} ∩ W_{j} for all j, and let U_{k+1} contain all the remaining vertices.

Proof of Theorem 1.1: Given two integers n and k, with n ≥ (k + 1)^{2}, we next describe a graph G_{k,n} on n vertices, and show that it contains every graph on n vertices whose strong chromatic number is at most k. We first present some terminology. Let K be the set of letters {1, 2, …, k, ∗}, and for each integer q, let K(q) denote the (k+1)^{q} words of length q with letters in K. We specify the integer n_{u}, for each u ∈ K(q), inductively on q; we first specify n_{u} for each u ∈ K(1) = K. Write n = x_{1} + x_{2} + … + x_{k} + x_{∗}, where x_{1}, …, x_{k}, x_{∗} is a nonincreasing sequence of integers such that x_{∗} + 1 ≥ x_{i} for all i ∈ K; let n_{u} = x_{u} for each u ∈ K = K(1). Note that this uniquely specifies n_{u} for u ∈ K(1). Now for general q, let us assume that we have specified n_{u′} for each u′ ∈ K(q − 1); we next specify n_{u} for each u ∈ K(q). Each u ∈ K(q) can be written uniquely as u′j, with u′ ∈ K(q − 1), and j ∈ K. Write n_{u′} = x_{u′1} + … + x_{u′k} + x_{u′∗}, where x_{u′1}, x_{u′2}, …, x_{u′k}, x_{u′∗} is a nonincreasing sequence of integers such that x_{u′∗} +1 ≥ x_{u′i} for all i ∈ K; let n_{u′i} = x_{u′i} for each i ∈ K. Note that this uniquely specifies n_{u} for each u ∈ K(q), and that ∑_{u∈K(q)} n_{u} = n for all q, and also that n_{u} − n_{v} ≤ 1 for each u, v ∈ K(q). We have specified n_{u} for each u ∈ K(q) for each positive integer q. Now let s be an integer such that (k + 1)^{s} ≤ n < (k + 1)^{s+1}. Observe that n_{u} ≤ (k + 1)^{2} for each u ∈ K(s − 1).

We now present the construction of G_{k,n}. The vertex set V of G_{k,n} consists of n vertices partitioned into (k + 1)^{s−1} sets, where each such set B_{u} corresponds to a u ∈ K(s − 1), and has cardinality n_{u}. The edge set E of G_{k,n} can be described as follows. Let x be a vertex in B_{u}, and y a vertex in B_{v}, with u and v not necessarily distinct words in K(s − 1). Write u = u_{1} … u_{s−1}, and v = v_{1} … v_{s−1}, with each u_{i} and v_{i} in K. Put xy ∉ E if and only if there exists an index i ≤ s − 1 such that u_{i} = v_{i} ≠ ∗.

Let us estimate the number of edges of G_{k,n}. There are precisely \binom{s−1}{i}k^{s−1−i} blocks indexed by vectors with i stars, and each vertex in such a block is connected to the vertices in k^{s−1−i}(k+ 1)^{i} blocks. Since each block contains at most (k + 1)^{2} vertices, the total number of edges does not exceed

∑_{i=0}^{s−1} \binom{s − 1}{i}k^{s−1−i}k^{s−1−i}(k + 1)^{i}(k + 1)^{4} = (k^{2} + k + 1)^{s−1}(k + 1)^{4}.

Recalling that n ≥ (k + 1)^{s}, we conclude that the number of edges is at most

n^{2}(k + 1)^{2} (1 − \frac{k}{(k + 1)^{2}} )^{s−1} ≤ n^{2}O(k^{2}e^{− \frac{k log n}{(k+1)^{2} log(k+1)}} ) ≤ n^{2−Ω(1/k log k)},

where the last inequality holds for all n > n_{0}(k).

To complete the proof of Theorem 1.1 it suffices, in view of Theorem 2.1(i), to prove that G_{k,n} contains any graph H on n vertices whose strong chromatic number does not exceed k. This is similar to the proof of Proposition 2.2, and can be done using Lemma A.1.

B Embedding via bipartite matchings

A standard way to guarantee a matching in a bipartite graph is via Hall’s condition, which can be stated as follows. For two disjoint subsets of vertices S and T of a graph A, we write e_{A}(S, T) for the number of edges with one endpoint in S and the other in T.

Proposition B.1 Let A = (Y, W, E) be a bipartite graph such that |Y | = m_{1} and |W | = m_{2}, with m_{2} ≥ m_{1}. If e_{A}(S, T) > 0 for every two sets S ⊂ Y and T ⊂ W of sizes |T | > m_{2} − |S|, then A has a matching saturating Y.

We will use the above result in the proof of Theorem 1.2. There are several stronger conditions which imply Hall’s condition. We list two of them to be used later in the proofs of Theorems 1.3 and 1.4. Their proofs are too easy to be given here.

Proposition B.2 Let A = (Y, W, E) be a bipartite graph such that |Y | = |W | = n, with minimum degree δ(A) ≥ δ. If e_{A}(S, T) > 0 for every two sets S ⊂ Y and T ⊂ W of size δ, then A has a perfect matching.

Proposition B.3 Let A = (Y, W, E) be a bipartite graph such that |Y | = m_{1} and |W | = m_{2}, where m_{2} ≥ m_{1}. If there are integers δ and x, 1 ≤ δ < x, such that

(i) deg_{A}(y) ≥ δ for every y ∈ Y, (ii) e_{A}(S, T) ≤ δ|T ||S|/x for every two sets S ⊂ Y and T ⊂ W of size δ ≤ |T | < |S| < x, and (iii) e_{A}(S, T) > 0 for every two sets S ⊂ Y and T ⊂ W of size |S| ≥ x and |T | > m_{2} − |S|, then A has a matching saturating Y.

In order to verify some of these conditions we will need the following lemmas about properties of random graphs. Given a vertex v and a set R of at most r vertices, where v ∉ R, we say that the pair (v, R) forms a star if v is joined to every vertex of R.

Lemma B.4 Fix ε > 0 and set N = (1 + ε)n. Let V_{0} be a fixed subset of the vertex set V of the random graph G(N, p), where |V_{0}| = N/d, d = r^{2} + 1 and r ≥ 2. If p = cn^{−1/r}(log n)^{1/r}, c > (4dε(r + 1))^{−1/r}, then a.a.s. G(N, p) satisfies the following properties:

(a) There are at most (1 + ε)^{2}cn^{2−1/r}(log n)^{1/r} edges.

(b) For every collection S of s ≤ n/d pairwise disjoint, non-empty subsets of V \ V_{0}, each of size at most r, and for every set T ⊂ V_{0} of t = N/d−s vertices, there is at least one star (v, S), where v ∈ T and S ∈ S.

Proof: Part (a) follows by the standard estimates for binomial distributions (or simply by Chebyshev’s inequality). To prove the assertion of part (b), note that the probability it fails is at most

∑_{s=1}^{n/d} \binom{N}{r}^{s}\binom{N/d}{s}(1 − p^{r})^{st} ≤ ∑_{s=1}^{n/d} N^{rs}N^{s}e^{−εc^{r}(log n)s/d} = ∑_{s=1}^{n/d} [\frac{N^{r+1}}{n^{εc^{r}/d}} ]^{s} = o(1/n^{3}).

The next two lemmas concern the bipartite random graph. Recall that the designated bipartition of G(n, n, p) is (V_{1}, V_{2}).

Lemma B.5 Set m = ⌊n/r^{2}⌋ and let V_{0} be a fixed subset of V_{2}, where |V_{0}| = m. Then, for all c ≥ 3 and r ≥ 2, a.a.s. the random bipartite graph G(n, n, p), where p = c(log n/n)^{1/2r}, satisfies the following properties:

(a) The minimum and maximum degree are within the range np ± \sqrt{n}.

(b) For every r-element subset S_{0} of V_{1}, the number of stars (v, S_{0}), where v ∈ V_{0}, is at least mp^{r}/2.

(c) For every collection S of s = mp^{r}/2 pairwise disjoint, r-element subsets of V_{1}, and for every s-element subset T of V_{2}, there is at least one star (v, S), where v ∈ T, and S ∈ S.

Proof: Parts (a-b) follow trivially by Chernoff’s bound.

To prove the assertion (c), observe that there are at most \binom{n}{s}n^{rs} < exp\{(r + 1)s log n\} choices of the set T and collection S. Consider an auxiliary bipartite random graph G(s, s, p^{r}) between the selected set T and the s r-tuples of S, whose edges are the stars (v, S) of G(n, n, p). The probability of there being no edges in G(s, s, p^{r}) is smaller than (1 − p^{r})^{s^{2}} < exp{−s^{2}p^{r}} ≤ exp\{−\frac{3^{2r}}{2r^{2}} s log n\}.

Lemma B.6 For all c_{1} > 0 and r ≥ 2, a.a.s. G(n, n, p), where p = c(log n/n)^{1/2r} and c = (5r/c_{1})^{1/2r}, r ≥ 2, satisfies the following properties:

(a) For every two sets U ⊂ V_{1} and W ⊂ V_{2} such that min(|U|, |W |) ≥ n^{1/2r} log n the number of edges e(U, W) between them deviates from the expectation |U||W |p by no more than 0.001|U||W |p.

(b) For all integers t and s, c_{1}p^{r}n ≤ t < s ≤ n, for every selection S of s pairwise disjoint r-element subsets of V_{1}, and for every t-element subset T of V_{2}, the number of stars (v, S), where v ∈ T and S ∈ S, is not bigger than 2stp^{r}.

Proof: Part (a) follows trivially by Chernoff’s bound.

The proof of assertion (b) follows the lines of the proof of Lemma B.5(c). This time, however, we use Chernoff’s bound (see, e.g., [10], Cor. 2.2, page 27), to argue that the probability of there being more than 2stp^{r} edges present in G(s, s, p^{r}) is smaller than exp{−stp^{r}/3} ≤ exp{−5rs log n}.

Proof of Theorem 1.2

Let p = cn^{−1/r}(log n)^{1/r}, where c > (4dε(r + 1))^{−1/r}, d = r^{2} + 1 and r ≥ 2. Let us set, as in Lemma B.4, N = (1 + ε)n. Let V be a set of N vertices, and let W_{1}, …, W_{d} be subsets that partition V such that each W_{i} has cardinality N/d. Let G be any graph on V satisfying conditions (a) and (b) of Lemma B.4, with V_{0} = W_{i}, for each i = 1, …, d. By Lemma B.4, and by the fact that d is a constant independent of n, the random graph G(N, p) a.a.s. satisfies these conditions, so to prove Theorem 1.2, it suffices to show that G is H(r, n)-universal. More specifically, for each H ∈ H(r, n), we will show that there exists an f : V (H) → V that satisfies conditions (I) and (II) given at the beginning of the section.

Fix H ∈ H(r, n). By the Hajnal-Szemerédi Theorem there are sets Y_{1}, …, Y_{d} that partition V (H) so that each Y_{i} is a two-independent set of H, and |Y_{i}| = n/d for each i.

We will define f recursively on each Y_{i}, i = 1, …, d. Let f be any injective embedding from Y_{1} to W_{1}. Let us now assume that we have extended f to Y_{1} ∪ … ∪ Y_{i}, that f(Y_{1} ∪ … ∪ Y_{i}) ⊆ W_{1} ∪ … ∪ W_{i}, and that f is still injective. We now extend f to Y_{i+1}, ensuring that f(Y_{i+1}) ⊆ W_{i+1}.

We define an auxiliary, bipartite graph A_{f}^{(i+1)} between Y_{i+1} and W_{i+1} where there is an edge between y and w if and only if N_{G}(w) ⊂ f(N_{H[Y_{1}∪...∪Y_{i}]}(y)). Suppose that for each y ∈ Y_{i+1}, we are able to map f(y) = w for some w such that yw ∈ A_{f}^{(i+1)}. Since Y_{i+1} is an independent set in H, that will guarantee that f satisfies (II). In order to guarantee (I) also, and therefore to prove Theorem 1.2, it suffices to show that the graph A_{f}^{(i+1)} has a matching M_{i+1} that saturates Y_{i+1}. Then, for each y ∈ Y_{i+1} let f(y) = w, where yw ∈ M_{i+1}.

For each y ∈ Y_{i+1}, let S(y) = f(N_{H[Y_{1}∪...∪Y_{i}]}(y)), and let S_{i+1} = {S(y) : y ∈ Y_{i+1}}. Note that each star in G of the form (w, S(y)), with S(y) ∈ S_{i+1}, and w ∈ W_{i+1} corresponds to the edge yw ∈ A_{f}^{(i+1)}. Also note that S_{i+1} is a collection of disjoint sets in W_{1} ∪ … ∪ W_{i}. This is because Y_{i+1} is two-independent and f is injective. Note also that each S ∈ S_{i+1} has cardinality not greater than r, since the degree of y in H is at most r. Applying Lemma B.4(b), with S = S_{i+1} and V_{0} = W_{i+1}, we see that A_{f}^{(i+1)} satisfies the hypothesis of Proposition B.1. Thus, A_{f}^{(i+1)} has a matching saturating Y_{i+1}, and Theorem 1.2 follows.

Proof of Theorem 1.3

Let p = c(log n/n)^{1/2r}, c ≥ 3, r ≥ 2. Assume for clarity of presentation that n is divisible by r^{2}. Let V_{1} and V_{2} be two disjoint sets of n vertices each, and let W_{1}, …, W_{r^{2}} be sets that partition V_{2} such that |W_{k}| = m = n/r^{2} for all k = 1, …, r^{2}. Let G be a bipartite graph with the two color classes V_{1} and V_{2}, and satisfying properties (a-c) of Lemma B.5 with V_{0} = W_{i}, i = 1, …, r^{2}. Observe that by property (a) G has at most 2cn^{2−1/2r}(log n)^{1/2r} edges. Since a random graph G(n, n, p) a.a.s. satisfies properties (a-c) of Lemma B.5, to prove Theorem 1.3, it suffices to prove that G is H(r, n, n)-universal. More specifically, for each H ∈ H(r, n, n), we will show that there exists an f : V (H) → V_{1} ∪ V_{2} that satisfies (I) and (II).

Fix H ∈ H(r, n, n) and denote by X and Y its two vertex classes. It is easy to show that there exists a bipartite graph H′ on the vertex set X ∪ Y, that contains H as a spanning subgraph, has Δ(H′) ≤ r + 1 and all vertices in Y have degree exactly r. Obviously, if H′ can be embedded into G, then so can be H, and hence we may assume without loss of generality that H already has the above properties of H′. By the Hajnal-Szemerédi Theorem there is a partition Y = Y_{1} ∪ … ∪ Y_{r^{2}}, such that each Y_{i} is two-independent in H and |Y_{i}| = |W_{i}|, i = 1, …, r^{2}.

We will first choose a suitable bijection f : X → V_{1}, and then extend it to Y, by simultaneously specifying f : Y_{i} → W_{i} for all i. Given f : X → V_{1}, define

A_{f}^{(i)} = (Y_{i}, W_{i}, E_{f}^{(i)}), i = 1, 2, …, r^{2} ,

where there is an edge between y and w in E_{f}^{(i)} if and only if N_{G}(w) ⊃ f(N_{H}(y)).

To prove Theorem 1.3, it suffices to show that for some f : X → V_{1} each A_{f}^{(i)} has a perfect matching. To this end, we will use Proposition B.2. Let S_{k} = {N_{H}(y) : y ∈ Y_{i}}. As in the proof of Theorem 1.2, each star of the form (w, N_{H}(y)), with w ∈ W_{i} and y ∈ Y_{i}, corresponds to the edge yw of A_{f}^{(i)}. Therefore, by Lemma B.5(b) with V_{0} = W_{i} we immediately conclude that the degree of each y ∈ A_{f}^{(i)} is at least δ = mp^{r}/2. Also, by Lemma B.5(c) with S being any δ-element subcollection of {N_{H}(y) : y ∈ Y_{i}}, we know that e_{A_{f}^{(i)}}(S, T) > 0 for any subset S ⊆ Y_{i} and any subset T ⊆ W_{i} such that |S| = |T | = δ. In view of Proposition B.2, to show that each A_{f}^{(i)} has a perfect matching, and thus to prove Theorem 1.3, all we need now is the existence of an f such that

(*) for each i = 1, …, r^{2}, every vertex of W_{i} has degree at least δ = mp^{r}/2 in A_{f}^{(i)}.

To achieve this goal we will apply the probabilistic method, i.e., we will choose a bijection f : X → V_{1} uniformly at random and show that it a.a.s. satisfies condition (*).

Observe that f will satisfy (*) if for each i = 1, …, r^{2} and w ∈ W_{i}, there exist at least mp^{r}/2 vertices y ∈ Y_{i} such that f(N_{H}(y)) ⊆ N_{G}(w). Let Z_{w} be the number of vertices y ∈ Y_{i} such that f(N_{H}(y)) ⊆ N_{G}(w). Since G is assumed to satisfy Lemma B.5(a), we have |N_{G}(w)| ≥ np − \sqrt{n} for all w ∈ W_{i}.

We fix w ∈ W_{i} and show that P (Z_{w} ≥ mp^{r}/2) = 1 − o(1/n). Consider the preimage f^{−1}(N_{G}(w)). It is drawn uniformly at random from the space of all subsets of X of order n_{w} = |N_{G}(w)|. Let Z′_{w} be the number of vertices y ∈ Y_{i} such that N_{H}(y) ⊆ f^{−1}(N_{G}(w)). Then Z′_{w} has the same distribution as Z_{w}. We now change the space once again, and compare Z′_{w} to yet another random variable Z′′_{w} which is easier to work with.

Let X_{q} be a random subset of X such that each x ∈ X belongs to X_{q} independently with probability q = n_{w}/n ≥ p − n^{−1/2}. Let Z′′ = |{y : N_{H}(y) ⊆ X_{q}}|. Since the sets N_{H}(y), y ∈ Y_{i}, are mutually disjoint, Z′′ has the binomial distribution Bi(m, q^{r}) with expectation

μ = mq^{r} ≥ 2mp^{r}/3 ≫ \sqrt{n}.

Hence, by Chernoff’s inequality (see e.g. [10], Thm. 2.6, page 26), it follows that

P (Z′′ ≤ mp^{2}/2) ≤ P (Z′′ ≤ 3μ/4)) ≤ exp\{−μ/48\} < exp \{−\sqrt{n}\} .

However, by Pittel’s inequality (see e.g. [10], formula (1.6), page 17),

P (Z_{w} ≤ mp^{r}/2) = P (Z′_{w} ≤ mp^{r}/2) ≤ \sqrt{n_{w}}P (Z′′ ≤ mp^{r}/2) = o(1/n).

So, for each w ∈ W_{i}, Z_{w} ≥ mp^{r}/2 with probability o(1/n), and consequently a.a.s. each vertex in W_{i} has degree at least mp^{r}/2 in A_{f}^{(i)}. Thus, a.a.s. f satisfies (*), which in particular implies that there exists a bijection f such that the hypothesis of Proposition B.2 holds for A_{f}^{(i)}, yielding the existence of a perfect matching in A_{f}^{(i)}. This completes the proof of Theorem 1.3.

C The proof of Theorem 1.4

For convenience, we interchange the roles of α and 1 − α in the definition of α-fault-tolerance. Given r and α, let c_{α,r} = \frac{1}{4r^{2}} (\frac{α}{2})^{r}, and let η < 1/2 be the constant guaranteed by Lemma 4.3 applied with γ = 1/2 and σ = \frac{1}{4}c_{α,r}, but also small enough to make the inequalites (8) and (10), below, true. Then Lemma 4.1, with ξ = \frac{1000}{1001}(α/2) and η^{2^{r}}/r^{2} instead of η, yields an ε. In addition, we assume that ε^{2} < min{0.1α, 1/2r^{2}}. With inputs ε^{2} and b = 1.001, Lemma 4.2 outputs β and K. Set c_{1} = \frac{1}{2Kr^{2}} (\frac{α}{2})^{r} = 2c_{α,r}/K. We will prove Theorem 1.4 with c = c(r, c_{1}) as in Lemma B.6 and C = 2K.

Let G be a bipartite graph with bipartition (V_{1}, V_{2}), where |V_{1}| = |V_{2}| = n, and satisfying properties (a) and (b) of Lemma B.6, as well as the conclusion of Lemma 4.1 with the input constants stated above.

Let Γ be an arbitrary subgraph of G with |E(Γ)| ≥ α|E(G)|. To prove Theorem 1.4, we must show that Γ is H(r, h, h)-universal. By Lemma B.6(a) the graph G is (p; 1.001, β)-bounded for any constant β, and so is Γ. Thus, by Lemma 4.2 applied to Γ with b = 1.001, the scaling factor p and with ε^{2}, we obtain a (p; Γ, ε^{2}, 2k)-regular subpartition Π = (Π_{1}^{1}, …, Π_{k}^{1}, Π_{1}^{2}, …, Π_{k}^{2}) of (V_{1}, V_{2}) for some k, 1 ≤ k ≤ K. We claim that among the k^{2} pairs (Π_{i}^{1}, Π_{j}^{2}) there is a pair (U, W), U ⊂ V_{1}, W ⊂ V_{2}, which is (p; ε^{2})-regular in Γ and has the p-density d_{p,Γ}(U, W) ≥ α/2 + ε^{2}. (Note that then for all U′ ⊂ U and all W′ ⊂ W for which |U′| ≥ ε^{2}|U| and |W′| ≥ ε^{2}|W |, we have d_{p,Γ}(U′, W′) ≥ α/2, or equivalently, d_{Γ}(U′, W′) ≥ αp/2.)

Indeed, using again Lemma B.6(a) and the fact that Γ ⊂ G, the number of edges in the (p; ε^{2})-irregular pairs is at most ε^{2}\binom{2k}{2}(n/k)^{2}(1.001)p < 2ε^{2}n^{2}(1.001)p. Hence the remaining

α(0.999)n^{2}p − 2ε^{2}n^{2}(1.001)p > (α/2 + ε^{2})n^{2}p

edges of Γ all stretch along the (p; ε^{2})-regular pairs, and by the Pigeon-Hole Principle at least one of these pairs, say (U, W), must contain at least (α/2 + ε^{2})n^{2}p/k^{2} ≥ (α/2 + ε^{2})p|U||W | edges. We will show that already the subgraph F = Γ[U, W] alone is H(r, h, h)-universal.

Note that |U| = |W | = n/k ≥ n/K > 2h. Set l = n/k and without loss of generality assume that l is divisible by r^{2}. Split arbitrarily W = W_{1} ∪ … ∪ W_{r^{2}} so that |W_{1}| = … = |W_{r^{2}}| = l/r^{2}. Let us also set m = l/r^{2}.

Fix H ∈ H(r, h, h) and denote by X and Y its two vertex classes. We may assume without loss of generality that H is r-regular, since otherwise one could make it so by adding at most r^{2} new vertices. Also, we may assume that h is divisible by r^{2}.

As in the proof of Theorem 1.3, by the Hajnal-Szemerédi Theorem, there is a partition Y = Y_{1} ∪ … ∪ Y_{r^{2}}, such that each Y_{i} is two-independent in H and |Y_{i}| = h/r^{2}. Note that for each i = 1, …, r^{2} and for every two distinct vertices y_{1} and y_{2} of Y_{i} their neighborhoods N_{H}(y_{1}) and N_{H}(y_{2}) are disjoint r-tuples in X. We will construct an injective embedding f : V (H) → U ∪ W of H into F, such that, as in the proof of Theorem 1.3, f(X) ⊆ U, and f(Y_{i}) ⊆ W_{i} for each i = 1, …, r^{2}.

For any injection f : X → U define now r^{2} auxiliary bipartite graphs

A_{f}^{(i)} = (Y_{i}, W_{i}, E_{f}^{(i)}) , i = 1, 2, …, r^{2} ,

where there is an edge between y and w in E_{f}^{(i)} if and only if N_{F} (w) ⊃ f(N_{H}(y)). To prove Theorem 1.4, it suffices to show that there exists an f : X → U such that each A_{f}^{(i)} contains a matching M_{i} that saturates Y_{i}. Indeed, then we will be able to extend f to Y: for each y ∈ Y_{i}, set f(y) = w, where w ∈ W_{i} is such that yw ∈ M_{i}. To show there exists such an f, we use Proposition B.3 and Lemma 4.3.

First notice that condition (ii) of Proposition B.3 is satisfied for each A_{f}^{(i)} with any δ ≥ c_{1}p^{r}n and x = δ/(2p^{r}) for arbitrary f. To see this, we use similar reasoning as in the proof of Theorem 1.3. Let S ⊂ Y_{i}, S = {N_{H}(y) : y ∈ S}, and T ⊆ W_{i} such that δ ≤ |T | < |S| < x. Since e_{A_{f}^{(i)}}(S, T) equals the number of stars (v, S) in F, where v ∈ T and S ∈ S, and since F ⊂ G, we conclude by Lemma B.6(b) that

e_{A_{f}^{(i)}}(S, T) ≤ 2|S||T |p^{r} = δ|S||T |/x.

Our choice will be δ = 2c_{α,r}p^{r}l and thus x = c_{α,r}l. Note that δ ≥ c_{1}p^{r}n because lK ≥ lk = n.

It remains to show that there exists an f such that each A_{f}^{(i)}, i = 1, 2, …, r^{2}, satisfies conditions (i) and (iii) of Proposition B.3 simultaneously.

Our plan is to pick first a random f′ and show, via Lemma 4.3, that with positive probability it satisfies a condition (i)′ which is weaker than (i), and a condition (iii)′ which is stronger than (iii). Then we will argue that the existence of any such f′ implies the existence of an f′′ for which conditions (i) and (iii) of Proposition B.3 hold.

To this end, we introduce some more notation and definitions. Let N be the hypergraph whose vertex-set is X and whose hyperedges are the sets N_{H}(y), y ∈ Y. Since H is r-regular, note that N is both r-regular and r-uniform.

Now let us set q = αp/2 for convenience, and for every W′ ⊂ W and U′ ⊂ U, we define the hypergraph B(U′, W′). The vertex set of B(U′, W′) is U′, and the edges of B(U′, V′) are the r-tuples R in [U′]^{r} with fewer than \frac{1}{2}q^{r}|W′| common neighbors in W′. We set B(U′) = ⋃_{i=1}^{r^{2}} B(U′, W_{i}).

Suppose we can show that for some U′ ⊆ U there exists an injective function f : X → U′ such that

f(N) ∩ B(U′) = ∅.  (6)

We claim that then each A_{f}^{(i)}, i = 1, …, r^{2}, satisfies condition (i) of Proposition B.3. To see this, fix i and an arbitrary y ∈ Y_{i} and note that (6) implies that f(N_{H}(y)) ∉ B(U′, W_{i}). This, in turn, implies that there must be at least q^{r}m/2 common neighbors of f(N_{H}(y)) in W_{i}, i.e., the degree of y in A_{f}^{(i)} must be at least q^{r}m/2. Since q^{r}m/2 ≥ c_{1}p^{r}n, it follows that each A_{f}^{(i)} satisfies (i) if f satisfies (6). Using Lemma 4.3, we will next show the existence of an f that satisfies (6) and (iii) simultaneously, .

We now describe the set U′ for which such an f will be found. Set B = B(U) and note that each subgraph F [U, W_{i}] is (p, (εr)^{2})-regular and has at least

q|U||W_{i}| ≥ \frac{1000}{1001}(α/2)e_{G}(U, W_{i})

edges, where the lower bound holds by Lemma B.6(a). Since (εr)^{2} < ε, Lemma 4.1 with ξ = \frac{1000}{1001}(α/2) and η replaced by η^{2^{r}}/r^{2} implies that |B| < η′\binom{l}{r}, where η′ = η^{2^{r}}, for some positive η < 1/2.

Let us define a preliminary, recursive family of j-uniform hypergraphs B_{j}, j = r, r −1, …, 1. Set B_{r} = B and, given B_{j}, define B_{j−1} as the family of all (j − 1)-tuples J which belong to more than (η′)^{1/2^{r−j+1}}l j-tuples of B_{j}, or in other words, for which the (hyper)degree deg_{B_{j}}(J) > (η′)^{1/2^{r−j+1}}l. One can easily prove by induction that |B_{j}| < (η′)^{1/2^{r−j}} \binom{l}{j}, which for j = 1 sets a bound of (η′)^{1/2^{r−1}}l = η^{2}l for the number of “bad” vertices, i.e., the singletons which are the hyperedges of B_{1}.

Let us remove them from U; the resulting set is U′. Let us also set |U′| = l′, and B′ = B(U′). Note that l′ ≥ (1 − η^{2})l, where we recall that l = |U|, and so |U′| ≥ |X|, since |X| ≤ l/2. The proportion of bad and good r-sets may have changed, but still (since η < 1/2)

|B′| < η′\binom{l}{r} < η\binom{l′}{r} .

Let us define (B′)_{r}^{η} = B′ and, for each j = r, …, 2,

(B′)_{j−1}^{η} = {J ∈ [U′]^{j−1} : deg_{(B′)_{j}^{η}}(J) > ηl′} .

Then, it can be proved by induction that (B′)_{j}^{η} ⊆ B_{j} ∩[U′]^{j}, j = r, r−1, …, 1, and in particular, (B′)_{1}^{η} = ∅. Hence, by Lemma 4.3 with γ = 1/2 at least half of the injections f′ : X → U′ satisfy the following property (i)′:

(i)′ f′ can be turned into an injective f′′ that satisfies (6) by a sequence of at most σl′ switchings.

The fact that the number of switchings needed is small is crucial, because we still need to show that the switchings lead to an f′′ for which A_{f′′}^{(i)} also satisfies condition (iii) of Proposition B.3. To achieve this task it will be helpful to know that f′ satisfies yet another property:

(iii)′ For all i = 1, …, r^{2}, all S ⊂ Y_{i}, and all T ⊂ W_{i}, where s = |S| ≥ x and |T | = m − s, we have, with N_{S} = {N_{H}(y) : y ∈ S} and D = 8 (1 − log c_{α,r}),

|f′(N_{S}) ∩ B(U′, T)| < \frac{Ds}{log(1/η)} .  (7)

In Claim C.1, below, we show that a random injection f′ a.a.s. satisfies property (iii)′. Taking this claim for granted, it follows that for a positive fraction of injections f′ : X → U′ conditions (i)′ and (iii)′ hold simultaneously. We will now show that for any such f′ a series of at most σl′ switchings leads to an injection f′′ which satisfies both conditions (i) and (iii) of Proposition B.3.

Let S ⊂ Y_{i} and T ⊂ W_{i}, where s = |S| ≥ x and |T | = m − s For any injection f : X → U′, let us call a vertex y ∈ S T -good under f if f(N_{H}(y)) ∉ B(U′, T). By definition, every T -good vertex sends in A_{f}^{(i)} at least \frac{1}{2}q^{r}|T | edges to T. Property (iii)′ asserts that under f′ there are at least s − \frac{Ds}{log(1/η)} T -good vertices in S.

When transforming f′ to f′′ by a series of at most

σl′ ≤ σl = \frac{1}{4}c_{α,r}l = \frac{x}{4} ≤ \frac{s}{4}

switchings, at most twice that many r-tuples of each f′(N_{i}) will be moved. Hence, for any T and S, at least

s − \frac{Ds}{log(1/η)} − 2σl′ ≥ \frac{s}{2} − \frac{Ds}{log(1/η)} > 0  (8)

vertices of S will be still T -good under f′′, yielding condition (iii) of Proposition B.3 with a surplus. At the same time, by the definition of f′′, it satisfies property (6), and consequently condition (i) of Proposition B.3 as well.

It remains to formulate and prove Claim C.1.

Claim C.1 A random injective f′ : X → U′ a.a.s. satisfies (iii)′.

Proof: The number of choices of i, S and T is at most

r^{2}\binom{h/r^{2}}{s}\binom{m}{s} < r^{2}\binom{l}{s}^{2} .

Since |U′| ≥ (1 − η^{2})l and |T | ≥ (l − h)/r^{2} ≥ l/2r^{2}, the pair (U′, T) is (p; 2ε^{2}r^{2})-regular in F and has at least q|U′||T | ≥ \frac{1000}{1001}(α/2)e_{G}(U′, T) edges, where the lower bound holds, again, by Lemma B.6(a). Since 2ε^{2}r^{2} < ε, another application of Lemma 4.1 (with the same parameters as before), yields that

|B(U′, T)| < η′\binom{l′}{r} ≤ η\binom{l′}{r} .

We may think of a random f′ as of a sequence of random selections of images of the elements of X. As the order in which the images are assigned is immaterial, we may as well begin with the r-tuples belonging to N_{S}. Then, the probability that the j-th of them will be mapped into an r-tuple of B(U′, T) is at most η\binom{l′}{r}/\binom{l′−(j−1)r}{r}. Note that r|N_{S}| ≤ h/r < l′/2 with room to spare. Thus, the probability of the event opposite to (iii)′ can be bounded by

r^{2}\binom{l}{s}^{2}P (Z ≥ \frac{Ds}{log(1/η)}) ,  (9)

where Z is a random variable with the binomial distribution Bi(s, ρ) with parameter

ρ = \frac{η\binom{l′}{r}}{\binom{l′/2}{r}} < 3^{r}η .

To estimate the tail probability, we employ the trivial bound

P (Z ≥ z) < \binom{s}{z}ρ^{z} < (esρ/z)^{z}

with z = \frac{Ds}{log(1/η)}. Since

\frac{1 + r log 3 − log D + log log(1/η) − log(1/η)}{log(1/η)} < −1/2 ,  (10)

we finally get

r^{2}\binom{l}{s}^{2}P (Z ≥ \frac{Ds}{log(1/η)}) < r^{2} ((el/s)^{2}e^{−D/2})^{s} = r^{2}e^{−Ds/4} = o(1) .  (11)

This completes the proof.