Monday, January 19, 2015
FU Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
Borsuk´s conjecture from 1933 is a beautiful problem in geometry that was solved (or rather disproved) by a stunning combinatorial argument sixty years later. The solution, in turn, gave rise to a new and very intriguing problem that was recently attacked by completely different methods, which use graphs and groups in unexpected ways, and eventually lead back to geometry. I will tell you about the original problem, its many ramifications, the old and new ideas, ending with two new "Borsuk-like" conjectures.
Colloquium - 16:00
Abstract:
Let E be the complete Euclidean graph on a finite set of points embedded in the plane. Given a constant t >= 1, a spanning subgraph G
of E is a (geometric) t-spanner of E, or simply a spanner of E if, for any two vertices u, v in E, their distance in G is at most t times their
distance in E (i.e., |uv|). A spanner is plane if its edges do not cross.
Without the planarity constraint, it is known that a plane spanner of E of maximum degree 3 can be constructed. The constant 3 is the best-known
lower bound on the maximum degree of a plane spanner of E. In this talk we survey some results — in a long sequence of results — on bounded-degree
plane spanners of E, leading to the most recent result (2014) proving that a plane spanner of E of maximum degree 4 can be constructed (efficiently). The question
of whether there exists a plane spanner of E of maximum degree 3 remains open.