# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | preliminary term schedule | history
|

# 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

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

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