printable pdf
比利时vs摩洛哥足彩 ,
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

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