This seminar builds on the knowledge and material studied within the Discrete Mathematics I course. This means students are expected to know basic objects and parameters from graph theory, e.g. chromatic number, clique, independent set and so on. For the partially ordered sets we only assume the knowledge of: chains, antichains, the width and the height of a poset. The only posetwise theorem we expect you to know beforehand is Dilworth's Theorem: any poset has a chain partition with the number of chains being equal to the poset's width.
We are going to explore the most important directions of recent (and not only) research in the combinatorics of posets. This includes: Ramsey properties, dimension of a poset (which is commonly compared with the chromatic number for graphs) and many extremal type questions.
The seminar's material will sometimes follow Tom Trotter's book Combinatorics of partially ordered sets: Dimension theory, but in most cases we will study original research papers.
The seminar will be run by
Arnimallee 3, Rm 205
A formal prerequisite is the successful completion of the Discrete Mathematics I course taught in the Summer 2016 semester, or the consent of the instructor (please contact if necessary).
This course can be used as a seminar in the Bachelor's curriculum of the Freie Universität Berlin.
The seminar will meet on Thursdays, 12:30 to 14:00, in Arnimallee 3, SR 119.
We will have a meeting on the 20th of October to assign topics and schedule the semester's talks.
|Nov 24||Michael Fritze||Schnyder Theorem:
Dimension of planar graphs [slides]
|T. Trotter: chapter in Handbook of Combinatorics, section 10;
W. Schnyder: Embedding Planar Graphs in the Grid
|Dec 1||Mara Nehring||Brightwell-Trotter Theorem:
Dimension of planar maps
|S. Felsner: The Order Dimension of Planar Posets Revisited;
Czyzowicz et al: some short proof
|Dec 8||Theresa Allner||Ramsey for Posets||H. Kierstead, T. Trotter: A ramsey-theoretic problem for finite ordered sets|
|Dec 15||Hannah Zabel||On-line chain partitions of posets|