%0 Journal Article
%T Filling the gap between Tur¨¢n's theorem and P¨®sa's conjecture
%A Peter Allen
%A Julia B£¿ttcher
%A Jan Hladky
%J Mathematics
%D 2009
%I arXiv
%R 10.1112/jlms/jdr007
%X Much of extremal graph theory has concentrated either on finding very small subgraphs of a large graph (Turan-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 Komlos, Sarkozy, and Szemeredi [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 Turan-type and Dirac-type results, but exhibit other interesting phenomena.
%U http://arxiv.org/abs/0906.3299v3