{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:26:28Z","timestamp":1787325988102,"version":"build-2736575974"},"reference-count":46,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>The conjecture of Bollob\u00e1s and Koml\u00f3s, recently proved by B\u00f6ttcher, Schacht, and Taraz [Math. Ann., 343 (2009), pp. 175\u2013205], implies that for any $\\gamma&gt;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\u2013900], as well as Hladk\u00fd and Schacht [SIAM J. Discrete Math., 24 (2010), pp. 357\u2013362], 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.<\/jats:p>","DOI":"10.1137\/090765481","type":"journal-article","created":{"date-parts":[[2010,9,30]],"date-time":"2010-09-30T18:48:34Z","timestamp":1285872514000},"page":"1215-1233","source":"Crossref","is-referenced-by-count":7,"title":["Embedding into Bipartite Graphs"],"prefix":"10.1137","volume":"24","author":[{"given":"Julia","family":"B\u00f6ttcher","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Heinig","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anusch","family":"Taraz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,9,29]]},"reference":[{"key":"R1","first-page":"109","volume":"6","author":"Abbasi S.","year":"2000","journal-title":"Graphs Combin."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-48.1.39"},{"key":"R3","first-page":"296","volume":"52","author":"Alon N.","year":"1999","journal-title":"Ars Combin.","ISSN":"https:\/\/id.crossref.org\/issn\/0381-7032","issn-type":"print"},{"key":"R4","unstructured":"N. Alon and J. H. Spencer,\n                      The probabilistic method\n                      , Wiley-Interscience Series in Discrete Mathematics and Optimization, 2nd ed., Wiley-Interscience, New York, 2000."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1996.0020"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(78)90030-8"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.05.002"},{"key":"R8","unstructured":"J. B\u00f6ttcher,\n                      Embedding large graphs\u2014The Bollob\u00e1s-Koml\u00f3s conjecture and beyond\n                      , Ph.D. thesis, Technische Universit\u00e4t M\u00fcnchen, 2009."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2009.10.010"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.11.005"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/s00208-008-0268-6"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.04.002"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008395"},{"key":"R14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.37236\/1022","volume":"14","author":"Csaba B.","year":"2007","journal-title":"Electron. J. Combin.","ISSN":"https:\/\/id.crossref.org\/issn\/1077-8926","issn-type":"print"},{"key":"R15","unstructured":"B. Csaba and M. Mydlarz,\n                      Approximate multipartite version of the Hajnal-Szemer\u00e9di theorem\n                      , arXiv:0807.4463v1 [math.CO]."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(02)00435-1"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.69"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)90079-1"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01285818"},{"key":"R20","unstructured":"P. Heinig,\n                      On prisms, M\u00f6bius ladders and the cycle space of dense graphs\n                      , in preparation."},{"key":"R21","unstructured":"P. Heinig,\n                      Forcing a spanning cyclic ladder graph in bipartite graphs with high minimum degree\n                      , B.Sc. thesis, Technische Universit\u00e4t M\u00fcnchen, 2008."},{"key":"R22","unstructured":"J. Hladk\u00fd and M. Schacht,\n                      Note on bipartite graph tilings\n                      , SIAM J. Discrete Math., to appear."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"S. Janson, T. \u0141uczak, and A. Rucinski,\n                      Random graphs\n                      , Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000.","DOI":"10.1002\/9781118032718"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)00324-6"},{"key":"R25","unstructured":"H. Kaul and A. Kostochka,\n                      Extremal graphs for a graph packing theorem of Sauer and Spencer\n                      , Combin. Probab. Comput., to appear."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2278-0"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10007"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008619"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070020"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1007\/BF01196135"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1007\/BF01626028"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004849"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20076"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"D. K\u00fchn and D. Osthus,\n                      Embedding large subgraphs into dense graphs\n                      , in Surveys in Combinatorics 2009, S. Huczynka, J. Mitchell, and C. Roney-Dougal, eds., Cambridge University Press, London, 2009, pp. 137\u2013167.","DOI":"10.1017\/CBO9781107325975.007"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-009-2254-3"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.04.004"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(85)80035-4"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00373-9"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.08.019"},{"key":"R40","doi-asserted-by":"crossref","first-page":"R109","DOI":"10.37236\/198","volume":"16","author":"Martin R.","year":"2009","journal-title":"Electron. J. Combin.","ISSN":"https:\/\/id.crossref.org\/issn\/1077-8926","issn-type":"print"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1007\/BF02759704"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(78)90005-9"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10091"},{"key":"R44","unstructured":"E. Szemer\u00e9di,\n                      Regular partitions of graphs\n                      , in Probl\u00e8mes combinatoires et th\u00e9orie des graphes (Orsay, 1976), Colloques Internationaux CNRS 260, CNRS, Paris, 1978, pp. 399\u2013401."},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190200209"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1137\/060665397"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090765481","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:25:06Z","timestamp":1787322306000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090765481"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":46,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090765481"],"URL":"https:\/\/doi.org\/10.1137\/090765481","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}