Introduction to Order Theory, Wintersemester 2020/21

Introduction
to
Order Theorie

Wintersemester 2020/21
Prof. Stefan Felsner
Unter Beteiligung von Piotr Micek

LV-Nr.: 3236 L 253
Zoom lectures are on Wednesdays and Fridays at 12:15
A Zoom meeting on Tuesday 14:15 will serve as consulting hour and for the discussion of exercises.

This course is offered in the context of Berlin Mathematical School and will be tought in English.
This course is on-line only. The lectures are made available via youtube on the channel Order & Geometry.
Diese Vorlesung ist Teil des Studienschwerpunkts Diskrete Strukturen und kann als DSIII angerechnet werden.

Aktuell
Übung
Literatur

Aktuell:

Ich habe meine Aufzeichnungen zu einigen der Kapitel als pdf verlinkt.

Die Evaluation des Lehrbetriebs hat begonnen, jetzt vollelektronisch. Den Link zur Evaluation dieser VL gibt es [HIER].

Inhalt:

Ordnungstheorie Thema ist die Kombinatorik endlicher partieller Ordnungen. Der Schwerpunkt der Vorlesung liegt bei den kombinatorischen Beweistechniken und den zentralen Resultaten der Theorie. Ergänzend werden Anwendungen von Ordnungen in Informatik, Algebra und Topologie besprochen.

Order Theory A partial order (poset) is a set equipped with a transitive order relation. Posets are widely used models in applications and also within mathematics and computer science. In this course we cover the basics of combinatorial order theory but we also add some more advanced and recent topics. A good fraction of the material will deal with poset dimension, an important measure for the complexity of posets. Other chapters will deal with Boolean lattices, aspects of planarity and enumeration problems related to posets.

Fundamentals [pdf]

Lecture 01. (Nov. 04) Essential definitions and examples
Lecture 02. (Nov. 06) Chains and antichains
Lecture 03. (Nov. 11) Linear extensions and dimension

First Steps in Dimension Theory

Lecture 04. (Nov. 13) Alternating cycles (Lect 07 in the Order & Geometry channel [OGC])
Lecture 05. (Nov. 18) Dimension of the complete graph (Lect 13 in OGC)

Interval Orders

The introduction to this chapter starts at minute 51:45 of Lecture 05.
Lecture 06. (Nov. 20) Dimension of interval orders (Lect 14 in OGC)
Lecture 07. (Nov. 25) Forbidden subposets and dimension (Lect 15 in OGC)

Extremal Problems [pdf]

The introduction to this chapter starts at minute 73:55 of Lecture 07.
Lecture 08. (Nov. 27) Applications of Dilworth's Theorem to geometric problems (Lect 16 in OGC - overlength!)
Lecture 09. (Dec. 02) Dimension and the standard example number (Lect 17 in OGC - overlength!)
Lecture 10. (Dec. 04) Cover graphs: curves and colorings (Lect 18 in OGC)
Lecture 11. (Dec. 09) Coloring 2-dim cover graphs & Bipartite analog of Dilworth (Lect 19 in OGC)

Linear Extensions, Polytopes, and Counting [pdf]

Lecture 12. (Dec. 11) Poset polytopes (Lect 20 in OGC)
Lecture 13. (Dec. 16) Bounds and inequalities (Lect 21 in OGC)
Lecture 14. (Dec. 18) Random generation of linear extensions the Markov chain approach (Lect 22 in OGC)

Dimension and Sparcity

Lecture 15. (Jan. 06) Sparse classes of graphs and weak coloring numbers (Lect 23 in OGC)
Lecture 16+17. (Jan. 08+13) Nowhere dense classes of graphs (Lect 24+25 in OGC)
Lecture 18. (Jan. 15; guest lecturer: Gwenaël Joret) Dimension vs maximum degree (Lect 26 in OGC)

Greene-Kleitman Theory

Lecture 19. (Jan. 20) Frank's network flow approach (Lect 27 in OGC)
Lecture 20. (Jan. 22) Viennot's approach to Greene-Kleitman theory for 2 dimensional orders (Lect 28 in OGC)

On-line Problems for Posets

Lecture 21. (Jan. 27) On-line Chain and Antichain Partitions (Lect 29 in OGC)
Lecture 22. (Jan. 29) First-Fit on Interval Order and Beyond (Lect 30 in OGC)

Dimension and Planarity

Lecture 23. (Feb. 03) planar posets with 0 and 1 (Second part of Lect 08 in OGC)
Kelly's example and further classes with bounded dim (First part of Lecture 09 in OGC)

Dimension of Incidence Posets [pdf]
- Lecture 24. (Feb. 05) Dimension of graphs (Second part of Lect 09 in OGC)
- Lecture 25. (Feb. 10) Schnyder woods and applications (Lect 10 in OGC)
- Lecture 26. (Feb. 12) intro to the Lecture
  3-connected planar graphs and orthogonal surfaces (Lect 11 in OGC)
- Lecture 27. (Feb. 17) Dimension of planar maps (Lect 12 in OGC)
Boolean Lattices [pdf]
- Lecture 28. (Feb. 19) Symmetric chains (Lect 04 in OGC)
- Lecture 29. (Feb. 24) Shadows and intersecting families (Lect 05 in OGC)
- Lecture 30. (Feb. 26) More Kruskal-Katona and r-cross families (Lect 06 in OGC)

Zielgruppe:

Studentinnen und Studenten der Mathematik, Techno- und Wirtschaftsmathematik und der Informatik.
Diese Vorlesung ist Teil des Studienschwerpunkts Diskrete Strukturen.

Übungen:

Zeit: Tuesday at 14:15.
The copy-and-paste link for the zoom meeting is:
https://tu-berlin.zoom.us/j/66789611513?pwd=RmY1Mm5Vc2l1bWU4cDBxZlNONkQ3UT09

Übungsleitung:
Stefan Felsner

Zum Ende des Semesters wird es eine Modulabschlussprüfung geben.

Übungsblätter

sheet [pdf]
sheet [pdf]
sheet [pdf]
sheet [pdf]
sheet [pdf]
sheet [pdf]
sheet [pdf]
sheet [pdf]
sheet [pdf]
sheet [pdf]
sheet [pdf]
sheet [pdf]

Literatur:

Bücher

W.T. Trotter: Combinatorics of Partially Ordered sets, Dimension Theory.
B. Schröder: Ordered Sets, An Introduction.

Ergänzende Artikel

W.T. Trotter: Partially Ordered Sets; in Handbook of Combinatorics.

Die Seite der Vorlesung in Krakau ist Hier
Zuletzt bearbeitet: Januar 2021