BIMSA >
Research seminar in Discrete Mathematics
Research seminar in Discrete Mathematics
Compatible Hamilton cycles
Compatible Hamilton cycles
Speaker
Allan Lo
Time
Tuesday, November 3, 2026 5:05 PM - 6:15 PM
Venue
Online
Online
Zoom 787 662 9899
(BIMSA)
Abstract
The renowned theorem of Dirac states that if $G$ is a graph with minimum degree at least $n/2$ then $G$ has a Hamilton cycle. A natural generalisation asks what properties of an edge-colouring of $G$ guarantee the existence of a properly edge-coloured Hamilton cycle in $G$.
This concept can be further generalised as follows: an incompatibility system for $G$ is a set $\mathcal{F}$ of `forbidden' pairs of adjacent edges, that is, $\mathcal{F}\subseteq \{\{uv,vw\}\in \binom{E(G)}2\}$. A cycle in $G$ is then compatible if no two of its edges form a pair in $\mathcal{F}$. The system $\mathcal{F}$ is called $\mu n$-bounded if for all $v\in V(G)$ and $uv\in E(G)$, there are at most $\mu n$ pairs $\{uv,vw\} \in \mathcal{F}$. How small must $\mu$ be to guarantee the existence of a compatible Hamilton cycle in $G$?
Krivelevich, Lee and Sudakov showed that $\mu=10^{-16}$ suffices (for $n$ large), while an example of Bollob\'as and Erd\H{o}s shows that $\mu\leq 1/4$ is necessary. In this talk, we show that if $\delta (G) \ge (1/2+\varepsilon)n$, then we have $1/6 \le \mu \le 1/8$.
This is joint work with Natalie Behague (Dublin City), Francesco Di Braccio (LSE) and Bertille Granet (Warwick).
This concept can be further generalised as follows: an incompatibility system for $G$ is a set $\mathcal{F}$ of `forbidden' pairs of adjacent edges, that is, $\mathcal{F}\subseteq \{\{uv,vw\}\in \binom{E(G)}2\}$. A cycle in $G$ is then compatible if no two of its edges form a pair in $\mathcal{F}$. The system $\mathcal{F}$ is called $\mu n$-bounded if for all $v\in V(G)$ and $uv\in E(G)$, there are at most $\mu n$ pairs $\{uv,vw\} \in \mathcal{F}$. How small must $\mu$ be to guarantee the existence of a compatible Hamilton cycle in $G$?
Krivelevich, Lee and Sudakov showed that $\mu=10^{-16}$ suffices (for $n$ large), while an example of Bollob\'as and Erd\H{o}s shows that $\mu\leq 1/4$ is necessary. In this talk, we show that if $\delta (G) \ge (1/2+\varepsilon)n$, then we have $1/6 \le \mu \le 1/8$.
This is joint work with Natalie Behague (Dublin City), Francesco Di Braccio (LSE) and Bertille Granet (Warwick).
Speaker Intro
Allan Lo is a Associate Professor at the University of Birmingham, United Kingdom. His research focuses on graph theory and combinatorics with a strong emphasis on tiling and Hamilton cycles in graphs and hypergraphs.