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 11, 2012

Technische Universität Berlin
Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041

Lecture - 14:15

Stefan Felsner - Technische Universität Berlin

Torus Squarings

A squaring is a tiling into squares of different sizes. In a seminal paper Brooks, Smith, Stone and Tutte (1940) discussed squarings related to segment contact representations of planar quadrangulations. Regarding the squares of a squaring as vertices and edges as being defined by contacts we obtain the square dual graph. Schramm (1993) showed that 5-connected inner triangulations of a 4-gon can be represented as square duals. In this talk we review the plane situation and present some results concerning squarings of the torus and the graphs represented by them. (joint work with E. Fusy)

Colloquium - 16:00

Julia Böttcher - London School of Economics

The tree packing conjecture of Gyarfas and Lehel

An old and surprising conjecture of Gyarfas and Lehel states the following. Let T_1,T_2,T_3,...,T_n be any family of trees such that T_i has i vertices for each i. Then these trees can be packed into the complete graph K_n on n vertices.
In the talk I will outline the history of this conjecture and explain some aspects of our recent approach (in joint work with Jan Hladky, Diana Piguet and Anusch Taraz) for an approximate version for families of bounded degree trees. Our proof uses a random embedding method and relies on properties of pseudo-random graphs, which I shall also illustrate.

Letzte Aktualisierung: 06.06.2012