#
Monday Lecture and Colloquium

**Monday, June 3, 2013**

Freie Universität Berlin

Institut für Informatik

Takustr. 9

14195 Berlin

room 005

** Lecture - 14:15**

### Jean Cardinal -
Université Libre de Bruxelles

###
Covering Decomposition and Geometric Hypergraph Coloring

*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**

### Oliver Cooley -
TU Graz

### Finding Large Planar Subgraphs

*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.

Letzte Aktualisierung:
28.05.2013