Introduction to order theory
winter 2020/21
Instytut Informatyki Analitycznej
Wydział Matematyki i Informatyki
Uniwersytet Jagielloński
Lecturers
Stefan Felsner and Piotr Micek
Classes
lectures Wed 12:15 - 13:45
  Fri 12:15 - 13:45
exercise session Fri 14:30 - 16:00
everything streamed on Zoom; please contact us for access.
YouTube channel with recordings
Content
About

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.

Below we have a table of contents with links to respective recordings.
  1. Fundamentals
    1. Fundamental examples [Lecture 01]
      poset, related graphs and diagram, linear orders, Boolean lattices and inclusion orders, down-set lattices, subposets and lattices, interval orders, products of orders, combinatorial orders
    2. Chains and antichains [Lecture 02]
      chains and antichains, antichains and downsets, height and width, Sperner's Theorem (LYM proof), height and width for compositions of orders, around Dilworth's Theorem, dual of Dilworth, Dilworth's Theorem, comparability graphs are perfect, Dilworth and bipartite matching
    3. Linear extensions and dimension [Lecture 03]
      linear extensions, the generic algorithm, scheduling with precedence constraints, poset antimatroid, dimension, dimension of Boolean lattices, standard examples, dimension and width, 2-dimensional posets
  2. Boolean Lattices
    1. Symmetric chains [Lecture 04]
      definitions, symmetric chain decomposition of products of chains, corollaries, symmetric chains and paranthesis, Dedekind numbers - counting antichains, a probability theory application, the bound is tight: example , orthogonal chain partitions for the Boolean lattice
    2. Shadows and intersecting families [Lecture 05] and [Lecture 06]
      shadows, Sperner's Thm. via shadows, intersecting families, Erdös-Ko-Rado Theorem, colex order on sets, k-cascade number representations, Kruskal-Katona Theorem, shifting, Where are we?, Proof of L-KK theorem - part 2, L-KK implies EKR, r-cross union families
    3. Enumerating sets and binary vectors [just a stub at the end of Lecture 06]
  3. First Steps in Dimension Theory
    1. Alternating cycles [first part of Lecture 07]
      reversible sets, alternating cycles, poset on connected induced subgraphs of a graph, dimension vs chromatic number
    2. Families of posets with unbounded dimension [second part of Lecture 07] and [first part of Lecture 08]
      dimension of incidence posets, dimension of interval orders, adjacency posets, critical pairs, generalized crowns, 2-cycles vs all cycles
    3. Dimension and planarity [second part of Lecture 08] and [first part of Lecture 09]
      planar posets with 0 and 1, Kelly's example, planar posets with 0, posets with a cover graph being a forest, posets with outerplanar cover graphs
  4. Dimension of Incidence Posets
    1. Introduction [second part of Lecture 09]
      dimension of graphs, incidence posets of dimension at most 3
    2. Schnyder woods and applications [Lecture 10]
      planar graphs and triangulations, Schnyder woods, dimension of planar graphs, adding the faces, planar drawings, triangle contact representations
    3. 3-connected planar graphs and orthogonal surfaces [intro to Lecture 11] and [Lecture 11]
      Schnyder woods for 3-connected graphs, drawings on small grids, towards a bound for dimension, orthogonal surfaces, geodesic embeddings, Schnyder woods and orthogonal surfaces, rigid surfaces, proof of the strong dimension theorem
    4. Dimension of planar maps [Lecture 12]
      dimension of polytopes, dimension of planar maps, splits and dimension, dimension of GIGs, segment contact representations, separating decompositions, separating dec. and segment contacts, dimension of 2-connected maps, dealing with degeneracies
    5. Incidence orders of complete graphs [first part of Lecture 13]
      the theorem, lower bound, upper bound, levels of the Boolean lattice, lower bound for dim(1,k;n) with k large,
  5. Interval Orders
    1. Characterizations and semi-orders [second part of Lecture 13] and [first part of Lecture 14]
      characterizations of interval orders, semi-orders characterizations of semi-orders, counting semi-orders
    2. Doubly logarithmic upper bound for dimension [second part of Lecture 14]
      marking functions, dimension of semi-orders, doubly logarithmic bound on dimension of interval orders, dimension of universal interval orders
    3. Forbidden subposets and dimension [first part of Lecture 15]
      theorem: interval orders with large dimension are universal, overlap graphs, dim^*, thickets, main technical theorem, the proof
  6. Extremal Problems and Applications to Discrete Geometry
    1. Applications of Dilworth theorem to problems in geometry [second part of Lecture 15] and [Lecture 16]
      introduction intersection graphs of rectangles , disjointness graphs of segments, extremal problems for geometric graphs, geometric graphs with no k+1 disjoint edges, disjointness graphs of rectangles, strong hitting sets for rectangles: 1. The k^7 factor, 2. A class and its intervals, 3. Hitting sets for c-intervals, 4. t-independence, 5. Transversal lemma, 6. A recursion for beta
    2. Forcing standard examples [Lecture 17]
      chi vs omega, dim vs sn, the split of a poset, sn does not grow when we split the poset, lemma on a matrix distinguishing all t-tuples of columns, proving the upper bound, claim that phi-monochromatic subsets help to reverse incomparable pairs, wrapping up the proof the upper bound, the lower bound, the proof of the lower bound, three claims, proof of Claim 1, proof of Claim 2, proof of Claim 3, wrapping up the proof of the lower bound
    3. Cover graphs: curves and coloring [Lecture 18] and [first part of Lecture 19]
      curves spanned in a strip, cover graphs and curves spanned in a cylinder, digression: push-down, the auxiliary poset Q, extending the curves, Chromatic number of cover graphs, points lines and a cover graph, bounding alpha, many incidences, wrap up, special classes of posets cover graphs of 2-dimensional orders: the instance, stages + forcing, the probability of being independent, the choice of m, the independence number, the choice of L, wrap up
    4. Bipartite analogue of Dilworth [second part of Lecture 19]
      the statement, the proof, claim, the statement is tight
  7. Linear Extensions, Polytopes and Counting
    1. Poset polytopes [Lecture 20]
      the order polytope, the volume formula, the chain polytope, Stanley's Theorem, convex corners and antiblockers, the antichain polytope
    2. Sidorenko's inequality
    3. Markov chains
  8. Dimension and Sparse Cover Graphs
    1. Dimension and weak coloring numbers
    2. Nowhere dense classes of graphs
    3. Scott-Wood proof for bounded degree posets
  9. Greene-Kleitmann Theory
    1. Duality for l-antichains and k-chains
    2. Young Tableaux and RSK correspondence, Viennot's skeletons of 2-d orders
  10. On-line Algorithms for Posets
    1. On-line chain and antichain paritioning
    2. First-Fit coloring for interval graphs and beyond
Warunki zaliczenia

Zaliczenie z ćwiczeń będzie wystawiane na podstawie rozwiązań zadań domowych. W trakcie kursu będą publikowane zestawy zadań domowych. Liczba zestawów będzie równa $Z$. Zestawy będą ukazywać się (zazwyczaj) co tydzień. Rozwiązania zadań studenci przekazują w formie pisemnej (emailem) prowadzącym w wyznaczonych terminach (najczęściej na dzień przed kolejną sesją ćwiczeń). Za rozwiązanie zadań pojedynczego zestawu będzie można uzyskać co najwyżej $\frac{100}{Z}$ punktów. Zadania w pojedynczym zestawie będą miały zróżnicowany poziom trudności i zazwyczaj będą tak samo punktowane. Studenci mogą rozwiązywać zadania samodzielnie lub w grupach dwuosobowych. Każda dwójka studentów może rozwiązywać wspólnie co najwyżej dwa zestawy.

Kodeks honorowy. Studenci nie mogą wyszukiwać, rozwiązań czy wskazówek do zadań domowych w internecie, książkach, pracach naukowych, czy też dyskutować zadania z osobami trzecimi. W sytuacjach wątpliwych najlepiej spytać. Każde rozwiązanie powinno zawierać oświadczenie o samodzielności wykonania (indywidualnie lub w grupie).

Ćwiczenia. W ramach ćwiczeń będziemy wspólnie rozwiązywać zadania. Zestawy zadań na ćwiczenia będą publikowane z niewielkim wyprzedzeniem lub rozdawane podczas zajęć. Studenci nie będą ewaluowani za pracę podczas ćwiczeń, a więc w ramach ćwiczeń nie będą przyznawane punkty.

Oceny z ćwiczeń wystawiane będą względem następujących progów:

Studenci, którzy otrzymają ocenę co najmniej 3,0 z ćwiczeń przystąpią do egzaminu końcowego w pierwszym terminie w formie ustnej. Studenci, którzy otrzymają ocenę co najmniej 3,0 z egzaminu w pierwszym terminie otrzymają ocenę końcową z kursu równą średniej arytmetycznej ocen z ćwiczeń i egzaminu. Studenci, którzy otrzymali ocenę 2,0 lub NZAL z egzaminu w pierwszym terminie mogą przystąpić do egzaminu w drugim terminie w sesji poprawkowej. Studenci, którzy otrzymali ocenę 2,0 lub NZAL z ćwiczeń nie zaliczą kursu.