Extra lecture notes : Day 15

The extra stuff today was a short introduction to posets.

Definition : Let S be any set. A relation ≤ on S is said to be a partial ordering if

(i) ≤ is reflexive, i.e.: a ≤ a ∀ a ∈ S,

(ii) ≤ is anti-symmetric, i.e.: if a ≤ b and b ≤ a then a = b,

(iii) ≤ is transitive, i.e.: if a ≤ b and b ≤ c then a ≤ c.

Definition : A set S together with a partial ordering ≤ on it is called a poset. Notation : (S, ≤).

Definition : Two elements a, b of a poset (S, ≤) are said to be comparable if either a ≤ b or b ≤ a.

A subset T of S is said to be totally ordered by ≤ if every pair of elements from T are comparable.

A totally ordered subset of a poset is called a chain.

A subset T ≤ S such that no pair of elements from T are comparable is called an antichain.

Example 0 : The ordinary ≤ relation on any subset of the real numbers is a total ordering. On the other hand, there is no ‘natural’ total ordering of the complex numbers.

Example 1 : Let X be any set and take S = 2^{X}, the collection of subsets of X. Define the relation ≤ on S by

A ≤ B if A ⊆ B.

Then (S, ≤) is a poset. It is called the Boolean algebra on the set X.

Example 2 : Let S be the set of positive integers. Define the relation ≤ by

n_{1} ≤ n_{2} if n_{1} | n_{2}.

If we let X be a set which contains infinitely many copies of each prime number, then the Fundamental Theorem of Arithmetic implies that (S, ≤) can be identified with that part of the Boolean algebra on X consisting of the finite subsets of X.

As preparation for the next result, note that if X = {1, ..., n}, then for any k with 0 ≤ k ≤ n, the subsets of X of size k form an antichain in 2^{X} of

size ( \begin{matrix}n \\ k \end{matrix} ).

Definition : Let f : Z → R be a sequence of real numbers. The sequence is said to be unimodal if there exists an integer k_{0} such that

(i) f(k_{0}) is a maximum for f,

(ii) f(k) is an increasing function of k for k ≤ k_{0}, (iii) f(k) is a decreasing function of k for k ≥ k_{0}.

Proposition Let n be a fixed positive integer, and consider the sequence f(k) given by

f(k) := \{ \begin{matrix}( \begin{matrix}n \\ k \end{matrix} ) , & if 0 ≤ k ≤ n, \\ 0, & otherwise. \end{matrix}

Then f(k) is unimodal with a maximum at k = ⌊n/2⌋.

Proof : Using the formula for the binomial coefficients we have that, for k < n,

( \begin{matrix}n \\ k + 1 \end{matrix} ) = \frac{n − k}{k + 1} ( \begin{matrix}n \\ k \end{matrix} ) .

Hence f(k + 1) ≥ f(k) if and only if n − k ≥ k + 1 ⇔ k ≤ (n − 1)/2 ⇔ k < ⌊n/2⌋, v.s.v.

Theorem (Sperner 1929) Let n be a positive integer and X = {1, ..., n}.

The largest size of an antichain in 2^{X} is ( \begin{matrix}n \\ ⌊n/2⌋ \end{matrix} ).

Proof : Not given. See [1], Chapter 6.

Theorem (Dilworth) Let (S, ≤) be any finite poset (i.e.: the set S is finite). Then the maximum size of an antichain in S equals the minimum number of pairwise disjoint chains needed to cover all the elements of S.

Proof : Not given. See [1], Chapter 6.

Corollary (Erdös) Let n be a positive integer. Then in any reordering of the integers 1, 2, ..., n^{2} + 1, there exists either an increasing or a decreasing subsequence of length n + 1.

Proof : Let S = {1, 2, ..., n^{2} + 1} and let π be any permutation of S. Define a relation ≤_{π} on S by

i ≤_{π} j if i ≤ j and π(i) ≤ π(j).

One easily checks that (i) ≤_{π} is a partial ordering on S, (ii) a chain in (S, ≤_{π}) corresponds to an increasing subsequence in the

reordering π,

(iii) an antichain in (S, ≤_{π}) corresponds to a decreasing subsequence in the reordering π.

By (iii), if there exists no decreasing subsequence of length n + 1, then there exists no antichain of size n + 1 in (S, ≤_{π}). By Dilworth’s Theorem, this implies that S can be covered by at most n pairwise disjoint chains. But S has n^{2} + 1 elements, so at least one of these chains must have size greater than n. By (ii), this would imply that the reordering π contained an increasing subsequence of length n + 1.

Reference

[1] J.H. van Lint and R.M. Wilson, A Course in Combinatorics, Cambridge University Press, 1992.