Powers of Hamilton Cycles of High Discrepancy are Unavoidable

Abstract

The Pósa-Seymour conjecture asserts that every graph on n vertices with minimum degree at least (1−1/(r +1))n contains the r-th power of a Hamilton cycle. Komlós, Sárközy and Szemerédi famously proved the conjecture for large n. The notion of discrepancy appears in many areas of mathematics, including graph theory. In this setting, a graph G is given along with a 2-coloring of its edges. One is then asked to find in G a copy of a given subgraph with a large discrepancy, i.e., with significantly more than half of its edges in one color. For r > 2, we determine the minimum degree threshold needed to find the r-th power of a Hamilton cycle of large discrepancy, answering a question posed by Balogh, Csaba, Pluhár and Treglown. Notably, for r > 3, this threshold approximately matches the minimum degree requirement of the Pósa-Seymour conjecture.

Locations

• The Electronic Journal of Combinatorics - View - PDF
• arXiv (Cornell University) - View - PDF
• Repository for Publications and Research Data (ETH Zurich) - View - PDF