比利时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
****************************