Advanced search
Start date
Betweenand
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

POWERS OF HAMILTON CYCLES IN PSEUDORANDOM GRAPHS

Full text
Author(s):
Allen, Peter ; Bottcher, Julia ; Han, Hiep ; Kohayakawa, Yoshiharu ; Person, Yury
Total Authors: 5
Document type: Journal article
Source: COMBINATORICA; v. 37, n. 4, p. 573-616, AUG 2017.
Web of Science Citations: 2
Abstract

We study the appearance of powers of Hamilton cycles in pseudorandom graphs, using the following comparatively weak pseudorandomness notion. A graph G is (epsilon,p,k,l)-pseudorandom if for all disjoint X and Y subset of V(G) with |X|>= epsilon p(n)(k) and |Y| >= epsilon p(l)n we have e(X,Y)=(1 +/-epsilon)p|X||Y|. We prove that for all beta > 0 there is an epsilon > 0 such that an (epsilon,p,1,2) -pseudorandom graph on n vertices with minimum degree at least beta pn contains the square of a Hamilton cycle. In particular, this implies that (n,d,lambda)-graphs with lambda << d(5/2)n(-3/2) contain the square of a Hamilton cycle, and thus a triangle factor if n is a multiple of 3. This improves on a result of Krivelevich, Sudakov and Szabo {[}27]. We also extend our result to higher powers of Hamilton cycles and establish corresponding counting versions. (AU)

FAPESP's process: 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science
Grantee:Carlos Eduardo Ferreira
Support type: Research Projects - Thematic Grants
FAPESP's process: 09/17831-7 - Embedding and packing problems in extremal graph theory
Grantee:Julia Boettcher
Support type: Scholarships in Brazil - Post-Doctorate
FAPESP's process: 10/09555-7 - Embedding, randomised and structural problems in extremal graph theory
Grantee:Peter David Allen
Support type: Scholarships in Brazil - Post-Doctorate
FAPESP's process: 13/07699-0 - Research, Innovation and Dissemination Center for Neuromathematics - NeuroMat
Grantee:Jefferson Antonio Galves
Support type: Research Grants - Research, Innovation and Dissemination Centers - RIDC
FAPESP's process: 10/16526-3 - Quasi-random hypergraphs and spanning subhypergraph containment
Grantee:Hiep Han
Support type: Scholarships in Brazil - Post-Doctorate