Monday, November 3, 2014
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
The Ring Loading Problem is an unsplittable multicommodity flow problem on undirected ring networks. Schrijver, Seymour, and Winkler, in a landmark paper from 1998, discuss the problem of turning a split routing solution to the problem into an unsplittable solution without too much increase of the maximum edge load. Among other results they show that any split routing can be turned into an unsplittable solution while increasing the load on any edge of the ring by no more than 1.5D, where D is the maximum demand value. In this lecture we show how to obtain a slightly improved bound of 1.4D and also present an improved lower bound of 1.1D (previously 1.01D) on the best possible bound. Finally, we disprove a long-standing conjecture of Schrijver et al. in this context.
Colloquium - 16:00
Define the middle layer graph as the graph whose vertex set consists of all
bitstrings of length 2n+1 that have exactly n or n+1 entries equal to 1,
with an edge between any two bitstrings that differ in exactly one bit.
The middle levels conjecture asserts that this graph has a Hamilton cycle
for every n>=1. This conjecture originated probably with Havel, Buck and Wiedemann,
but has also been attributed to Dejter, Erdőss, Trotter and various others,
and despite considerable efforts it resisted all attacks during the last 30 years.
In this talk I present a proof of the middle levels conjecture. In fact, I
show how to construct 2^{2^{\Omega(n)}} different Hamilton cycles in the middle
layer graph, which is best possible.
http://www.openproblemgarden.org/op/middle_levels_problem
http://www.math.uiuc.edu/~west/openp/revolving.html