Monday, June 3, 2013
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
Given a k-fold covering of the plane by translates of a convex body,
in how many 1-fold coverings can we decompose it, as a function of k?
This problem was formulated in the early eighties and is far from
having a complete solution. We will survey recent results on this and
several related variants. In particular, we will discuss recent progress
on coloring problems involving bottomless rectangles,
three-dimensional octants, and triangles.
Colloquium - 16:00
Abstract:
Given a graph G, we consider the problem of finding a planar
subgraph H of G with many edges. Define the planarity pl(G) of G to be
max{e(H)} over all planar subgraphs H ? G. Given integers n and d, let
pl(n, d) be min{pl(G)} over all graphs G on n vertices with minimum degree
d.
In this talk we will examine the curious behaviour of pl(n, d) when d is
approximately n/2. Kühn, Osthus and Taraz showed that for ?(n) = d <= n/2
we have pl(n, d) = (2 + o(1))n. In this talk we will outline a proof that
pl(n, (n + 1)/2) = (2.25 + o(1))n for n odd and
pl(n, n/2 + 1) = (2.5 + o(1))n for n even.
Thus the asymptotic behaviour of the parameter pl(n, d)/n is to remain
constant at 2 for some time before exhibiting two discrete jumps at d = (n
+ 1)/2 and d = n/2 + 1.
This is based on joint work with Thomas Łuczak, Anusch Taraz and Andreas
Würfl.