EMBEDDING INTO BIPARTITE GRAPHS

The conjecture of Bollobas and Komlos, recently proved by Bottcher, 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 (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 Hladky 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 (1/2 + gamma) n and n sufficiently large, the set of Hamilton cycles of G is a generating system for its cycle space.