Powers of Hamilton cycles of high discrepancy are unavoidable
The electronic journal of combinatorics, Tome 29 (2022) no. 3
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.
@article{10_37236_10279,
author = {Domagoj Brada\v{c}},
title = {Powers of {Hamilton} cycles of high discrepancy are unavoidable},
journal = {The electronic journal of combinatorics},
year = {2022},
volume = {29},
number = {3},
doi = {10.37236/10279},
zbl = {1494.05063},
url = {http://geodesic.mathdoc.fr/articles/10.37236/10279/}
}
Domagoj Bradač. Powers of Hamilton cycles of high discrepancy are unavoidable. The electronic journal of combinatorics, Tome 29 (2022) no. 3. doi: 10.37236/10279
Cité par Sources :