##### Department of Mathematics,

University of California San Diego

****************************

### Math 269 - Combinatorics

## Bartosz Walczak

#### Jagiellonian University

## Sparse Kneser graphs are Hamiltonian

##### Abstract:

For integers $k\geq 1$ and $n\geq 2k+1$, the \emph{Kneser graph} $K(n,k)$ is the graph whose vertices are the $k$-element subsets of $\{1,\ldots,n\}$ and whose edges connect pairs of subsets that are disjoint. The Kneser graphs of the form $K(2k+1,k)$ are also known as the \emph{odd graphs}. We settle an old problem due to Meredith, Lloyd, and Biggs from the 1970s, proving that for every $k\geq 3$, the odd graph $K(2k+1,k)$ has a Hamilton cycle. The proof is based on a reduction of the Hamiltonicity problem in the odd graph to the problem of finding a spanning tree in a suitably defined hypergraph on Dyck words. As a byproduct, we obtain a new proof of the so-called middle levels conjecture. This is joint work with Torsten MÃ¼tze and Jerri Nummenpalo.

Host: Andrew Suk

### February 12, 2019

### 1:00 PM

### AP&M 7321

****************************