Bipartite Kneser graphs are Hamiltonian

Datum

17.07.2015

Zeit

13:15 - 14:15

Sprecher

Dr. Torsten Muetze

Zugehörigkeit

ETH Zuerich

Sprache

en

Hauptthema

Mathematik

Andere Themen

Mathematik

Host

Jun.-Prof. Dr. Martin Schneider

Beschreibung

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, i.e., a cycle that visits every vertex exactly once. 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 Lovász, 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 year I presented a rather technical proof of the middle levels conjecture in the seminar. 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.

Links

• Institut für Algebra: International Seminar

Letztmalig verändert: 17.07.2015, 13:14:04