Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
|
locations | Term schedule | history
|
predoc-courses | schools | block-courses | workshops
partners


Monday Lecture and Colloquium


Monday, January 19, 2015

FU Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005



Lecture - 14:15

Martin Aigner - FU Berlin


Around the Borsuk Conjecture in 80 Years

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

Iyad Kanj - De Paul University, Chicago


On Bounded-Degree Plane Geometric Spanners

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.




Letzte Aktualisierung: 05.01.2015