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
partners


Monday Lecture and Colloquium


Monday, February 12, 2018

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005

Lecture - 14:15

Michaël Rao - ENS de Lyon


Exhaustive search of all convex pentagons which tile the plane

Abstract:
In 1918, Karl Reinhardt asked which convex polygon can tile the plane, and the pentagons was the only opened case. Fifteen types of such pentagons have been found between 1918 and 2015.
I present an exhaustive search of all families of convex pentagons which tile the plane. This proof is in two parts. First we show that if a pentagon tiles the plane, then it is in one of 371 families. Then a computer program tries, for each family, all possible tile arrangement, and shows that there are no more than the already known fifteen types. In particular, this implies that there is no convex polygon which allows only non-periodic tilings.



Colloquium - 16:00

Andrei Asinowski - TU Wien


Enumeration of triangulations of (some kinds of) subdivided convex polygons

Abstract:
We compute the number of triangulations of a convex k-gon with subdivided sides for the following cases: (1) all the sides are subdivided by the same number of points (r); (2) k=3. We find explicit formulas and generating functions, and we determine the asymptotic behaviour of these numbers as k and/or r tend to infinity. Finally, we link these results to a well-known open problem from computational geometry: finding a planar set of n points in general position that has the minimum possible number of triangulations.

joint work with C. Krattenthaler and T. Mansour




Letzte Aktualisierung: 26.01.2018