Discrete Mathematics 2010-2022

A vertex colouring of a hypergraph is $c$-strong if every edge $e$ sees at least $\min\{c, |e|\}$ distinct colours. Let $\chi(t,c)$ denote the least number of colours needed so that every $t$-intersecting hypergraph has a $c$-strong colouring. In 2012, Blais, Weinstein and Yoshida introduced this parameter and initiated study on when $\chi(t,c)$ is finite: they showed that $\chi(t,c)$ is finite whenever $t \geq c$ and unbounded when $t\leq c-2$. The boundary case $\chi(c-1, c)$ has remained elusive for some time: $\chi(1,2)$ is known to be finite by an easy classical result, and $\chi(2,3)$ was shown to be finite by Chung and independently by Colucci and Gy\'{a}rf\'{a}s in 2013. In this talk, we present some recent work with Kevin Hendrey, Freddie Illingworth and Nina Kam\v{c}ev in which we fill in this gap by showing that $\chi(c-1, c)$ is finite in general.

Meeting link:
\[
\text{https://tugraz.webex.com/tugraz/j.php?MTID=m8500c46344212abf0fa37925da5ef9bf}
\]

For integers $k\geq 1$ and $n\geq 2k+1$, the Kneser graph $K(n,k)$ has as vertices all $k$-element subsets of an $n$-element ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Hamilton cycle, with one notable exception, namely the Petersen graph $K(5,2)$. This problem received considerable attention in the literature, including a recent solution for the sparsest case $n=2k+1$. The main contribution of our work is to prove the conjecture in full generality. We also extend this Hamiltonicity result to all connected generalized Johnson graphs (except the Petersen graph). The generalized Johnson graph $J(n,k,s)$ has as vertices all k-element subsets of an n-element ground set, and an edge between any two sets whose intersection has size exactly $s$. Clearly, we have $K(n,k)=J(n,k,0)$, i.e., generalized Johnson graphs include Kneser graphs as a special case. Our results imply that all known families of vertex-transitive graphs defined by intersecting set systems have a Hamilton cycle, which settles an interesting special case of Lovász’ conjecture on Hamilton cycles in vertex-transitive graphs from 1970. Our main technical innovation is to study cycles in Kneser graphs by a kinetic system of multiple gliders that move at different speeds and that interact over time, reminiscent of the gliders in Conway’s Game of Life, and to analyze this system combinatorially and via linear algebra.

This is joint work with Arturo Merino (TU Berlin) and Namrata (Warwick).

Meeting link:
\[
\text{https://tugraz.webex.com/tugraz/j.php?MTID=m8500c46344212abf0fa37925da5ef9bf}
\]