A graph Γ is said to be universal for a class of graphs H if Γ contains a copy of every H ε H as a subgraph. The number of edges required for a host graph Γ to be universal for the class of D -degenerate graphs on n vertices has been shown to be O ((log n ) 2/D (log log n ) 5 n 2-1/D ). We generalise this result to r-uniform hypergraphs, showing the following. Given D, r ≥ 2 and n sufficiently large, there exists a constant C = C(D, r) such that there exists a graph with at most Cn r−1/D (log n) 2/D (log log n) 2r+1 edges, which is universal for the class of D -degenerate r -uniform hypergraphs on n vertices. This is tight up to the multiplicative constant and polylogarithmic term.

We obtain an approximate sparse hypergraph version of the blow-up lemma, showing that partite hypergraphs with sufficient regularity of small subgraph counts behave as if they were complete partite for the purpose of embedding bounded degree hypergraphs.

We study the problem of finding pairwise vertex-disjoint copies of the ℓ-vertex cycle Cℓ in the randomly perturbed graph model, which is the union of a deterministic n-vertex graph G and the binomial random graph G(n, p). For ℓ ≥ 3 we prove that asymptotically almost surely G U G(n, p) contains min{δ(G), min{δ(G), [n/l]} pairwise vertex-disjoint cycles Cℓ, provided p ≥ C log n/n for C sufficiently large. Moreover, when δ(G) ≥ αn with 0 ≤ α/l and G and is not ‘close’ to the complete bipartite graph Kαn,(1 - α)n, then p ≥ C/n suffices to get the same conclusion. This provides a stability version of our result. In particular, we conclude that p ≥ C/n suffices when α > n/l for finding [n/l] cycles Cℓ. Our results are asymptotically optimal. They can be seen as an interpolation between the Johansson-Kahn-Vu Theorem for Cℓ-factors and the resolution of the El-Zahar Conjecture for Cℓ-factors by Abbasi.

The blow-up lemma established by Komlós, Sárközy, and Szemerédi in 1997 is an important tool for the embedding of spanning subgraphs of bounded maximum degree. Here we prove several generalizations of this result concerning the embedding of $a$-arrangeable graphs, where a graph is called $a$-arrangeable if its vertices can be ordered in such a way that the neighbors to the right of any vertex $v$ have at most $a$ neighbors to the left of $v$ in total. Examples of arrangeable graphs include planar graphs and, more generally, graphs without a $K_s$-subdivision for constant $s$. Our main result shows that $a$-arrangeable graphs with maximum degree at most $\sqrt{n}/\log n$ can be embedded into corresponding systems of superregular pairs. This is optimal up to the logarithmic factor. We also present two applications. We prove that any large enough graph $G$ with minimum degree at least $\big(\frac{r-1}{r}+\gamma\big)n$ contains an $F$-factor of every $a$-arrangeable $r$-chromatic graph $F$ with at most $\xi n$ vertices and maximum degree at most $\sqrt{n}/\log n$, as long as $\xi$ is sufficiently small compared to $\gamma/(ar)$. This extends a result of Alon and Yuster [J. Combin. Theory Ser. B, 66 (1996), pp. 269--282]. Moreover, we show that for constant $p$ the random graph $\mathcal{G}(n,p)$ is universal for the class of $a$-arrangeable $n$-vertex graphs $H$ of maximum degree at most $\xi n/\log n$, as long as $\xi$ is sufficiently small compared to $p/a$.

We prove that for any pair of constants a>0 and D and for n sufficiently large, every family of trees of orders at most n, maximum degrees at most D, and with at most n(n-1)/2 edges in total packs into the complete graph of order (1+a)n. This implies asymptotic versions of the Tree Packing Conjecture of Gyarfas from 1976 and a tree packing conjecture of Ringel from 1963 for trees with bounded maximum degree. A novel random tree embedding process combined with the nibble method forms the core of the proof.

The conjecture of Bollobás and Komlós, recently proved by Böttcher, Schacht, and Taraz [Math. Ann., 343 (2009), pp. 175–205], implies that for any $\gamma>0$, every balanced bipartite graph on $2n$ vertices with bounded degree and sublinear bandwidth appears as a subgraph of any $2n$-vertex graph G with minimum degree $(1+\gamma)n$, provided that n is sufficiently large. We show that this threshold can be cut in half to an essentially best-possible minimum degree of $(\frac{1}{2}+\gamma)n$ when we have the additional structural information of the host graph G being balanced bipartite. This complements results of Zhao [SIAM J. Discrete Math., 23 (2009), pp. 888–900], as well as Hladký and Schacht [SIAM J. Discrete Math., 24 (2010), pp. 357–362], who determined a corresponding minimum degree threshold for $K_{r,s}$-factors, with r and s fixed. Moreover, our result can be used to prove that in every balanced bipartite graph G on $2n$ vertices with minimum degree $(\frac{1}{2}+\gamma)n$ and n sufficiently large, the set of Hamilton cycles of G is a generating system for its cycle space.