Title: Filling the gap between Turán's theorem and Pósa's conjecture
Abstract: Journal of the London Mathematical SocietyVolume 84, Issue 2 p. 269-302 Articles Filling the gap between Turán's theorem and Pósa's conjecture Peter Allen, Peter Allen DIMAP and Mathematics Institute, University of Warwick, Coventry, CV4 7AL, United Kingdom, Current address:, Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508–090 São Paulo, Brazil, [email protected] for more papers by this authorJulia Böttcher, Corresponding Author Julia Böttcher [email protected] Zentrum Mathematik, Technische Universität München, Boltzmannstraße 3, D-85747 Garching bei München, Germany, Current address:, Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508–090 São Paulo, [email protected] for more papers by this authorJan Hladký, Jan Hladký Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Malostranské náměstí 25, 118 00 Prague, Czech Republic, and, DIMAP and Department of Computer Science, University of Warwick, Coventry, CV4 7AL, United Kingdom, [email protected] for more papers by this author Peter Allen, Peter Allen DIMAP and Mathematics Institute, University of Warwick, Coventry, CV4 7AL, United Kingdom, Current address:, Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508–090 São Paulo, Brazil, [email protected] for more papers by this authorJulia Böttcher, Corresponding Author Julia Böttcher [email protected] Zentrum Mathematik, Technische Universität München, Boltzmannstraße 3, D-85747 Garching bei München, Germany, Current address:, Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508–090 São Paulo, [email protected] for more papers by this authorJan Hladký, Jan Hladký Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Malostranské náměstí 25, 118 00 Prague, Czech Republic, and, DIMAP and Department of Computer Science, University of Warwick, Coventry, CV4 7AL, United Kingdom, [email protected] for more papers by this author First published: 13 July 2011 https://doi.org/10.1112/jlms/jdr007Citations: 4 2000 Mathematics Subject Classification 05C35 (primary), 05C38 (secondary). During this work Peter Allen was supported by the University of Warwick and DIMAP, EPSRC award EP/D063191/1, Julia Böttcher by Technische Universität München and DFG grant TA 309/2-1, Jan Hladký by the Charles University grant GAUK 202-10/258009, by DAAD, by BAYHOST, and by DIMAP, EPSRC award EP/D063191/1. AboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onFacebookTwitterLinked InRedditWechat Abstract Much of extremal graph theory has concentrated either on finding very small subgraphs of a large graph (Turán-type results) or on finding spanning subgraphs (Dirac-type results). In this paper, we are interested in finding intermediate-sized subgraphs. We investigate minimum degree conditions under which a graph G contains squared paths and squared cycles of arbitrary specified lengths. We determine precise thresholds, assuming that the order of G is large. This extends results of Fan and Kierstead [J. Combin. Theory Ser. B 63 (1995) 55–64] and of Komlós, Sarközy and Szemerédi [Random Structures Algorithms 9 (1996) 193–211] concerning the containment of a spanning squared path and a spanning squared cycle, respectively. Our results show that such minimum degree conditions constitute not merely an interpolation between the corresponding Turán-type and Dirac-type results, but exhibit other interesting phenomena. Citing Literature Volume84, Issue2October 2011Pages 269-302 RelatedInformation