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

The Upcoming Monday Lecture and Colloquium

Monday, June 25, 2007

Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Math building - Room MA 041

Lecture - 14:15

Stefan Felsner - TU Berlin

Combinatorial Structures on Plane Quadrangulations and Triangulations

Schnyder woods of plane triangulations are in bijection to certain angle labelings, 3-orientations and pairs of non-crossing Dyck path (the last of these incarnations was topic of O.Bernardi's talk two weeks ago). This polymorphism seems to be the root of the applicability of Schnyder structures to problems in different areas.
Recently we have learned that on quadrangulations there is a similarly diverse family of structures. This family again involves partitions into trees, angle labelings and 2-orientations. There are also bijections to Baxter permutations, triples of non-crossing lattice path and rectangular dissections. Our guided tour will involve many bijections, and some counting results.

Colloquium - 16:00

Piotr Micek - Jagiellonian University, Krakow

On-line chain partitioning of up-growing interval orders and semi-orders

The value of the on-line chain partitioning of orders problem is between {w+1\choose 2} and frac{5^{w}-1}{4} for width w orders (bounds by Szemeredi and Kierstead). This is already a complicated result, and no progress has been made on this problem for the last 20 years. The case of interval orders is solved: 3w-2 (Kierstead and Trotter). The case of semi-orders is relatively easy: 2w-1. On the other hand Felsner proved that if incoming points are maximal in already presented order (so called up-growing version) then the value of the problem for general orders is {w+1\choose 2}. We study on-line chain partitioning of up-growing interval orders and semi-orders. The values are respectively: 2w-1 and \lfloor\frac{1+\sqrt{5}}{2}w\rfloor (suprisingly the golden ratio comes into the play for semi-orders).