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

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

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

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