We prove that asymptotically (as $n\to\infty$) almost all graphs with n vertices and $C_dn^{2-\frac{1}{2d}} \log^{\frac{1}{d}} n$ edges are universal with respect to the family of all graphs with maximum degree bounded by d. Moreover, we provide an efficient deterministic embedding algorithm for finding copies of bounded degree graphs in graphs satisfying certain pseudorandom properties. We also prove a counterpart result for random bipartite graphs, where the threshold number of edges is even smaller but the embedding is randomized.

We investigate the threshold probability for the property that every r-coloring of the edges of a random binomial k-uniform hypergraph ${\mathbb G }^{(k)}(n,p)$ yields a monochromatic copy of some fixed hypergraph G. In this paper we solve the problem for arbitrary $k\geq 3$ and k-partite, k-uniform hypergraphs G.

A bipartite graph G = (U,V;E) is called $\epsilon$-regular if the edge density of every sufficiently large induced subgraph differs from the edge density of G by no more than $\epsilon$. If, in addition, the degree of each vertex in G is between $(d-\epsilon)n$ and $(d+\epsilon)n$, where d is the edge density of G and |U|=|V|=n, then G is called super $(d,\epsilon)$-regular. In [Combinatorica, 19 (1999), pp. 437--452] it was shown that if $S \subset U$ and $T \subset V$ are subsets of vertices in a super-regular bipartite graph G = (U,V;E), and if a perfect matching M of G is chosen randomly, then the number of edges of M that go between the sets S and T is roughly |S||T|/n. In this paper, we derandomize this result using the Erdos--Selfridge method of conditional probabilities. As an application, we give an alternative constructive proof of the blow-up lemma of $\komlos$, $\sarkozy$, and $\szemeredi$ (see [Combinatorica, 17 (1997), pp. 109--123] and [Random Structures Algorithms, 12 (1998), pp. 297--312]).

For any positive integers r and n, let H(r,n) denote the family of graphs on n vertices with maximum degree r, and let H(r,n,n) denote the family of bipartite graphs H on 2n vertices with n vertices in each vertex class, and with maximum degree r. On one hand, we note that any H(r,n)-universal graph must have /spl Omega/(n/sup 2-2/r/) edges. On the other hand, for any n/spl ges/n/sub 0/(r), we explicitly construct H(r,n)-universal graphs G and /spl Lambda/ on n and 2n vertices, and with O(n/sup 2-/spl Omega//(1/r log r)) and O(n/sup 2-1/r/ log/sup 1/r/ n) edges, respectively, such that we can efficiently find a copy of any H /spl epsiv/ H (r,n) in G deterministically. We also achieve sparse universal graphs using random constructions. Finally, we show that the bipartite random graph G=G(n,n,p), with p=cn/sup -1/2r/ log/sup 1/2r/ n is fault-tolerant; for a large enough constant c, even after deleting any /spl alpha/-fraction of the edges of G, the resulting graph is still H(r,/spl alpha/(/spl alpha/)n,/spl alpha/(/spl alpha/)n)-universal for some /spl alpha/: [0,1)/spl rarr/(0,1].

For a tree T a perfect T-matching in a graph G is a subgraph of G with at least $|G| - |T| + 1$ vertices, each component of which is isomorphic to T. Two properties, $\mathcal{A}$ and $\mathcal{B}$, are introduced where the former is a modification of the fact that the largest component of G has a perfect T-matching and the latter is a suitably chosen necessary condition for $\mathcal{A}$ expressed in terms of forbidden “pendant” subgraphs. We show that in the random graph process $\hat G_n $ the hitting times of both above properties coincide. This paper is the first one that deals with the hitting times of nonmonotone graph properties. It extends results of Bollobás and Frieze [Ann. Discrete Math., 28 (1985), pp. 23–46] and Bollobás and Thomason [Ann. Discrete Math., 28 (1985), pp. 47–98].