Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, May 10, 2011, 12:15 pm

Duration: This information is not available in the database

Location: CAB G51

Speaker: Torsten Mütze

Explicit matchings in the middle levels graph

Define the 'middle levels graph' M_{2n+1} of the discrete cube Q_{2n+1} as the bipartite graph whose vertices are all bitstrings of length (2n+1) with exactly n or exactly n+1 entries equal to 1, where two vertices are connected whenever the corresponding bitstrings differ in exactly one bit. By Hall's theorem the graph M_{2n+1} clearly has a perfect matching, but it is surprisingly difficult to find `explicit' constructions of such matchings. In this talk I will present and compare several constructions known from the literature, and also motivate why we are interested in such matchings.

Information for students and suggested topics for student talks