{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,22]],"date-time":"2026-06-22T17:37:25Z","timestamp":1782149845968,"version":"3.54.5"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,7,1]],"date-time":"2010-07-01T00:00:00Z","timestamp":1277942400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2010,7]]},"DOI":"10.1007\/s00493-010-2422-5","type":"journal-article","created":{"date-parts":[[2010,10,14]],"date-time":"2010-10-14T01:24:30Z","timestamp":1287019470000},"page":"445-470","source":"Crossref","is-referenced-by-count":11,"title":["A randomized embedding algorithm for trees"],"prefix":"10.1007","volume":"30","author":[{"given":"Benny","family":"Sudakov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Vondr\u00e1k","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2010,10,13]]},"reference":[{"key":"2422_CR1","unstructured":"M. Ajtai, J. Koml\u00f3s, M. Simonovits and E. Szemer\u00e9di: The exact solution of the Erd\u0151s-T. S\u00f3s conjecture for (large) trees, in preparation."},{"issue":"6","key":"2422_CR2","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1007\/s00493-007-2182-z","volume":"27","author":"N. Alon","year":"2007","unstructured":"N. Alon, M. Krivelevich and B. Sudakov: Embedding nearly-spanning bounded degree trees, Combinatorica 27(6) (2007), 629\u2013644.","journal-title":"Combinatorica"},{"key":"2422_CR3","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1006\/jctb.1999.1906","volume":"76","author":"N. Alon","year":"1999","unstructured":"N. Alon, L. R\u00f3nyai and T. Szab\u00f3: Norm-graphs: variations and applications; J. Combinatorial Theory Ser. B 76 (1999), 280\u2013290.","journal-title":"J. Combinatorial Theory Ser. B"},{"key":"2422_CR4","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1214\/aop\/1176988857","volume":"22","author":"I. Benjamini","year":"1994","unstructured":"I. Benjamini and Y. Peres: Markov chains indexed by trees, Ann. Probability 22 (1994), 219\u2013243.","journal-title":"Ann. Probability"},{"key":"2422_CR5","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/PL00001625","volume":"7","author":"I. Benjamini","year":"1997","unstructured":"I. Benjamini and O. Schramm: Every Graph with a Positive Cheeger Constant Contains a Tree with a Positive Cheeger Constant, Geometric and Functional Analysis 7 (1997), 403\u2013419.","journal-title":"Geometric and Functional Analysis"},{"key":"2422_CR6","doi-asserted-by":"crossref","first-page":"1091","DOI":"10.4153\/CJM-1966-109-8","volume":"18","author":"C. T. Benson","year":"1966","unstructured":"C. T. Benson: Minimal regular graphs of girth eight and twelve, Canad. J. Math. 18 (1966), 1091\u20131094.","journal-title":"Canad. J. Math"},{"key":"2422_CR7","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1137\/0402014","volume":"2","author":"S. N. Bhatt","year":"1989","unstructured":"S. N. Bhatt, F. Chung, F. T. Leighton and A. Rosenberg: Universal graphs for bounded-degree trees and planar graphs, SIAM J. Discrete Math. 2 (1989), 145\u2013155.","journal-title":"SIAM J. Discrete Math"},{"key":"2422_CR8","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1016\/0012-365X(95)00207-D","volume":"150","author":"S. Brandt","year":"1996","unstructured":"S. Brandt and E. Dobson: The Erd\u0151s-S\u00f3s conjecture for graphs of girth 5, Discrete Math. 150 (1996), 411\u2013414.","journal-title":"Discrete Math."},{"key":"2422_CR9","first-page":"47","volume":"30","author":"P. Erd\u0151s","year":"1995","unstructured":"P. Erd\u0151s, Z. F\u00fcredi, M. Loebl and V. T. S\u00f3s: Discrepancy of Trees, Studia Sci. Math. Hungarica 30 (1995), 47\u201357.","journal-title":"Studia Sci. Math. Hungarica"},{"key":"2422_CR10","first-page":"215","volume":"7","author":"P. Erd\u0151s","year":"1962","unstructured":"P. Erd\u0151s and A. R\u00e9nyi: On a problem in the theory of graphs (in Hungarian), Publ. Math. Inst. Hungar. Acad. Sci. 7 (1962), 215\u2013235.","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"issue":"1","key":"2422_CR11","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF02579202","volume":"7","author":"J. Friedman","year":"1987","unstructured":"J. Friedman and N. Pippenger: Expanding graphs contain all small trees, Combinatorica 7(1) (1987), 71\u201376.","journal-title":"Combinatorica"},{"key":"2422_CR12","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1006\/jctb.2001.2049","volume":"832","author":"T. Jiang","year":"2001","unstructured":"T. Jiang: On a conjecture about trees in graphs with large girth, J. Combinatorial Theory Ser. B 83(2) (2001), 221\u2013232.","journal-title":"J. Combinatorial Theory Ser. B"},{"key":"2422_CR13","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/S0012-365X(96)00184-7","volume":"165\/166","author":"E. Gy\u0151ri","year":"1997","unstructured":"E. Gy\u0151ri: C 6-free bipartite graphs and product representation of squares, Discrete Math. 165\/166 (1997), 371\u2013375.","journal-title":"Discrete Math."},{"issue":"1\u20133","key":"2422_CR14","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF02808204","volume":"89","author":"P. Haxell","year":"1995","unstructured":"P. Haxell and Y. Kohayakawa: The size-Ramsey number of trees, Israel J. Math. 89(1\u20133) (1995), 261\u2013274.","journal-title":"Israel J. Math."},{"key":"2422_CR15","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/S0012-365X(99)00354-4","volume":"216","author":"P. Haxell","year":"2000","unstructured":"P. Haxell and T. \u0141uczak: Embedding trees into graphs of large girth, Discrete Math. 216 (2000), 273\u2013278.","journal-title":"Discrete Math."},{"key":"2422_CR16","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1002\/1097-0118(200103)36:3<121::AID-JGT1000>3.0.CO;2-U","volume":"36","author":"P. Haxell","year":"2001","unstructured":"P. Haxell: Tree embeddings, J. Graph Theory 36 (2001), 121\u2013130.","journal-title":"J. Graph Theory"},{"key":"2422_CR17","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/BF01261323","volume":"163","author":"J. Koll\u00e1r","year":"1996","unstructured":"J. Koll\u00e1r, L. R\u00f3nyai and T. Szab\u00f3: Norm-graphs and bipartite Tur\u00e1n numbers, Combinatorica 16(3) (1996), 399\u2013406.","journal-title":"Combinatorica"},{"key":"2422_CR18","doi-asserted-by":"crossref","first-page":"50","DOI":"10.4064\/cm-3-1-50-57","volume":"3","author":"T. K\u0151v\u00e1ri","year":"1954","unstructured":"T. K\u0151v\u00e1ri, V. T. S\u00f3s and P. Tur\u00e1n: On a problem of K. Zarankiewicz, Colloquium Math. 3 (1954), 50\u201357.","journal-title":"Colloquium Math."},{"key":"2422_CR19","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1002\/jgt.20048","volume":"48","author":"D. K\u00fchn","year":"2005","unstructured":"D. K\u00fchn and D. Osthus: 4-cycles in graphs without a given even cycle, Journal of Graph Theory 48 (2005), 147\u2013156.","journal-title":"Journal of Graph Theory"},{"key":"2422_CR20","doi-asserted-by":"crossref","unstructured":"M. Krivelevich and B. Sudakov: Pseudo-random graphs, in: More Sets, Graphs and Numbers; Bolyai Society Mathematical Studies 15, Springer, 2006, pp. 199\u2013262.","DOI":"10.1007\/978-3-540-32439-3_10"},{"key":"2422_CR21","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1007\/s00039-009-0713-z","volume":"19","author":"M. Krivelevich","year":"2009","unstructured":"M. Krivelevich and B. Sudakov: Minors in expanding graphs, Geometric and Functional Analysis 19 (2009), 294\u2013331.","journal-title":"Geometric and Functional Analysis"},{"key":"2422_CR22","volume-title":"The Self-Avoiding Walk","author":"N. Madras","year":"1993","unstructured":"N. Madras and G. Slade: The Self-Avoiding Walk, Birkhauser, Boston, 1993."},{"key":"2422_CR23","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/978-3-662-12788-9_6","volume-title":"Probabilistic methods for algorithmic discrete mathematics","author":"C. McDiarmid","year":"1998","unstructured":"C. McDiarmid: Concentration, in: Probabilistic methods for algorithmic discrete mathematics, Algorithms and Combinatorics 16, Springer, Berlin, 1998, pp. 195\u2013248."},{"issue":"5\u20136","key":"2422_CR24","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1017\/S0963548305007029","volume":"14","author":"A. Naor","year":"2005","unstructured":"A. Naor and J. Verstra\u00ebte: A note on bipartite graphs without 2k-cycles, Combinatorics, Probability and Computing 14(5\u20136) (2005), 845\u2013849.","journal-title":"Combinatorics, Probability and Computing"},{"key":"2422_CR25","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0012-365X(76)90068-6","volume":"14","author":"L. P\u00f3sa","year":"1976","unstructured":"L. P\u00f3sa: Hamiltonian circuits in random graphs, Discrete Math. 14 (1976), 359\u2013364.","journal-title":"Discrete Math."},{"issue":"3","key":"2422_CR26","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/s00493-008-2300-6","volume":"28","author":"B. Sudakov","year":"2008","unstructured":"B. Sudakov and J. Verstra\u00ebte: Cycle lengths in sparse graphs, Combinatorica 28(3) (2008), 357\u2013372.","journal-title":"Combinatorica"},{"key":"2422_CR27","first-page":"335","volume":"14","author":"W. F. Vega de la","year":"1979","unstructured":"W. F. de la Vega: Long paths in random graphs, Studia Sci. Math. Hungar. 14 (1979), 335\u2013340.","journal-title":"Studia Sci. Math. Hungar."},{"key":"2422_CR28","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0095-8956(88)90056-1","volume":"45","author":"W. F. Vega de la","year":"1988","unstructured":"W. F. de la Vega: Trees in sparse random graphs, J. Combinatorial Theory Ser. B 45 (1988), 77\u201385.","journal-title":"J. Combinatorial Theory Ser. B"},{"key":"2422_CR29","unstructured":"Y. Zhao: Proof of the (n\/2-n\/2-n\/2) conjecture for large n, manuscript, 2007."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-010-2422-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-010-2422-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-010-2422-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T01:32:47Z","timestamp":1559093567000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-010-2422-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,7]]}},"alternative-id":["2422"],"URL":"https:\/\/doi.org\/10.1007\/s00493-010-2422-5","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,7]]}}}