Böttcher, Julia; Heinig, Peter; Taraz, Anusch Embedding into bipartite graphs. (English) Zbl 1221.05209 SIAM J. Discrete Math. 24, No. 4, 1215-1233 (2010). Summary: The conjecture of Bollobás and Komlós, recently proved by J. Böttcher, M. Schacht and Taraz [“Proof of the bandwidth conjecture of Bollobás and Komlós,”Math. Ann. 343, No. 1, 175-205 (2009; Zbl 1229.05132)], 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 Y. Zhao [“Bipartite graph tiling,” SIAM J. Discrete Math. 23, No.2, 888–900 (2009; Zbl 1191.05075)], as well as J. Hladký and M. Schacht [“Note on bipartite graph tilings,” SIAM J. Discrete Math. 24, No. 2, 357–362 (2010; Zbl 1213.05138)], 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. Cited in 7 Documents MSC: 05C35 Extremal problems in graph theory 05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) Keywords:graph theory; extremal combinatorics; graph embedding Citations:Zbl 1191.05075; Zbl 1213.05138; Zbl 1229.05132 PDFBibTeX XMLCite \textit{J. Böttcher} et al., SIAM J. Discrete Math. 24, No. 4, 1215--1233 (2010; Zbl 1221.05209) Full Text: DOI arXiv