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
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. Bounds and inequalities [Lecture 21]
      3. upper bound on e(P), 2nd proof, optimizing b, a corollary, Sidorenko's inequality, proof 1: pushing chains, proof 2: network flow, e(P) : some easy cases, Young tableaux: hook formula
    3. Random generation of linear extensions the Markov chain approach [Lecture 22] Markov chains, total variational distance, couplings, proof of the Coupling Lemma, linear extensions, the path coupling approach, the key proposition, specifying and using the p_i's, final remarks
  8. Sparsity and Dimension
    1. Introduction and sparse classes of Graphs [first part of Lecture 23]
      2. introduction, dim-boundedness, dim vs height: posets with a planar cover graph , dim vs height: posets with a planar diagram , lower bounds , sparse classes of graphs, depth-d minors, bounded expansion , hierarchy of sparse classes of graphs
    2. Weak coloring numbers [second part of Lecture 23]
      3. weak coloring numbers, characterization of bounded expansion in terms of wcols, dim vs height: bounded expansion, dim vs height and wcols, combining paths for wcols, proof of the thm, the signature
    3. Nowhere dense classes of graphs [Lectures 24 and 25]
      4. nowhere denseness, the theorem, proof of the easy direction, plan of the proof for the other direction, the main technical theorem, lemma involving wcols, proof of the lemma, where are we?, starting the proof of the theorem, first claim, proof of the first claim, second claim , proof of the second claim , finding y^* , going down from y^* to a good branching element, def of (V',R') , constructing a subdivision of K_t
    4. Dimension vs maximum degree of the comparability graph [Lecture 26]
      5. dimension vs boxicity, quadratic bound, coloring lemma, bipartite coloring lemma, representation lemma, proof of main theorem, permutation lemma
  9. Greene-Kleitmann Theory
    1. Statement of results, The orthogonal pairs, The network and the algorithm [Lecture 27]
      2. statement of results, orthogonal pairs, network flow - the network, the optimality criterion, the algorithm, lemma (a), from (f,pi) to orthogonal pairs, an example, the pair is orthogonal, wrap up
    2. Viennot's permutation skeletons [Lecture 28]
      3. Young tableaux, RS-correspondence and bumping, Viennot's construction of the pair (P,Q), the plan for the lecture, a lemma on jump lines, proof of (I) : the bijection, proof of (II) : maximum ell-antichains , proof of (III) : maximum k-chains
  10. On-line Algorithms for Posets
    1. On-line chain and antichain paritioning [Lecture 29]
      2. on-line game, on-line coloring is hopeless on forests , quick overview on on-line graph coloring , on-line antichain partition , on-line chain partition: lower bound , on-line chain partition: upper bound , up-growing variant, overview on variants of on-line chain partitions , on-line coloring of intervals , application to lower bound on chi-bounding function
    2. First-Fit coloring for interval graphs and beyond [Lecture 30]
      3. First-Fit coloring, quadratic bound , <8w-bound: column construction , claim: every interval is hit , the number of dollars , claim: the number of F's, finishing off, First-Fit on k+k-free orders, claim: (k+k)-free order as an extension of an interval order, claim: pseudo-monotonicity of First-Fit on subgraphs of interval graphs, on-line coloring of objects spanned between two lines
Content
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.