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
Abstract:
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
Abstract:
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.