组合数学

9 - Extremal Set Theory

2019-12-04 14:00 CST
2019-12-12 16:32 CST
CC BY-NC 4.0

What is extremal combinatorics?

How large or how small a collection of finite objects can be, if it has to satisfy certain restrictions.

Sunflowers

Definition: $\mathcal{F}$ is a sunflower of size $c$ with center $C$ if

  • $|\mathcal{F}| = r$
  • $\forall S, T \in \mathcal{F}, S \cap T = C$

Sunflower Lemma (Erdos-Rado 1960):

If $\mathcal{F} \subseteq {[n] \choose k}$ and $|\mathcal{F}| > k!(r-1)^k$, then there exists a sunflower $\mathcal{G} \subseteq \mathcal{F}$ such that $|\mathcal{G}| = r$.

Proof by induction on $k$.(太复杂,看讲义)

Intersecting Families

$\mathcal{F} \subseteq {[n] \choose k}$, intersecting means $\forall S, T \in \mathcal{F}$, $S \cap T \neq \emptyset$.

Trival case: $n < 2k$, $|\mathcal{F}| = 1$.

How large can a nontrival intersecting family be?

Erdos-Ko-Rado Theorem:

$$n \geqslant 2k \ \Longrightarrow \ |\mathcal{F}| \leqslant {n-1 \choose k-1}$$

Proof by induction on $n$ and $k$. (Construct two subfamily by whether contains $n$ or not.)

Shifting

  • With fixed perimeter, what plane figure has the largest area?
  • With fixed area, what plane figure has the smallest perimeter?

$\forall T \in \mathcal{F}$, write $T_{ij} = (T \setminus \{j\}) \cup \{i\}$.

$(i, j)$-shift $S_{ij}(\cdot)$ is defined as

$$S_{ij}(T) = \begin{cases} T_{ij} & \text{if } j \in T, i \notin T, \text{and } T_{ij} \notin \mathcal{F}, \\ T & \text{otherwise}. \end{cases}$$

$$S_{ij}(\mathcal{F}) = \{S_{ij}(T) | T \in \mathcal{F}\}$$

Properties:

  • $|S_{ij}(T)| = |T|$ and $S_{ij}(\mathcal{F}) = |\mathcal{F}|$
  • $\mathcal{F}$ intersecting $\Longrightarrow$ $S_{ij}(\mathcal{F})$ intersecting

Repeat applying $(i,j)$-shifting $S_{ij}(\mathcal{F})$ for all $1 \leqslant i < j \leqslant n$. Eventually, $\mathcal{F}$ is unchanged by any $S_{ij}(\mathcal{F})$, called $\mathcal{F}$ is **shifted**.

Erdos-Ko-Rado’s Proof:

True for $k=1$. When $n = 2k$, at most one of $S$ and $\bar{S}$ is in $\mathcal{F}$, hence

$$|\mathcal{F}| \leqslant \dfrac{1}{2}{n \choose k} = {n-1 \choose k-1}$$

When $n > 2k$, induction on $n$. Suppose $\mathcal{F}$ is shifted (without loss of generality = WLOG), let

$$\mathcal{F}_1 = \{ S \in \mathcal{F} | n \in S \}, \mathcal{F}_1' = \{ S \setminus \{n\} | S \in \mathcal{F}_1 \}$$

We can prove that $\mathcal{F}_1'$ is intersecting (otherwise leads to a contradiction).

Let $\mathcal{F}_0 = \{S \in \mathcal{F} | n \in S\}$, we know $\mathcal{F}_0$ is intersecting. Therefore by induction hypothesis,

$$|\mathcal{F}| \leqslant |\mathcal{F}_0| + |\mathcal{F}_1| \leqslant {n-2 \choose k-1} + {n-2 \choose k-2} = {n-1 \choose k-1}.$$

Katona’s Proof

  • $k$-arc: length $k$ path on a $n$-cycle
  • intersecting arcs: arcs that share edges

Lemma: $n \geqslant 2k$. Suppose $A_1, A_2, \dots, A_t$ are distinct pairwise intersecting $k$-arcs, then $t \leqslant k$.

Proof: take an $n$-cycle $\pi$ of $[n]$, the family of all $k$-arcs in $\pi$ are

$$\mathcal{G}_\pi = \{\{ \pi_{(i+j) \bmod n} | j \in [k] \} | i \in [n] \}.$$

Double counting on $X = \{ (S, \pi) | S \in \mathcal{F} \cap \mathcal{G}_\pi \}$:

  • Each $n$ cycle has at most $k$ intersecting $k$-arcs, there are $(n-1)!$ $n$-cycles, thus $$|X| \leqslant k(n-1)!$$
  • Each $S$ is a $k$-arc in $k!(n-k)!$ cycles , thus $$|X| = \sum_{S \in \mathcal{F}} |\{\pi | S \in \mathcal{G}_\pi\}| = |\mathcal{F}| k! (n-k)!$$

Therefore we have $|\mathcal{F}| \leqslant \dfrac{k(n-1)!}{k!(n-k)!} = \dbinom{n-1}{k-1}$.

Antichains

Definition: $\mathcal{F} \subseteq 2^{[n]}$ is an antichain if $\forall A, B \in \mathcal{F}, A \nsubseteq B$.

Theorem (Sperner 1928): For any antichain $\mathcal{F}$,

$$\mathcal{F} \leqslant {n \choose \lfloor n/2 \rfloor}.$$

For $\mathcal{F} \subseteq {[n] \choose k}$, define

  • shade: $$\nabla \mathcal{F} = \left\{ T \in {[n] \choose k+1} \vert \exists S \in \mathcal{F}, S \subset T \right\}$$
  • shadow: $$\Delta \mathcal{F} = \left\{ T \in {[n] \choose k-1} \vert \exists S \in \mathcal{F}, T \subset S \right\}$$

Lemma (Sperner): Let $\mathcal{F} \subseteq {[n] \choose k}$, then

  • for $k < n$, $|\nabla \mathcal{F}| \geqslant \frac{n-k}{k+1} |\mathcal{F}|$,
  • for $k > 0$, $|\Delta \mathcal{F}| \geqslant \frac{k}{n-k+1} |\mathcal{F}|$.

Corollary:

  • If $k \leqslant \frac{1}{2}(n-1)$, then $|\nabla \mathcal{F}| \geqslant |\mathcal{F}|$.
  • If $k \geqslant \frac{1}{2}(n+1)$, then $|\Delta \mathcal{F}| \geqslant |\mathcal{F}|$.

When $k = \lfloor n/2 \rfloor$, there is no decreasing of $|\mathcal{F}|$.

Lubell’s Proof

Length of a maximal chain in $2^{[n]}$ is $n$, # of maximal chains in $2^{[n]}$ is $n!$.

For all $S \subseteq [n]$, # of maximal chains containing $S$ is $|S|! (n-|S|)!$.

By definition, we have $$\mathcal{F} \text{ is antichain} \Longrightarrow \forall C \text{ is chain}, |\mathcal{F} \cap C| \leqslant 1.$$

Therefore # of maximal chains crossing $\mathcal{F} \leqslant$ # of all maximal chains.

$$\sum_{S \in \mathcal{F}} |S|!(n-|S|)! \leqslant n!$$

Since ${n \choose |S|} \leqslant {n \choose \lfloor n/2 \rfloor}$, we can then conclude that $|\mathcal{F}| \leqslant {n \choose \lfloor n/2 \rfloor}$.

LYM Inequality

LYM inequality: $\mathcal{F} \subseteq 2^{[n]}$ is an antichain, $$\sum_{S \in \mathcal{F}} \dfrac{1}{{n \choose |S|}} \leqslant 1.$$

Alon’s proof (the probabilistic method): let $\pi$ be a random permutation of $[n]$, define

$$\mathcal{C}_\pi = \{ \{\pi_1\}, \{\pi_1, \pi_2\}, \dots \}$$

For all $S \in \mathcal{F}$, define random variable $X_S = 1$ iff $S \in \mathcal{C}_\pi$.

Let $X = \sum\limits_{S \in \mathcal{F}} X_S = |\mathcal{F} \cap \mathcal{C}_\pi|$. Since $\mathcal{C}_\pi$ contains precisely 1 $|S|$-set, we have

$$E[X_S] = Pr[S \in \mathcal{C}_\pi] = \dfrac{1}{{n \choose |S|}}.$$

Since $\mathcal{F}$ is antichain, we know

$$X = \sum_{S \in \mathcal{F}} X_S = |\mathcal{F} \cap \mathcal{C}_\pi| \leqslant 1$$

thus by probability method we know that $1 \geqslant E[X] = \sum\limits_{S \in \mathcal{F}} E[X_S]$ and thus LYM inequality is true.

Shattering

Let $\mathcal{F} \subseteq 2^{[n]}, R \subseteq [n]$, define

  • trace $\mathcal{F}|_R = \{ S \cap R | S \in \mathcal{F} \}$
  • $\mathcal{F}$ shatters $\mathcal{R}$ if $\mathcal{F}|_R = 2^R$.

Sauer’s Lemma: if $|\mathcal{F}| > \sum\limits_{0 \leqslant i < k}{n \choose i}$, then $\exists R \in {[n] \choose k}$ such that $\mathcal{F}$ shatters $R$.

Define VC-dimension of $\mathcal{F}$: size of the largest $R$ shattered by $\mathcal{F}$.

$$\text{VC-dim}(\mathcal{F}) = \max \{ |R| | R \subseteq [n], \mathcal{F}|_R = 2^R \}$$

Heredity

$\mathcal{F}$ is hereditary if $\forall B \subseteq A \in \mathcal{F}$, $B \in \mathcal{F}$.

For any hereditary $\mathcal{F}$,

$$\forall B \subseteq A \in \mathcal{F}, B \in \mathcal{F}$$

therefore

$$R \in \mathcal{F} \Longrightarrow \mathcal{F} \text{ shatters } R.$$

Down Shift

Define down-shift $S_i(\cdot)$:

$$S_i(T) = \begin{cases} T \setminus \{i\} & \text{if } i \in T \in \mathcal{F}, \text{and } T \setminus \{i\} \notin \mathcal{F}, \\ T & \text{otherwise} \end{cases}$$

$$S_i(\mathcal{F}) = \{S_i(T) | T \in \mathcal{F}\}$$

Properties:

  • $|S_i(\mathcal{F})| = |\mathcal{F}|$
  • $|S_i(\mathcal{F})|_R| \leqslant |\mathcal{F}|_R|$ for all $R \subseteq [n]$
  • $S_i(\mathcal{F})|_R \subseteq S_i(\mathcal{F}|_R)$

Repeat applying down-shifting to $\mathcal{F}$ until $\mathcal{F}$ is unchanged by any $S_i(\cdot)$, then $\mathcal{F}$ is hereditary.

Since $|\mathcal{F}| > \sum\limits_{0 \leqslant i < k} {n \choose i}$, there exists a $k$-size subset $R$ of $\mathcal{F}$, thus $\mathcal{F}$ shatters $R$.

Kruskal-Katona Theorem

How small can the shadow $\Delta \mathcal{F}$ be?

Colex Order of Sets

  • Lexicographic order: elements in increasing order, sets in lexicographic order.
  • Co-lexicographic (colex) order: elements in decreasing order, sets in lexicographic order.

Define $\mathcal{R}(m,k)$ as the first $m$ members of ${\mathbb{N} \choose k}$ in colex order.

$$\mathcal{R} \left( {n \choose k}, k \right) = {[n] \choose k}$$

$k$-cascade Representation

For any positive integers $m$ and $k$, $m$ can be uniquely represented as

$$m = \sum_{l=t}^{k} {m_l \choose l}.$$

K-K Theorem

$\mathcal{F} \subseteq {[n] \choose k}$, $|\mathcal{F}| = m$, the $k$-cascade of $m$ is $$m = {m_k \choose k} + {m_{k-1} \choose k-1} + \dots + {m_t \choose t},$$ then $$|\Delta \mathcal{F}| \geqslant {m_k \choose k-1} + {m_{k-1} \choose k-2} + \dots + {m_t \choose t-1}.$$

The first $m$ $k$-sets in colex order have the smallest shadow.

$$|\Delta \mathcal{F}| \geqslant |\Delta \mathcal{R}(|\mathcal{F}|, k)|$$