#
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

*Abstract:*

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

*Abstract:*

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).