Series:

Graph Theory Seminar

Thursday, April 9, 2015 - 12:05pm

1 hour (actually 50 minutes)

Location:

Skiles 005

Organizer:

For integers k>=1 and n>=2k+1, the bipartite Kneser graph H(n,k) is defined

as the graph that has as vertices all k-element and all (n-k)-element

subsets of {1,2,...,n}, with an edge between any two vertices (=sets) where

one is a subset of the other. It has long been conjectured that all

bipartite Kneser graphs have a Hamilton cycle. The special case of this

conjecture concerning the Hamiltonicity of the graph H(2k+1,k) became known

as the 'middle levels conjecture' or 'revolving door conjecture', and has

attracted particular attention over the last 30 years. One of the

motivations for tackling these problems is an even more general conjecture

due to Lovasz, which asserts that in fact every connected vertex-transitive

graph (as e.g. H(n,k)) has a Hamilton cycle (apart from five exceptional

graphs).

Last week I presented a (rather technical) proof of the middle levels

conjecture. In this talk I present a simple and short proof that all

bipartite Kneser graphs H(n,k) have a Hamilton cycle (assuming that

H(2k+1,k) has one). No prior knowledge will be assumed for this talk

(having attended the first talk is not a prerequisite).

This is joint work with Pascal Su (ETH Zurich).

as the graph that has as vertices all k-element and all (n-k)-element

subsets of {1,2,...,n}, with an edge between any two vertices (=sets) where

one is a subset of the other. It has long been conjectured that all

bipartite Kneser graphs have a Hamilton cycle. The special case of this

conjecture concerning the Hamiltonicity of the graph H(2k+1,k) became known

as the 'middle levels conjecture' or 'revolving door conjecture', and has

attracted particular attention over the last 30 years. One of the

motivations for tackling these problems is an even more general conjecture

due to Lovasz, which asserts that in fact every connected vertex-transitive

graph (as e.g. H(n,k)) has a Hamilton cycle (apart from five exceptional

graphs).

Last week I presented a (rather technical) proof of the middle levels

conjecture. In this talk I present a simple and short proof that all

bipartite Kneser graphs H(n,k) have a Hamilton cycle (assuming that

H(2k+1,k) has one). No prior knowledge will be assumed for this talk

(having attended the first talk is not a prerequisite).

This is joint work with Pascal Su (ETH Zurich).