MATH 206A: Combinatorics - Course Review

This is a review and summary for course MATH 206A Combinatorics at UCLA, given by Prof. Igor Pak.

I try to make the flow more naturally, but also want to include brief description of important theorems.

Overview

The topics of 206A and 206B changes every year. This year, the professor decides to focus on poset, a set associated with a (strict) partial order $<$. The lectures become a slice that goes across every subfield of combinatorics. We use tools from algebra, graph theory, analysis, geometry, probabilistic method, etc.

Chains & Antichains

The property of a set is highly related to the properties of its subsets. Therefore, when a set is associatesd with an order, the first thing we want to ask is what properties its subsets may have. A random subset is boring, because when we restrict the order to it we always get another poset. However, there are two special kinds of subsets — one that every two elements can be compared; one that every two elements cannot. They are called chains and antichains, resp.

Dilworth's theorem

The story starts with the basic properties, height and width, of a poset $P$. Height is the maximum length of (maximal) chains $h(P) = \max |\{c_1< c_2< \ldots < c_h\}|$; width is the maximum size of (maximal) antichains $w(P) = \max |\{a_1, \ldots, a_w: a_i,a_j\text{ incomparible} \}|$.

Dilworth's theorem states that

• Height = size of smallest antichain partition
• Weight = size of smallest chain partition

The first case is simple: we can define the height of an element $x\in P$ to be the height of its principal ideal $\{ y\in P: y< x \}$, or equivalently, the longest path towards it. Then, the elements with the same height forms an antichain.

The second case is not so simple. There does not exists an obvious dual poset, so the width of an element is undefined. To prove it, we can pick a maximal antichain, and induct on the two subposets separated by this antichain.

Dilworth's theorem has several corollaries. One interesting result is Hall't marriage theorem: Given $n$ men and $n$ women, if any $k$ women has more than $k$ acceptable partners, then there exists an arrangement that everyone can be married; because the width of this graph is less than $n$.

Dilworth's theorem can be considered as a special case of more general theorems. One by Gallai states that every directed graph has a path partition of vertices, whose size is less than the number of independent sets.

Boolean lattice

An important kind of posets is (finite) boolean lattices: $B_n = (2^{[n ]}, \subsetneqq)$, where $[n ] = \{0,1,\ldots, n-1\}$. We tried to count the number of chains and antichains using enumerative method. For chain, the generating function is the same as the number of surjections. Greene-Kleitman shows that $B_n$ can be partitioned into $w(B_n)$ symmetric saturated chains. As a corollary, the width of each level is unimodal: ${n\choose 0} \leq \cdots \leq {n\choose n/2} \geq \cdots \geq {n\choose n}$. G-K gives a bracket-sequence representation of these chains.

Two properties $B_n$ satisfies are Bollobás's Two Families Theorem, LYM inequality, and Sperner property.

LYM inequality

Let $A\subset B_n$ be an antichain, then

$$\sum_{a\in A} {n\choose |a|}^{-1} \leq 1$$

In other words, the sum of probabilities, that each set is chosen out of the rank it lies in, is less than 1.

This can be proven by double counting the number of maximal chains: For each $a\in A$, there are $|a|!(n- |a|)!$ maximal chains passing it; each chain cannot pass two elements in an antichain, so the sum of this thing is less than $n!$.

Sperner property

Sperner property argues that the largest antichain is the largest rank. This is a corollary of LYM: suppose $A$ is the largest antichain, then

$$1 \geq \sum_{a\in A}{n\choose |a|}^{-1} \geq \mathrm{width}(B_n){n\choose n/2}^{-1}$$

Bollobás's theorem

Suppose $A_1,\ldots, A_m,B_1,\ldots, B_m \subseteq [n ]$ s.t. $A_i\cap B_j = \varnothing$ iff $i=j$. Then.

$$\sum_{i= 1}^{m} {|A_i|+|B_i| \choose |A_i|}^{-1} \leq 1$$

LYM inequality is a corollary of Bollobás's theorem.

Applications of chains & antichains

As applications, we learnt Gray codes and universal sequences. The latter one contains every subset of $[ n]$ as continuous subsequences.

Linear Algebra Methods

Perfect graphs

A perfect graph is a simple graph in which the chromatic number of every induced subgraph equals its the clique number.

• Comparability graphs and incomparability graphs are always perfect.
• Weak perfect graph conjecture: a graph is perfect iff its complement graph is perfect.
• Strong perfect graph conjecture: a graph is perfect iff neither it nor its complement graph contains any $(2n+1)$-cycle as an induced subgraph, for all $n\geq 2$.
• Replication lemma: If both $G$ and $H$ are perfect, then the result of replacing a vertex in $G$ with $H$ is perfect.
• A graph is perfect iff the size of every induced subgraph is $\leq$ its clique number times independent number.

To prove the last lemma, we use some argument on matrix rank.

Equal subset sums

Given a set $S$ of $n$ different positive real numbers, we want to count how many subsets of $S$ whose elements sum up to a given $K$. We proved that:

• The number is $\leq {n\choose n/2}$
• (Erdős-Moser Conjecture) The number is not larger than the case where $S = \{1,2,\ldots, n\}$ and $K = \frac{n(n+1)}{4}$ equals half the sum of $S$.

The proof idea is: let

$$M_n = \{(b_1,\ldots, b_n) : 0\leq b_i\leq n \wedge 0 = b_1 = \cdots = b_l < b_{l+1} < \cdots < b_n \}$$

and $\leq$ on $M_n$ defined by pointwise $\leq$. Then, $M_n$ does not have symmetric saturated chain decomposition.

However, after embedding $M_n$ into a linear spaces, we can still prove that $M_n$ is unimodular and has Sperner property. The conjecture is equivalent to Sperner property, so it holds. The operations in $M_n$ is somehow related to the representation of Lie group $\mathrm{SL}_2$.

Combinatoric Optimization

Dilworth gives one longest chain / antichain, so now we want to generalize it to the largest union set of $k$ chains / antichains. This is the Greene-Kleitman theorem:

• The largest $k$ chain union, $\alpha_k$, equals to the minimum $\sum_{A\in\mathcal{A}}\min\{k, |A|\}$, where $\mathcal{A}$ is an antichain cover.
  • $\min\{k, \|A\|\}$ is because every antichain can contribute at most $k$ elements to the $k$ chain union.
• Dual is the largest $k$ antichain union $\beta_k$.
• For any poset, $\alpha_k$ and $\beta_k$ are the sum of lengths of rows and columns of one specific standard Young diagram.
  • That is, let $a_k = \alpha_k - \alpha_{k-1}$, $b_k = \beta_k - \beta_{k-1}$. Then, there exists some $\lambda\vdash n$ s.t. the $k$-row is $a_k$, the $k$-column is $b_k$.

This is proven by transform the poset into a min-cost circulation problem, which is itself a linear programming and has some well-researched properties.

On the other hand, RSK correspondence also gives a bijection between an $n$-permutation and a pair of $n$ standard Yound tableaux. The Young tableaux given by RSK also gives $a_k$ and $b_k$.

Poset Arithmetic & Lattice

Poset operations

We can define several arithmetic operations on poset:

• Sum: $P+Q$ contains all elements of $P$,$Q$. Any $p\in P$ and $q\in Q$ are incomparable.
• Product (noncommutative): $P\cdot Q$ contains $P$, $Q$. $p > q$ for all $p\in P$, $q\in Q$.
  • A poset obtained from single-points via sum and product is series-parallel. A poset is series-parallel iff it does not contain $N = \{a< c, a < d, b < d\}$ as an induced subposet.
• Cartesian product: $P\times Q$ contains every pair $(p, q)$, with pointwise order: $(p_1,q_1)\leq (p_2,q_2)$ iff $p_1\leq q_1 \wedge p_2 \leq q_2$.
  • Boolean lattice $B_n$ is the cartesian product of $n$ $B_1$.
• Power poset: $Q^P$ contains all functions $f:P\to Q$ that preserve the order. The order of functions $f\leq g$ is defined pointwise.
  • $P\times (Q+R) = P\times Q + P\times R$; $P^{Q+R} = P^Q\times P^R$
• For a poset $P$, let $J(P)$ be the poset of lower sets of $P$, with order $\subset$.
  • $J(P)$ is a distributive lattice with $\wedge = \cap$, $\vee = \cup$.

Distributive lattice

A lattice is a poset $L = (X, <)$, closed under operations meet $\wedge$ and join $\vee$:

• Meet $a\wedge b$ is the greatest (universal) lower bound, infimum.
• Join $a\vee b$ is the least (universal) upper bound, supremum.

Lattice satisfies many propositions as basic logic $B_1 = \{ True, False \}$:

• A finite lattice always has one greatest element (top) $\top$ or $1$, and one least element (bottom) $\bot$ or $0$.
  • $a\vee 0 = a \wedge 1 = a$.
• Meet and join are associative, commutative, and satisfies absorption laws: $a\wedge(a\vee b) = a\vee(a\wedge b) = a$
• Idempotent laws: $a\wedge a = a\vee a = a$.

A filter on a poset is a non-empty upper sets that does not contain $\bot$ and is closed under finitely many meets $\wedge$. Dually, $ideal$. A maximal filter is called a ultrafilter. A ultrafilter of the form $F_y = \{ x\in L: x \leq y \}$ is principal.

A lattice is distributive if meet is distributive over join and vice versa.

Fundamental theorem of finite distr. lat.: Every finite distributive lattice $L$ is isomorphic to some $J(P)$.

• An element is join-irreducible if it is not the join of two other elements.
• Every element has a unique factorization as a join of a set of join-irreducible elements.
• Let $P$ be the subposet containing all join-irreducible elements, then $L=J(P)$.

The Stone representation theorem: If a (possibly infinite) distributive lattice has well-defined $\top$, $\bot$ and $\neg$ ($a\vee\neg a = \top$, $a\wedge\neg a = \bot$), then it is isomorphic to a field of sets.

• Let $S$ be the set of ultrafilters of $L$.
• Let $f: L\to 2^S$ be defined as $f(x) = \{U\in S: x\in U\}$.
  • $f$ is not necessarily be surjective if $L$ is infinite.

A lattice is distributive iff it admits cancallation: for all $x,y,z$, if $z\wedge x = z\wedge y$ and $z\vee x = z\vee y$, then $z = y$.

A lattice is distributive iff it does not contain induced sublattice isomorphic to diamond $M_3$ or pentagon $N_5$.

Linear Extensions

The set of linear extensions of a poset $P$ is the set of maps $P\to [ n]$ that preserves the order, denoted by $\alpha(P)$ Let $e(P) = \|\alpha(P)\|$ denote the number of linear extensions of $P$.

• $e(P\cdot Q) = e(P)e(Q)$; $e(P+Q) = e(P)e(Q){\|P\| + \|Q\|\choose \|P\|}$
• $e(P)$ of a tree is $\|P\|!$ divided by the product of sizes of all subtrees.
• $e(P)$ of a $2\times m$-square is the Catalan number $C_m$.
• The hook length formula computes $e(P)$ for standard Young diagrams.
• $e(P_{\sigma})$ is the number of permutations less than or equal to $\sigma$ under Bruhat order.
  • The weak Bruhat order gives a partial order on permutations.

Estimations of linear extensions

Computing $e(P)$ is generally ♯P-complete. However, we can estimate it.

• $e(P) \geq \|A_1\|!\cdots\|A_n\|!$ for any antichain partition $\{A_1,\ldots, A_n\}$.
• $n!/e(P) \geq \|C_1\|!\cdots\|C_n\|!$ for any chain partition $\{C_1,\ldots, C_n\}$.
• $e(P) \leq \mathrm{width}(P)^n$.

Operations on linear extensions

• Jeu-de-taquin acts on skew Young tableau.
• Schützenberger Promotion
  • $\psi$:
    • Starting from $1$, replacing every element with its least child; go down the path till the maximal element.
    • Remove the maximal element; shift every element by $1$ and fill in the blank by $n$.
  • $\psi$ is a bijection on linear extensions.
• Evacuation:
  • $\eta$: similar to promotion
  • $\eta$ is also a bijection. $\eta^2 = 1$.
• Coxeter group:
  • The infinite group generated by $\langle\tau_1, \ldots, \tau_{n-1}\rangle$.
    • $\tau_i$ means swap $i$ and $i+1$ if possible in $P$.
    • $\tau_i^2 = (\tau_i\tau_j)^2 = 1$, for non-adjacent $i,j$.
  • $\psi$ and $\eta$ can be expressed in Coxeter group.

Domino tableaux

• There is a bijection between domino diagrams and a pair of standard Young diagrams: $\phi(\lambda) = (\mu, \nu)$.
• The number of domino tableaux in shape $\lambda$ is ${\|\mu\|+\|\nu\|\choose \|\mu\|}\#SYT(\mu)\#SYT(\nu)$.

We also proved the Hook length formula by poset sorting and $P$-partition theory.

Poset Polytopes

Poset polytopes are the application of geometry methods on posets. For each post $P$, we can define two kinds of polytopes: the order polytope and the chain polytope.

Order polytope

• The order polytope $\mathcal{O}_p$ contains real functions $f: P\to [0, 1]$ that preserves the order.
• Facets of $\mathcal{O}_p$ are $f(x) = 0$ for $x$ minimal; $f(y) = 1$ for $y$ maximal; $f(x)=f(y)$ for $x$ covers $y$ in the Hasse diagram.
• Vertices of $\mathcal{O}_p$ are characteristic functions of upper sets.
• Its volume is $e(P)/n!$.

Chain polytope

• The chain polytope $\mathcal{C}_p$ contains real functions $f: P\to [0, 1]$ that the sum of any chain is $\leq 1$.
• Vertices of $\mathcal{C}_p$ are characteristic functions of antichains.
• Its volume is also $e(P)/n!$.
  • Proven by build a continuous, pointwise linear, volume preserving bijection between $\mathcal{O}_p$ and $\mathcal{C}_p$.
  • Corollary: $e(P)$ depends only on the comparability graph.

Ehrhart polynomial

Given an $n$-d integral polytope $Q$ and $N\in\mathbb{N}$, then the integral points contained by $NQ$ is $L(Q,N) = \|NQ\cap \mathbb{Z}^n\|$ is a polynomial of $N$ of degree $n$, and the leading coefficient is the volume of $Q$.

Let $a_P(m)$ be order preserving functions from $P$ to $[m ]$. Then, $a_P(m)$ is a polynomial of $m$, with its leading coeff = $e(P)/(m-1)!$.

Aleksandrov-Fenchel inequality

Suppose $Q_0$, $Q_1$ are convex polytopes in $\mathbb{R}^n$. Let $Q = conv\{Q_0, Q_1\}$ be the polytope that continuously vary from $Q_0$ to $Q_1$. Then, the volume of $Q_{\lambda}$ is

$$\mathrm{vol}_{n-1}(Q_{\lambda}) = \sum_{i=0}^{n-1}{n-1 \choose i}V_i(Q_0, Q_1)\lambda^i(1-\lambda)^{n-1-i}$$

Where $V_i^2(Q_0, Q_1) \geq V_{i-1}(Q_0, Q_1)V_{i+1}(Q_0, Q_1)$.

Given a poset $P$, let $\alpha_j(x)$ denote the number of linear extensions that maps $x$ to $j$. Then, $\alpha_j(x)^2\geq \alpha_{j-1}(x)\alpha_{j+1}(x)$ is log concave. Log concavity implies unimodularity.

Let $\beta_i(x,y)$ denote number of linear extensions where the images of $x$ and $y$ differs by $i$. Then, $\beta_i(x)$ is also unimodular.

If $a_i/{n\choose i}$ is log concave, then $a_i$ is ultra log concave. The convolution $c_i = \sum_k{n\choose k}a_k b_{i-k}$ of two ultra log concave sequences is ultra log concave. Thus, for a series parallel poset $P$, $a_i$ is ultra log concave.

Brightwell-Tetali theorem

Suppose $h: P\to \mathbb\{R\}\_\{+\}$ s.t. the sum over any antichain is less than $1$. Then, $e(P)\leq \prod_{x\in P} 1/h(x)$.

As a corollary, for all ranked $P$ with LYM property, $e(P) \leq \prod_{k=1}^{h(P)} (r_k)^{r_k}$

Correlation Results

Pick $x,y,z\in P$ pairwise incomparable and a linear extension $\sigma$. Then, if $\sigma(x) < \sigma(z)$, then $\sigma(y) < \sigma(z)$ will be generally higher. Because these two events are positive correlated. There are exceptions like trees and series parallel posets, where these events are independent.

Generate a random graph $G$. Then, $G$ being planar and being Hamiltonian are negative correlated. Intuitively, planarity is downward closed but Hamiltonianity is upward closed. These two examples inspire us correlations widely exist in posets.

Four functions theorem

Kleitman

Let $L,U\subseteq B_n$ s.t. $L$ is lower set and $U$ is upper set. Then, $\|L\cap U\|\cdot\|B_n\|\leq \|L\|\cdot\|U\|$.

Four functions theorem

Suppose $\alpha,\beta,\gamma,\delta$ are four functions from $2^{[ n]}$ to $\mathbb{R}_+$ s.t. $\forall A,B\in 2^{[ n]}$,

$$\alpha(A)\beta(B) \leq \gamma(A\cup B)\delta(A\cap B)$$

Then for all set family $\mathcal{A}, \mathcal{B}\subset 2^{[ n]}$,

$$\alpha(\mathcal{A})\beta(\mathcal{B}) \leq \gamma(\underline{\mathcal{A}\cup \mathcal{B}})\delta(\underline{\mathcal{A}\cap \mathcal{B}})$$

where the underlined intersection and union means pairwise intersection and union.

This can be extended to any finite distributive lattice. For example,

$$|A|\cdot |B| \leq |A\wedge B|\cdot |A\vee B|$$

FKG inequality

Let $L$ be a distributive lattice. A nonnegative function $\mu$ is log supermodular if for all $x,y\in L$

$$\mu(x)\mu(y)\leq \mu(x\wedge y)\mu(x\vee y)$$

A nonnegative function $f$ is increasing if it preserves the order.

FKG inequality states than given $\mu$ log supermodular and $f,g$ increasing,

$$\left(\sum_{x\in L}\mu(x)f(x)\right)\left(\sum_{x\in L}\mu(x)g(x)\right) \leq \left(\sum_{x\in L}\mu(x)f(x)g(x)\right)\left(\sum_{x\in L}\mu(x)\right)$$

Suppose $\mu$ is a probability measure, such as a ultrafilter, then,

$$\mathbb{E}(f) \mathbb{E}(g) \leq \mathbb{E}(fg)$$

indicates that two increasing functions are positive correlated.

Shepp's XYZ Theorem

Given $x,y,z\in P$ pairwise incomparable, then for $A$ varying over all linear extensions,

$$\mathbb{P}[A(x)\leq A(y)]\cdot \mathbb{P}[A(x)\leq A(z)] \leq \mathbb{P}[A(x)\leq A(y), A(x)\leq A(z)]$$

Or equivalently,

$$\mathbb{P}(A(x)\leq A(y)) \leq \mathbb{P}(A(x)\leq A(y)\mid A(x)\leq A(z))$$

Winkler's theorem

Suppose $P$ and $Q$ are two posets on the same base set $X$ but with different orders. If for all $x,y\in X$,

$$\mathbb{P}_P[ A(x)\leq A(y) ] \leq \mathbb{P}_Q[ B(x)\leq B(y) ]$$

Then, $Q$ can be obtianed by refining $P$.

Comparisons via linear extensions

Winkler's canonical linear ordering

Let $h_P(x)$ be the average rank of $x$ over all linear extensions of $P$.

Suppose $x,y\in P$ are incomparable, $P' = P\cup (x> y)$ and $P' = P\cup (x< y)$. Then, $h_{P'}(x) \geq h_{P}(x)$ and $h_{P'}(x) \geq 1 + h_{P''}(x)$.

$h_P$ is not always linear, but always well-defined.

Preferential ordering

Before Winkler, people doing social choice tried $x\triangleright y$ if $x$ less than $y$ happens more often, i.e. $\mathbb{P}[A(x) < A(y)] > \frac{1}{2}$.

However, $\triangleright$ is not always a partial order. Because in a poset there may exist 3 elements that are amazingly correlated. Fishburn constructs a set where $x\triangleright y\triangleright z \triangleright x$.

Intransitive dice

Let three dice $A = [2,2,4,4,9,9 ]$, $B = [1,1,6,6,8,8 ]$, $C = [3,3,5,5,7,7 ]$. Then, $P[A> B ] = P[B> C ] = P[C> A ] = \frac{5}{9}$.

1/3-2/3 Conjecture

This conjecture has not been proven yet. It states for all non-chain poset $P$, there exist two elements $x,y\in P$ such that the probability $x > y$ is within $[\frac{1}{3}, \frac{2}{3} ]$.

Some special cases are proven.

Summary

By focusing on poset, this course touched nearly every fields of combinatorics:

• Graph Theory: matching, path covering, perfect graph.
• Probabilistic Method: random graphs, correlated inequalityes.
• Combinatoric Optimization: min-cost flow.
• Geometric Combinatorics: poset polytopes, permutohedron.
• Enumerative Combinatorics: standard Young diagrams, evacuation, P-partition.
• Analytic Combinatorics: generating functions, asymptotic methods.
• Algebraic Combinatorics: Coxeter group, RSK.
• Arithmetic Combinatorics
  • Extremal Combinatorics: Sperner property, subsets with equal sums.
• Discrete Geometry: Integral polytope.
• Complexity

The most impressive thing I feel is that, different branches of math are highly related. After changing to a different point of view, some concepts, ideas, methods that previously looked totally unrelated can conctribute a lot.