Powers of Hamilton cycles in directed and oriented graphs.

Abstract: The P\’osa–Seymour conjecture determines the minimum degree threshold for forcing the $k$th power of a Hamilton cycle in a graph. After numerous partial results, Koml\’os,  S\’ark\”ozy and Szemer\’edi proved the conjecture for sufficiently large graphs. We focus on the analogous problem for digraphs and for oriented graphs. For digraphs, we asymptotically determine the minimum total degree threshold for forcing the square of a Hamilton cycle. We also give a conjecture on the corresponding threshold for $k$th powers of a Hamilton cycle more generally. For oriented graphs, we provide a minimum semi-degree condition that forces the $k$th power of a Hamilton cycle, matching the correct order of magnitude of the threshold.

Date: Oct 25, 2024 at 10:00:00 h
Venue: Sala de Seminario John Von Neumann, CMM, Beauchef 851, Torre Norte, Piso 7.
Speaker: Simón Piga
Affiliation: University of Hamburg, Alemania
Coordinator: Matías Pavez
More info at:
Event website
Abstract:
PDF

Posted on Oct 23, 2024 in Seminario de Grafos, Seminars