Extremal Combinatorics V: POSETS

Posted on February 5, 2019 by Gil Kalai

This is the remaining post V on partially ordered sets of my series on extremal combinatorics (I,II,III,IV,VI). 

We will talk here about POSETS – partially ordered sets. The study of order is very important in many areas of mathematics starting with the order relation on the integers and reals in algebra and in Euclidean geometry. The set of all subsets of a set can be partially ordered by inclusion and this is a very basic example of posets. While the study of order and posets is a separate area on its own, parts of it are very important in extremal combinatorics and we will give a little taste here.

Dear readers, please contribute your favorite result or problem on partially ordered sets (or Sorting) in the comment session.

A chain C \subset P in a POSET is a set of elements so that every two of them are comparable. An antichain $A \subset P$ is a set of elements so that every two distinct elemenאs in A are incomparable.  (Antichains are also called independent sets.) An immediate but important Lemma is:

The immediate lemma: The intersection of a chain A and an antichain C contains at most one element. Walla!

Dilworth’s theorem

Dilworth’s theorem (DT): Every finite partially ordered P set can be covered by a(P) chains.

(By the immediate lemma, at least a(P) chains are needed.)

Dual Dilworth theorem: Every partially ordered sets can be covered by c(P) antichains.

(By the immediate lemma, at least c(P) antichains are needed.)

The proof of the dual Dilworth theorem is easy. Note that the set A_1=MIN(P) of minimal elements of P is an antichain. Let A_k = MIN (P\backslash (A_1 \cup A_2 \cup \dots A_{k-1})). We need two easy observations. First, A_k is an antichain and second: If A_k \ne \emptyset then there is a chain with one element from A_i: 1 \le i\le k. Walla!

The proof of Dilworth’s theorem is by induction on $|P|$. For the induction step you first consider the case where every antichain of maximal size is either MAX(P) or MIN (P). In this case you consider a chain with one element in MAX(P) and one element in MIN (P) and delete these elements from P. For the resulting post Q, a(Q)=a(P)-1 and we can use the induction hypothesis.

Otherwise there is an antichain A of maximum size t=a(P) which is not MAX(P) or MIN(P).  Put A=\{a_1,a_2,\dots,a_t\}. Let P^+ be the set of elements in P which are larger or equal some element in A, and let P^- be the set of elements in P which are smaller or equal some element in A.

Now,

  1. P^+ \cup P^-=P. Otherwise we could add an element to A to form a larger antichain.
  2. P^+ \cap P^- = A. Otherwise, there will be two elements of A which are comparable.

So by the induction hypothesis P^+ can be covered by t chains C_1^+, C_2^+, \dots, C_t^+ and P^- can be covered by a(P$ chains C_1^-, C_2^-, \dots, C_t^-. Bu re-indexing we can assume that both C_i^+ and C_i^- contains a_i. It follows that a_i is the minimal element in $C_i^+$ and the maximal element in $C_i^-$ and hence C_i=:C_i^+ \cup C_i^- is a chain. The t chains C_1, C_2, \dots, C_t cover P. Sababa!

An important Corollary both from Dilworth’s theorem and its dual is that

a(P) c(P) \ge |P|.

Erdos-Szekeres theorem

The fundamental Erdos Szekeres theorem asserts that if n=ab+1 then every sequence a_1,a_2,\dots ,a_n of different real numbers contains a monotone increasing sequence of length a+1 or a monotone decreasing sequence of length b+1.

There are simple proofs. For example, associate to every k a pair (I_k,D_k) of integers where  I_k is the maximum length of the increasing subsequence starting with a_k and D_k is the maximum length of the deccreasing subsequence starting with a_k. The result follows from the easy observation that all these pairs are different.

Both Dilworth’ theorem and its easy dual imply easily (in fact we need only the important corollary) the Erdos Szekeres theorem when we define the following partial order: i < k if both i<k and a_i < a_k.

Looking at Sperner’s theorem again

Sperner’s theorem asserts that the maximal size of an antichain of subsets of an n elements set is {{n} \choose {[n/2]}}. By Dilworth’s theorem it follows that we can cover all sets by {{n} \choose {[n/2]}} chains (and, of course when we exhibit such a covering it reproves Sperner’s theorem). A symmetric saturated chain decomposition is a partition of P(n) (=all subsets of [n]) to saturated chains where each chain has, for some k, sets of sizes $k,k+1,\dots,d-k$. You can build such a decomposition inductively.

Start with a decomposition for n for each chain C_i create a new chain C'_i by adding the element n+1 to every set. And then move the top set in C'_i to C_i.  Walla!

This is the beginning of a very beautiful story related also to the Dedekind Problem about  number of antichains in P(n).

Curtis Greene and Danny Kleitman

The Greene-Kleitman theorem

Let a_k(P) be the maximum size of the union X of k antichains in a poset P. For every chain For every chain C we have |C \cap X| \le \min\{|C|,k\}. Therefore for a partition of P to chains C_1,C_2,\dots,C_t we   have \sum\min\{|C_i|,k\ge |X|. The Greene-Kleitman theorem asserts that there is always  a decomposition into chains with \sum\min\{|C_i|,k\}=a_k(P).

The perfect graph theorem.

What is the relation between the very easy dual Dilworth theorem and the harder Dilworth theorem? As it turns out there is a very general theorem, Lovasz’ perfect graph theorem, that shows that these two theorems are equivalent.

A graph G is perfect if for every induced subgraph H, the chromatic number equals the clique number. Lovasz’ theorem  (conjectured by Claude Berge) asserts that complements of perfect graphs are perfect. The perfectness of the comparability graph of a poset amounts to the dual Dilworth theorem, and for its complement it is the Dilworth theorem. Lovasz in fact proved that perfectness is equivalent to the relation $\latex \omega(H)\cdot \alpha (H) \ge |H|$ for every induced subgraph H. (For posets this is our important corollary above.)

Jeff Kahn and Jake Baron (see here on their 2016 asymptotic solution to Tusza’s conjecture), Mike Saks, and Nati Linial

Startling theorems on POSETS: Kahn-Saks,  Linial-Saks, Linial-Kahn, and Kahn-Saks

Here  are some beautiful and important theorems on posets. An order ideas I of a post is a set of elements so that if x in I and y < x then y \in I.

Theorem (Linial-Saks, 1985): In every poset P there is an element which is contained in more than δ and less than 1-δ order ideas of P.  (Paper)

Theorem (Kahn-Saks, 1984): For every Poset P which is not a chain there are two incomparable elements x,y such that the number of linear extensions of P for which x<y is between 3/11 and 8/11. (Paper)

A simpler proof was found in the late 80s by Kahn and Linial and by Karzanov and Khachiyan. It  is  based on the Brunn Minkowski theorem and gives a weaker constant 1/2e .

Theorem (Kahn-Saks, 1987): For every finite distributive lattice L the maximum antichain is of size o(|L|). (Paper)

Lattices are special types of posets with the property that for every set of elements (pairs \{x,y\} suffice in the finite case), there is a unique minimal elements above them all (denoted for pairs by x ∧ y) and a unique maximal element (denoted for pairs by x ∨ y) below them all.

A distributive lattice is a lattice that satisfies for every x, y and z, the relation

x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)

Birkhoff’s representation theorem asserts that finite distributive lattices can be represented as order ideals of posets (ordered by inclusion).

 

 

This entry was posted in Combinatorics and tagged , , , , , , , , , . Bookmark the permalink.

6 Responses to Extremal Combinatorics V: POSETS

  1. dsp says:
    February 5, 2019 at 7:18 pm

    There are many beautiful problems and results to choose from, but right now my favorite is the following from Patricia Hersh, which combines posets with the Hirsch conjecture:

    Let P be a simple polytope and c a linear functional such that no edge of P is normal to c. Then the graph (1-skeleton) of P has a natural orientation, defined by letting an edge \{u,v\} point from u to v iff c(u) < c(v). Suppose that this oriented graph is the Hasse diagram of a lattice. Must it then be the case that no directed path which leaves a facet can re-enter that facet?

    Reply
  2. Joseph Malkevitch says:
    February 7, 2019 at 2:09 am

    Dear Gil,

    Thanks for this latest in a very nice series of posts.

    A favorite theorem of mine is the very basic version of the Gale/Shapely Theorem about matching men who have ranked women and women who have ranked men (or medical school graduates to be paired to hospitals looking to fill residencies). What one seeks are “stable” marriages.

    https://en.wikipedia.org/wiki/Stable_marriage_problem

    Donald Knuth credits John H. Conway with the observation that these stable marriages form a distributive lattice. One can generalize the rules (some women might rather not be paired than accept some men; ties in preferences, etc.) to situations where, suitably defined, there may not be any stable marriages, but, again, if there are stable marriages, they form a distributive lattice. There are many papers by David Manlove (U. of Glasgow) and Robert Irving about these issues, and a relatively recent book of Manlove surveys these these ideas.

    Regards,

    Joe

    Reply
  3. Gil Kalai says:
    February 7, 2019 at 8:31 am

    Dear Joe and dsp, many thanks –Gil

    Reply
    • dsp says:
      February 7, 2019 at 12:12 pm

      I’ve just read the mathoverflow thread and it seems to me that Frankl’s conjecture should count as a question about posets, since it can be equivalently stated purely in terms of lattices, without any reference to union-closed set families (“In any finite lattice, there is a join-irreducible element that is below at most half the elements of the lattice.”)

      Reply

  5. Pingback: Updates and plans III. | Combinatorics and more

Leave a comment