| Full text | |
| Author(s): |
Allen, Peter
;
Boettcher, Julia
;
Han, Hiep
;
Kohayakawa, Yoshiharu
;
Person, Yury
;
Pardo, A
;
Viola, A
Total Authors: 7
|
| Document type: | Journal article |
| Source: | LATIN 2014: THEORETICAL INFORMATICS; v. 8392, p. 12-pg., 2014-01-01. |
| 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, F)- pseudorandom if for all disjoint X, Y subset of (G) with |X|. Spkn 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 [Triangle factors in sparse pseudo- random graphs, Combinatorica 24 (2004), no. 3, 403-426]. We also obtain results for higher powers of Hamilton cycles and establish corresponding counting versions. Our proofs are constructive, and yield deterministic polynomial time algorithms. (AU) | |
| FAPESP's process: | 09/17831-7 - Embedding and packing problems in extremal graph theory |
| Grantee: | Julia Boettcher |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |
| FAPESP's process: | 13/07699-0 - Research, Innovation and Dissemination Center for Neuromathematics - NeuroMat |
| Grantee: | Oswaldo Baffa Filho |
| Support Opportunities: | 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 Opportunities: | Scholarships in Brazil - Post-Doctoral |
| FAPESP's process: | 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science |
| Grantee: | Carlos Eduardo Ferreira |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 10/09555-7 - Embedding, randomised and structural problems in extremal graph theory |
| Grantee: | Peter David Allen |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |