Monday, June 25, 2007
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Math building - Room MA 041
Lecture - 14:15
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
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).