{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T06:35:02Z","timestamp":1771050902732,"version":"3.50.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2018,3,5]],"date-time":"2018-03-05T00:00:00Z","timestamp":1520208000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2019,2]]},"DOI":"10.1007\/s00493-017-3701-1","type":"journal-article","created":{"date-parts":[[2018,3,5]],"date-time":"2018-03-05T02:26:02Z","timestamp":1520216762000},"page":"135-151","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Long Cycles in Locally Expanding Graphs, with Applications"],"prefix":"10.1007","volume":"39","author":[{"given":"Michael","family":"Krivelevich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,3,5]]},"reference":[{"key":"3701_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579172","volume":"1","author":"M. Ajtai","year":"1981","unstructured":"M. Ajtai, J. Koml\u00f3s and E. Szemer\u00e9di: The longest path in a random graph, Combinatorica 1 (1981), 1\u201312.","journal-title":"Combinatorica"},{"key":"3701_CR2","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1002\/1097-0118(200011)35:3<193::AID-JGT4>3.0.CO;2-G","volume":"35","author":"N. Alon","year":"2000","unstructured":"N. Alon, M. Krivelevich and P. Seymour: Long cycles in critical graphs, J. Graph Th. 35 (2000), 193\u2013196.","journal-title":"J. Graph Th."},{"key":"3701_CR3","doi-asserted-by":"crossref","first-page":"R6","DOI":"10.37236\/278","volume":"17","author":"J. Balogh","year":"2010","unstructured":"J. Balogh, B. Csaba, M. Pei and W. Samotij: Large bounded degree trees in expanding graphs, Electr. J. Combin. 17 (2010), Publ. R6.","journal-title":"Electr. J. Combin."},{"key":"3701_CR4","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1002\/jgt.3190070115","volume":"7","author":"J. Beck","year":"1983","unstructured":"J. Beck: On size Ramsey number of paths, trees, and circuits. I, J. Graph Th. 7 (1983), 115\u2013129.","journal-title":"J. Graph Th."},{"key":"3701_CR5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511735202","volume-title":"Combinatorial games: Tic-tac-toe theory, Encyclopedia of Mathematics and its Applications 114","author":"J. Beck","year":"2008","unstructured":"J. Beck: Combinatorial games: Tic-tac-toe theory, Encyclopedia of Mathematics and its Applications 114, Cambridge U. Press, Cambridge, 2008."},{"key":"3701_CR6","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.tcs.2012.12.037","volume":"475","author":"M. Bednarska-Bzd\u0229ga","year":"2013","unstructured":"M. Bednarska-Bzd\u0229ga: On weight function methods in Chooser-Picker games, Theor. Comp. Sci. 475 (2013), 21\u201333.","journal-title":"Theor. Comp. Sci."},{"key":"3701_CR7","doi-asserted-by":"publisher","first-page":"823","DOI":"10.1017\/S0963548315000310","volume":"25","author":"M. Bednarska-Bzd\u0229ga","year":"2016","unstructured":"M. Bednarska-Bzd\u0229ga, D. Hefetz, M. Krivelevich and T. \u0141uczak: Manipulative waiters with probabilistic intuition, Combin. Probab. Comput. 25 (2016), 823\u2013849.","journal-title":"Combin. Probab. Comput."},{"key":"3701_CR8","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1002\/1098-2418(200103)18:2<141::AID-RSA1002>3.0.CO;2-W","volume":"18","author":"M. Bednarska","year":"2001","unstructured":"M. Bednarska and T. \u0141uczak: Biased positional games and the phase transition, Random Struct. Alg. 18 (2001), 141\u2013152.","journal-title":"Random Struct. Alg."},{"key":"3701_CR9","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/j.ejc.2003.12.015","volume":"26","author":"M. Bednarska","year":"2005","unstructured":"M. Bednarska and O. Pikhurko: Biased positional games on matroids, Eur. J. Combin. 26 (2005), 271\u2013285.","journal-title":"Eur. J. Combin."},{"key":"3701_CR10","doi-asserted-by":"publisher","first-page":"742","DOI":"10.1016\/j.ejc.2007.02.017","volume":"29","author":"M. Bednarska","year":"2008","unstructured":"M. Bednarska and O. Pikhurko: Odd and even cycles in Maker-Breaker games, Eur. J. Combin. 29 (2008), 742\u2013745.","journal-title":"Eur. J. Combin."},{"key":"3701_CR11","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1016\/j.jctb.2011.10.002","volume":"102","author":"I. Ben-Eliezer","year":"2012","unstructured":"I. Ben-Eliezer, M. Krivelevich and B. Sudakov: The size Ramsey number of a directed path, J. Combin. Th. Ser. B 102 (2012), 743\u2013755.","journal-title":"J. Combin. Th. Ser. B"},{"key":"3701_CR12","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1002\/jgt.20616","volume":"70","author":"I. Ben-Eliezer","year":"2012","unstructured":"I. Ben-Eliezer, M. Krivelevich and B. Sudakov: Long cycles in subgraphs of (pseudo)random directed graphs, J. Graph Th. 70 (2012), 284\u2013296.","journal-title":"J. Graph Th."},{"key":"3701_CR13","first-page":"123","volume":"58","author":"J. Bierbrauer","year":"1987","unstructured":"J. Bierbrauer and A. Gy\u00e1rf\u00e1s: On (n;k)-colorings of complete graphs, Congressus Num. 58 (1987), 123\u2013139.","journal-title":"Congressus Num."},{"key":"3701_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/rsa.20343","volume":"38","author":"T. Bohman","year":"2011","unstructured":"T. Bohman, A. Frieze, M. Krivelevich, P.-S. Loh and B. Sudakov: Ramsey games with giants, Random Struct. Alg. 38 (2011), 1\u201332.","journal-title":"Random Struct. Alg."},{"key":"3701_CR15","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s00493-006-0002-5","volume":"26","author":"S. Brandt","year":"2006","unstructured":"S. Brandt, H. Broersma, R. Diestel and M. Kriesell: Global connectivity and expansion: long cycles in f-connected graphs, Combinatorica 26 (2006), 17\u201336.","journal-title":"Combinatorica"},{"key":"3701_CR16","volume-title":"Proc 18th ACM-SIAM Symp. Discr. Alg. (SODA\u201907)","author":"J. Cain","year":"2007","unstructured":"J. Cain, P. Sanders and N. Wormald: The random graph threshold for korientability and a fast algorithm for optimal multiple-choice allocation, Proc 18th ACM-SIAM Symp. Discr. Alg. (SODA\u201907), 2007."},{"issue":"4","key":"3701_CR17","doi-asserted-by":"crossref","first-page":"P4.38","DOI":"10.37236\/6039","volume":"23","author":"O. Dean","year":"2016","unstructured":"O. Dean and M. Krivelevich: Client Waiter games on complete and random graphs, Electron. J. Combin. 23 (4) (2016), P4.38.","journal-title":"Electron. J. Combin."},{"key":"3701_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-62012-6","volume-title":"Finite Geometries","author":"P. Dembowski","year":"1968","unstructured":"P. Dembowski: Finite Geometries, Springer Verlag, Berlin, 1968."},{"key":"3701_CR19","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1017\/S096354831400056X","volume":"24","author":"A. Dudek","year":"2015","unstructured":"A. Dudek and P. Pra\u0142at: An alternative proof of the linearity of the size-Ramsey number of paths, Combin. Probab. Comput. 24 (2015), 551\u2013555.","journal-title":"Combin. Probab. Comput."},{"key":"3701_CR20","doi-asserted-by":"publisher","first-page":"2079","DOI":"10.1137\/16M1069717","volume":"31","author":"A. Dudek","year":"2017","unstructured":"A. Dudek and P. Pra\u0142at: On some multicolour Ramsey properties of random graphs, SIAM J. Discr. Math. 31 (2017), 2079\u20132092.","journal-title":"SIAM J. Discr. Math."},{"key":"3701_CR21","first-page":"291","volume":"11","author":"R. J. Faudree","year":"2002","unstructured":"R. J. Faudree and R. H. Schelp: A survey of results on the size Ramsey number, in: Paul Erdos and his mathematics II, Bolyai Soc. Math. Stud. Vol. 11, 2002, 291\u2013309.","journal-title":"Bolyai Soc. Math. Stud. Vol."},{"key":"3701_CR22","volume-title":"Proc 18th ACM-SIAM Symp. Discr. Alg. (SODA\u201907)","author":"D. Fernholz","year":"2007","unstructured":"D. Fernholz and V. Ramachandran: The k-orientability Thresholds for Gn;p, Proc 18th ACM-SIAM Symp. Discr. Alg. (SODA\u201907), 2007."},{"key":"3701_CR23","doi-asserted-by":"publisher","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 (1987), 71\u201376.","journal-title":"Combinatorica"},{"key":"3701_CR24","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BF02579271","volume":"1","author":"Z. F\u00fcredi","year":"1981","unstructured":"Z. F\u00fcredi: Maximum degree and fractional matchings in uniform hypergraphs, Combinatorica 1 (1981), 155\u2013162.","journal-title":"Combinatorica"},{"key":"3701_CR25","first-page":"71","volume-title":"Commun. Comput. Automat. Inst. Hungar. Acad. Sci.","author":"A. Gy\u00e1rf\u00e1s","year":"1977","unstructured":"A. Gy\u00e1rf\u00e1s: Partition coverings and blocking sets in hypergraphs (in Hungarian), Commun. Comput. Automat. Inst. Hungar. Acad. Sci. 71 (1977)."},{"key":"3701_CR26","doi-asserted-by":"publisher","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 Th. 36 (2001), 121\u2013130.","journal-title":"J. Graph Th."},{"key":"3701_CR27","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1017\/S0963548300001619","volume":"4","author":"P. E. Haxell","year":"1995","unstructured":"P. E. Haxell, Y. Kohayakawa and T. \u0141uczak: The induced size-Ramsey number of cycles, Combin. Probab. Comput. 4 (1995), 217\u2013239.","journal-title":"Combin. Probab. Comput."},{"key":"3701_CR28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-0825-5","volume-title":"Positional Games","author":"D. Hefetz","year":"2014","unstructured":"D. Hefetz, M. Krivelevich, M. Stojakovi\u0107 and T. Szab\u00f3: Positional Games, Birkh\u00e4user, 2014."},{"key":"3701_CR29","doi-asserted-by":"publisher","first-page":"1525","DOI":"10.1016\/j.disc.2015.12.020","volume":"339","author":"D. Hefetz","year":"2016","unstructured":"D. Hefetz, M. Krivelevich and W. E. Tan: Waiter-Client and Client-Waiter planarity, colorability and minor games, Discr. Math. 339 (2016), 1525\u20131536.","journal-title":"Discr. Math."},{"key":"3701_CR30","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.ejc.2017.02.002","volume":"63","author":"D. Hefetz","year":"2017","unstructured":"D. Hefetz, M. Krivelevich and W. E. Tan: Waiter-Client and Client-Waiter Hamiltonicity games on random graphs, Eur. J. Combin. 63 (2017), 26\u201343.","journal-title":"Eur. J. Combin."},{"key":"3701_CR31","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S. Hoory","year":"2006","unstructured":"S. Hoory, N. Linial and A. Wigderson: Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.) 43 (2006), 439\u2013561.","journal-title":"Bull. Amer. Math. Soc. (N.S.)"},{"key":"3701_CR32","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1002\/rsa.20508","volume":"46","author":"M. Krivelevich","year":"2015","unstructured":"M. Krivelevich, C. Lee and B. Sudakov: Long paths and cycles in random subgraphs of graphs with large minimum degree, Random Struct. Alg. 46 (2015), 320\u2013345.","journal-title":"Random Struct. Alg."},{"key":"3701_CR33","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316479988","volume-title":"Random graphs, Geometry and Asymptotic Structure","author":"M. Krivelevich","year":"2016","unstructured":"M. Krivelevich, K. Panagiotou, M. Penrose and C. McDiarmid: Random graphs, Geometry and Asymptotic Structure, Cambridge U. Press, Cambridge, 2016."},{"key":"3701_CR34","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/978-3-540-32439-3_10","volume":"15","author":"M. Krivelevich","year":"2006","unstructured":"M. Krivelevich and B. Sudakov: Pseudo-random graphs. in: More sets, graphs and numbers, E. Gy\u00f6ri, G. O. H. Katona and L. Lov\u00e1sz, Eds., Bolyai Soc. Math. Stud. Vol. 15, 2006, 199\u2013262.","journal-title":"Bolyai Soc. Math. Stud. Vol."},{"key":"3701_CR35","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1002\/rsa.20470","volume":"43","author":"M. Krivelevich","year":"2013","unstructured":"M. Krivelevich and B. Sudakov: The phase transition in random graphs a simple proof, Random Struct. Alg. 43 (2013), 131\u2013138.","journal-title":"Random Struct. Alg."},{"key":"3701_CR36","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1017\/S0963548315000279","volume":"25","author":"S. Letzter","year":"2016","unstructured":"S. Letzter: Path Ramsey number for random graphs, Combin. Probab. Comput. 25 (2016), 612\u2013622.","journal-title":"Combin. Probab. Comput."},{"key":"3701_CR37","volume-title":"London Math. Soc. Lect. Note Ser. 141","author":"C. McDiarmid","year":"1989","unstructured":"C. McDiarmid: On the method of bounded differences, in: Surveys in Combinatorics 1989, J. Siemons, Ed., London Math. Soc. Lect. Note Ser. 141, Cambridge U. Press, Cambridge, 1989."},{"key":"3701_CR38","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.jctb.2014.01.003","volume":"106","author":"A. Pokrovskiy","year":"2014","unstructured":"A. Pokrovskiy: Partitioning edge-coloured complete graphs into monochromatic cycles and paths, J. Combin. Th. Ser. B 106 (2014), 70\u201397.","journal-title":"J. Combin. Th. Ser. B"},{"key":"3701_CR39","doi-asserted-by":"publisher","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, Discr. Math. 14 (1976), 359\u2013364.","journal-title":"Discr. Math."},{"key":"3701_CR40","doi-asserted-by":"publisher","first-page":"764","DOI":"10.1002\/rsa.20571","volume":"45","author":"O. Riordan","year":"2014","unstructured":"O. Riordan: Long cycles in random subgraphs of graphs with large minimum degree, Random Struct. Alg. 45 (2014), 764\u2013767.","journal-title":"Random Struct. Alg."},{"key":"3701_CR41","doi-asserted-by":"crossref","first-page":"133","DOI":"10.37236\/405","volume":"17","author":"R. Sp\u00f6hel","year":"2010","unstructured":"R. Sp\u00f6hel, A. Steger and H. Thomas: Coloring the edges of a random graph without a monochromatic giant component, Electron. J. Combin. 17 (2010), no. 1, Research Paper 133.","journal-title":"Electron. J. Combin."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-017-3701-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-017-3701-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-017-3701-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,28]],"date-time":"2020-10-28T23:30:38Z","timestamp":1603927838000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-017-3701-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,5]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,2]]}},"alternative-id":["3701"],"URL":"https:\/\/doi.org\/10.1007\/s00493-017-3701-1","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,5]]},"assertion":[{"value":"26 September 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2017","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 March 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}