组合数学

课程编号:081200D14(本科:22010240)

课程教师:尹一通

课程主页:http://tcs.nju.edu.cn/wiki

总体评价:知识点和作业特别难,考试比较偏重基础

1. Basic Enumeration

Preface

Combinatorial problems:

  • Enumeration (counting):有多少个符合条件的解?
  • Existence:是否存在解?
    • Extremal(极问题):满足特定约束的解最大/最小是多少?
    • Ramsey:当解很大的时候会出现什么结构?
  • Optimization:找到最优解
  • Construction (design):构造一个解

Enumeration

How many ways are there:

  • to rank \( n \) people: \( n! \)
  • to assign \( m \) zodiac signs to \( n \) people: \( m^n \)
  • to choose \( m \) people out of \( n \) people: \( \binom{n}{m} \)
  • to partition \( n \) people into \( m \) groups: \( {n \brace m} = \binom{n+m-1}{m-1} \) (stirling numbers of the second kind)
  • to distribute \( m \) yuan to \( n \) people: \( n^m \)
  • to partition \( m \) yuan to \( n \) parts: \( p_n(m) \) (partition number)
  • \( \dots \)

The Twelvefold Way

Knuth's version: \( n \) balls are put into \( m \) bins

balls per binany\( \leqslant 1 \)\( \geqslant 1 \)
\( n \) distinct balls, \( m \) distinct bins\( m^n \)\( (m)_n \)\( m!{n \brace m} \)
\( n \) identical balls, \( m \) distinct bins\( \left({m \choose n}\right) \)\( {m \choose n} \)\( {n-1 \choose m-1} \)
\( n \) distinct balls, \( m \) identical bins\( \sum\limits_{k=1}^{m} {n \brace k} \)\( \begin{cases}1 \text{ if } n \leqslant m \\ 0 \text{ if } n > m\end{cases} \)\( {n \brace m} \)
\( n \) identical balls, \( m \) identical bins\( \sum\limits_{k=1}^m p_k(n) \)\( \begin{cases}1 \text{ if } n \leqslant m \\ 0 \text{ if } n > m\end{cases} \)\( p_m(n) \)

Tuples

符号定义:

  • \( [m] = \lbrace 1, 2, \dots, m \rbrace \)
  • \( [m]^n = [m] \times \dots \times [m] \)
  • \( \vert [m]^n \vert = m^n \)

Product rule: \( \vert S \times T \vert = \vert S \vert \cdot \vert T \vert \).

Functions

Bijection rule: 若存在\( S \)到\( T \)的双射,则\( \vert S \vert = \vert T \vert \).

Therefore, the number of functions:

  • \( f: [n] \rightarrow [m] \)
  • \( f \Leftrightarrow (f(1), \dots, f(n)) \in [m]^n \)
  • \( \vert [n] \rightarrow [m] \vert = \vert [m]^n \vert = m^n \).

The number of 1-1 functions (injections):

  • \( \pi = (f(1), \dots, f(n)) \)
  • \( n \)-permutation: \( \pi \in [m]^n \) of distinct elements
  • \( \vert \pi \vert = \dfrac{m!}{(m-n)!} = (m)_n \) (\( m \) lower factorial \( n \))

Subsets

  • \( [n] = \lbrace 1, 2, \dots, n \rbrace \)
  • Power set: \( 2^{[n]} = \lbrace S | S \subseteq [n] \rbrace \)
  • \( \vert 2^{[n]} \vert = 2^n \)

Sum rule: finite disjoint sets \( S \) and \( T \), \( \vert S \cup T \vert = \vert S \vert + \vert T \vert \).

\( \Rightarrow \vert 2^{[n]} \vert = 2\vert 2^{[n-1]} \vert, \vert 2^{\emptyset} \vert = 1 \).

Subsets of fixed size:

  • \( k \)-uniform: \( {S \choose k} = \lbrace T \subseteq S | \vert T \vert = k \rbrace \)
  • \( {n \choose k} = \vert {[n] \choose k} \vert = \dfrac{n!}{k!(n-k)!} \)

Binomial coefficients

Binomial coefficient: \( {n \choose k} = \dfrac{n!}{k!(n-k)!} \)

Properties:

  • \( {n \choose k} = {n \choose n-k} \)
  • \( \sum\limits_{k=0}^{n} {n \choose k} = 2^n \)
  • # of odd subsets = # of even subsets

Binomial theorem: \( (1+x)^n = \sum\limits_{k=0}^{n} {n \choose k} x^k \).

Compositions of an integer

\( n \)块钱分给\( k \)个不同的人,每个人至少一块钱:

\( k \)-composition of \( n \): a \( k \)-tuple \( (x_1, x_2, \dots, x_k) \), satisfying

\[ x_1 + x_2 + \dots + x_k = n, \ x_i \in \mathbb{Z}^+ \]

# of \( k \)-composition of \( n \): \( {n-1 \choose k-1} \) (can be proven in the following ways)

  • 高中的插板法
  • Define \( \phi((x_1, \dots, x_k)) = \lbrace x_1, x_1 + x_2, \dots, x_1 + x_2 + \dots + x_{k-1} \rbrace \), then \( \phi \) is a 1-1 correspondence between \( k \)-compositions of \( n \) and \( {[n-1] \choose k-1} \).

Weak \( k \)-composition of \( n \): \( x_i \in \mathbb{N} \) \[ (x_1 + 1) + (x_2 + 1) + \dots + (x_k + 1) = n + k \]

# of weak \( k \)-composition of \( n \): \( {n+k-1 \choose k-1} \)

Multisets

\( k \)-subset of \( S \): "\( k \)-combination of set \( S \) without repetition".

# of \( k \)-subset is denoted as \( \left( {n \choose k} \right) = {n+k-1 \choose n-1} = {n+k-1 \choose k} \).

\( k \)-subset of \( S \) is a weak \( n \)-composition of \( k \).

Multinomial coefficients

Permutations of a multiset of size \( n \) with multiplicities \( m_1, m_2, \dots, m_k \)

= Assign \( n \) distinct balls to \( k \) distinct bins with the \( i \)-th bin receiving \( m_i \) balls

E.g. # of reordering of "multinomial" \( \Leftrightarrow \) permutations of {a, i, i, l, l, m, m, n, o, t, u}

Multinomial coefficient is denoted as \( {n \choose m_1, \dots, m_k} = \dfrac{n!}{m_1! m_2! \dots m_k!} \).

Multinomial theorem: \( (x_1 + \dots + x_k)^n = \sum\limits_{m_1+\dots+m_k = n} {n \choose m_1, \dots, m_k} x_1^{m_1} \cdots x_k^{m_k} \)

Partitions of a set

把\( n \)个人分到\( k \)艘船上,每艘船至少一个人

Divide a set of \( n \) into \( k \) partitions

\( P = \lbrace A_1, \dots, A_k \rbrace \) is a partition of \( S \) if:

  • \( A_i \neq \emptyset \),
  • \( A_i \cap A_j = \emptyset \),
  • and \( \bigcup A_i = S \).

# of \( k \)-partitions of an \( n \) set (Stirling number of the second kind) is denoted as \( {n \brace k} \).

# of all partitions of an \( n \) set (Bell number) is \( B_n = \sum\limits_{k=1}^{n} {n \brace k} \).

Satisfies: \( {n \brace k} = k {n-1 \brace k} + {n-1 \brace k-1} \) (as the following two cases)

  • case 1: \( \lbrace n \rbrace \) is not a partition block
  • case 2: \( \lbrace n \rbrace \) is a partition block

Surjections

\( \forall i \in [m] \), \( f^{-1}(i) \neq \emptyset \), then

\( f \Leftrightarrow (f^{-1}(1), \dots, f^{-1}(m)) \).

Surjections is equal to an ordered \( m \)-partition of \( [n] \)

Therefore # of surjections is \( m! {n \brace m} \).

Partitions of a number

\( p_k(n) \): # of partitions of \( n \) into \( k \) parts

Equal to # of integral solutions to

\[ \begin{cases}x_1 + \dots + x_k = n, \ x_1 \geqslant \dots \geqslant x_k \geqslant 1\end{cases} \]

Depending on \( x_k = 1 \) or not, we have

\[ p_k(n) = p_{k-1}(n-1) + p_k(n-k) \]

Difference of partition and composition:

  • partition: \( x_1 \geqslant \dots \geqslant x_k \geqslant 1 \)
  • composition: \( x_i \geqslant 1 \)

Every partition is a composition (onto).

If we have a partition of \( n \) into \( k \) parts \( x_1 \dots x_k \), then by defining \( y_i = x_i + k - i \), we have a \( k \) composition of \( n + \dfrac{k(k-1)}{2} \) (1-1).

Therefore, we have

\[ \dfrac{{n-1 \choose k-1}}{k!} \leqslant p_k(n) \leqslant \dfrac{n + \frac{k(k-1)}{2} -1 \choose k-1}{k!} \]

Results of Young Graph:

  • # of partitions of \( n \) into \( k \) parts = # of compositions of \( n \) with largest part being \( k \)
  • # of partitions of \( n \) into \( k \) parts = # of partitions of \( n-k \) into at most \( k \) parts

2. Generating Functions

What is # of compositions of \( n \) with summands from \( \lbrace 1, 2 \rbrace \)?

  • Case 1: \( x_k = 1 \), then \( x_1 + \dots + x_{k-1} = n-1 \),
  • Case 2: \( x_k = 2 \), then \( x_1 + \dots + x_{k-1} = n-2 \).

Thus \( a_n = a_{n-1} + a_{n-2} \).

Catalan Number

\( C_n \): # of full binary trees with \( n+1 \) leaves

Using recursion: \( C_0 = 1 \), for all \( n \geqslant 1 \),

\[ C_n = \sum\limits_{k=0}^{n-1}C_k C_{n-1-k} \]

Double Decks

How to choose \( m \) cards from \( 2 \) decks of \( n \) cards?

Each card can be chosen for no times, once and twice:

\[ (x_1^0 + x_1^1 + x_1^2) (x_2^0 + x_2^1 + x_2^2) \cdots (x_n^0 + x_n^1 + x_n^2) \]

\[ \Rightarrow (1+x+x^2)^n = \sum_k \sum_{l \leqslant k} {n \choose k}{k \choose l} x^{k+l} = \sum_m \left( \sum_l {n \choose m-l} {m-l \choose l} \right) x^m \]

Multisets

Multisets on \( S = \lbrace x_1, \dots, x_n \rbrace \).

Each element can be chosen for no time, once, twice, ...

\[ (1 + x_1^1 + x_1^2 + \dots) (1 + x_2^1 + x_2^2 + \dots) \cdots (1 + x_n^1 + x_n^2 + \dots) \]

\[ (1 + x^1 + x^2 + \dots)^n = \sum_{m \in \mathbb{N}^n} x^{m_1 + \dots + m_n} = \sum_{k \geqslant 0} \left( {n \choose k} \right) x^k \]

By some magic:

\[ (1 + x^1 + x^2 + \dots)^n = (1-x)^{-n} = \sum_{k \geqslant 0} {n+k-1 \choose k} x^k \]

Therefore \( \left( {n \choose k} \right) = {n+k-1 \choose k} \).

Ordinary Generating Function

\( G(x) = \sum\limits_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + \dots \)

Define \( [x^n]G(x) = a_n \).

Fibonacci Number

Solution of \( F_n \): \( \phi = \dfrac{1 + \sqrt{5}}{2}, \hat{\phi} = \dfrac{1 - \sqrt{5}}{2} \)

\[ F_n = \dfrac{1}{\sqrt{5}} \left( \phi^n - \hat{\phi}^n \right). \]

By recursion:

\( G(x) = F_0 + F_1 x + \sum\limits_{n \geqslant 2} F_n x^n = x + \sum\limits_{n \geqslant 2} F_{n-1} x^n + \sum\limits_{n \geqslant 2} F_{n-2} x^n \)

Identity: \( G(x) = x + (x + x^2) G(x) \).

Solution: \( G(x) = \dfrac{x}{1-x-x^2} \).

Formal Power Series

\( G(x) = \sum\limits_{n=0}^{\infty} a_n x^n \)

\( \mathbb{C}[x] \): ring of formal power series with complex coefficient

Inverse: \( F(x)G(x) = 1 \Longrightarrow F(x) = G^{-1}(x) = \dfrac{1}{G(x)} \)

Generatingfunctionology

  1. Recurrence: \( a_n = a_{n-1} + a_{n-2} \)
  2. Manipulation: \( G(x) = x + (x + x^2) G(x) \)
  3. Solving: \( G(x) = \dfrac{x}{1-x-x^2} = \dots \)

Generating Function Manipulations

\( G(x) = \sum\limits_{n \geqslant 0} g_n x^n, F(x) = \sum\limits_{n \geqslant 0} f_n x^n \)

  • shift: \( x^kG(x) = \sum\limits_{n \geqslant k} g_{n-k} x^n \)
  • addition: \( F(x)+G(x) = \sum\limits_{n \geqslant 0} (f_n + g_n) x^n \)
  • convolution: \( F(x)G(x) = \sum\limits_{n \geqslant 0} \sum\limits_{k=0}^n f_k g_{n-k} x^n \)
  • differentiation: \( G'(x) = \sum\limits_{n \geqslant 0} (n+1) g_{n+1} x^n \)

Expanding Generating Functions

  • Taylor's expansion: \[ G(x) = \sum_{n \geqslant 0} \dfrac{G^{(n)}(0)}{n!} x^n \]
  • Geometric sequence: \[ \dfrac{a}{1-bx} = a \sum_{n \geqslant 0} (bx)^n \]
  • Binomial theorem (Newton's formula): \[ (1+x)^\alpha = \sum_{n \geqslant 0} {\alpha \choose n} x^n \]

Generalized binomial coefficient: \[ {\alpha \choose n} = \dfrac{\alpha (\alpha-1) \cdots (\alpha - n + 1)}{n!} \]

Catalan Number (cont'd)

\( C_0 = 1 \), for all \( n \geqslant 1 \),

\[ C_n = \sum\limits_{k=0}^{n-1}C_k C_{n-1-k} \]

Manipulation:

\( G(x) = \sum_{n \geqslant 0} C_nx^n = C_0 + \sum_{n \geqslant 1} \sum_{k=0}^{n-1} C_{k} C_{n-1-k} x^n \)

\( \Longrightarrow G(x) = 1 + xG^2(x) \)

Solving:

\( \Longrightarrow G(x) = \dfrac{1 \pm (1-4x)^{1 / 2}}{2x} \)

Since \( \lim\limits_{x \rightarrow 0} G(x) = C_0 = 1 \), we have

\[ G(x) = \dfrac{1 - (1-4x)^{1 / 2}}{2x} \]

Expanding (by Newton's formula):

\[ \begin{align} (1-4x)^{1 / 2} &= \sum\limits_{n \geqslant 0} {1 / 2 \choose n} (-4x)^n \\ &= 1 + \sum\limits_{n \geqslant 1} {1 / 2 \choose n} (-4x)^n \\ &= 1 + \sum\limits_{n \geqslant 0} {1 / 2 \choose n + 1} (-4x)^{n+1} \\ &= 1 - 4x \sum\limits_{n \geqslant 0} {1 / 2 \choose n} (-4x)^n \end{align} \]

Therefore, \( G(x) = \dfrac{1 - (1-4x)^{1 / 2}}{2x} = 2 \sum\limits_{n \geqslant 0} {1 / 2 \choose n + 1} (-4x)^n = \sum\limits_{n \geqslant 0} 2 {1 / 2 \choose n + 1} (-4)^n x^n \)

We get \( C_n = 2 {1 / 2 \choose n + 1} (-4)^n \).

Further more, \( C_n = \dfrac{1}{n+1} {2n \choose n} \).

Quicksort

Complexity:

  • worst case: \( \Theta(n^2) \)
  • average case: ?

Let \( T_n \) be the average # of comparisons used by quick sort.

Suppose \( \pi \) is a uniform random permutation of \( S_n \), then we run quick sort on \( \pi \).

Suppost the pivot is the \( k \)-th smallest number in \( \pi \), then we have the # of elements in both sections:

  • \( \vert L \vert = k - 1 \)
  • \( \vert R \vert = n - k \)

Since \( \pi \) is uniformly random, the probability of pivot being the \( k \)-th smallest element for any \( k \) is \( \dfrac{1}{n} \).

By recursion, we have \[ T_n = \dfrac{1}{n} \sum\limits_{k=1}^n (n-1 + T_{k-1} + T_{n-k}) \]

-> \( T_n = \Theta(n \lg n) \) (see the slides).

3. Sieve Methods

Principle of Inclusion-Exclusion

\( \left\vert \bigcup\limits_{i=1}^n A_i \right\vert = \sum\limits_{I \subseteq {1, \dots, n}, I \neq \emptyset} (-1)^{\vert I \vert - 1} \left\vert \bigcap\limits_{i \in I} A_i \right\vert \).

Suppose \( A_1, \dots, A_n \subseteq U \), then \[ \left\vert \overline{A_1} \cap \dots \cap \overline{A_n} \right\vert = \left\vert U - \bigcup\limits_{i=1}^n A_i \right\vert. \]

Denote \( A_I = \bigcap\limits_{i \in I} A_i \), \( A_{\emptyset} = U \).

Surjections

What is # of onto functions from \( [n] \) to \( [m] \)?

Let \( U \) be the domain of functions \( [n] \rightarrow [m] \). \( A_i = [n] \rightarrow ([m] \setminus {i}). \)

Then we have \[ \left\vert \bigcap_{i \in [m]} \overline{A_i} \right\vert = \sum\limits_{I \subseteq [m]} (-1)^{\vert I \vert} \vert A_I \vert = \sum\limits_{I \subseteq [m]} (-1)^{\vert I \vert} (m - \vert I \vert)^n = \sum\limits_{k=0}^{m} (-1)^{m-k} {m \choose k} k^n. \]

Therefore, the sterlin number of the second kind is \[ {n \brace m} = \dfrac{1}{m!} \sum\limits_{k=0}^{m} (-1)^{m-k} {m \choose k} k^n. \]

Derangement

# of permutation \( \pi \) of \( [n] \), \( \forall i \), \( \pi(i) \neq i \). (permutations with no fixed point, denoted as \( !n \)).

\( U \): all permutations of \( [n] \) (a symetric group), \( A_i \): permutations with \( \pi(i) = i \).

Size of \( A_I \) is \( (n - \vert I \vert)! \).

\[ \left\vert \bigcap_{i \in [n]} \overline{A_i} \right\vert = \sum\limits_{I \subseteq [n]} (-1)^{\vert I \vert} \vert A_I \vert = \dots = n! \sum_{k=0}^n \dfrac{(-1)^k}{k!} = \dfrac{n!}{e}. \]

Permutations with restricted positions

  • Derangement: \( \forall i, \pi(i) \neq i \)
  • Generally: \( \pi(i_1) \neq j_1, \pi(i_2) \neq j_2, \dots \)
  • Forbidden patterns: \( B \subseteq [n] \times [n], \forall i, (i, \pi(i)) \notin B \)

A chess board: a grid of \( [n] \times [n] \). To put \( n \) chess pieces on the board and with no two pieces on same row/column. (A placement of non-attacking rooks).

Forbidden positions \( B \subseteq [n] \times [n] \)

Derangement: \( \forall i, (i, i) \notin B \) (not on the diagonal).

\( r_k \): # of ways of placing \( k \) non-attacking rooks in \( B \).

\[ r_k = {n \choose k}. \]

\( N_0 \): # of placements of \( n \) non-attacking rooks.

\[ N_0 = \sum\limits_{k=0}^{n} (-1)^k r_k (n-k)! = \sum\limits_{k=0}^{n} (-1)^k {n \choose k} (n-k)! \rightarrow \dfrac{n!}{e}. \]

Ménage Problem

# of ways that \( n \) couples sit around a table, satisfying

  • male-female alternative
  • no one sit next to its spouse

Ladies first choose where to sit: \( 2 \cdot n! \) ways (all odd or all even).

Then gentlemen sit, each way has a corresponding permutation \( \pi \) of \( [n] \).

  • \( i \): husband of the lady at the \( i \)-th position.
  • \( \pi(i) \): his position

Requires

  • \( \pi(i) \neq i \)
  • \( \pi(i) \neq i+1 \mod n \)

\( \Rightarrow \) Chess game again: \( B = {(i, i), (i, i+1 \mod n)} \).

  • \( r_k \): # of ways of placing \( k \) non-attacking rooks in \( B \).
  • \( r_k \): # of ways of choosing \( k \) non-consecutive points from a circle of \( 2n \) points

\( \Rightarrow \) \( L(m, k) \): # of ways to choose \( k \) non-consecutive objects from a line of \( m \) objects.

  • select \( k \) slots from \( n-k+1 \) slots after removing \( k \) objects.

\[ L(m, k) = {n-k+1 \choose k}. \]

\( C(m, k) \): # of ways to choose \( k \) non-consecutive objects from a circle of \( m \) objects.

  • choose \( k \) non-consecutive objects from a circle and mark one of the remaining objects: \( (m-k) \cdot C(m, k) \).
  • mark one object and disconnect the circle by removing the object, then choose \( k \) non-consecutive objects from the \( m-1 \) objects: \( m \cdot L(m-1, k) \).

\[ C(m, k) = \dfrac{m}{m-k} L(m-1, k) = \dfrac{m}{m-k} {m-k \choose k}. \]

\( \Leftarrow \) \( r_k = \dfrac{2n}{2n-k}{2n-k \choose k} \). Therefore,

\[ N_0 = \sum\limits_{k=0}^{n} (-1)^k r_k (n-k)! = \sum\limits_{k=0}^{n} (-1)^k \dfrac{2n}{2n-k} {2n-k \choose k} (n-k)! \]

Inversion

\( V \): \( 2^n \)-dimensional vector space of all mappings

\[ f: 2^{[n]} \rightarrow \mathbb{N}. \]

linear transformation \( \phi: V \rightarrow V \).

\[ \forall S \subseteq [n], \ \ \phi(f(S)) \overset{\Delta}{=} \sum_{T \supseteq S, T \subseteq [n]} f(T). \]

then its inverse:

\[ \forall S \subseteq [n], \ \ \phi^{-1} (f(S)) = \sum_{T \supseteq S, T \subseteq [n]} (-1)^{[T \setminus S]} f(T). \]

\( f_{=}(I) = \left\vert \left\{ x \in U | \forall i \in I, x \in A_i, \forall j \notin I, x \notin A_j \right\} \right\vert = \left\vert \left(\bigcap\limits_{i \in I} A_i\right) \setminus \left(\bigcap\limits_{j \notin I} A_j\right) \right\vert. \)

\( f_{\geqslant} (I) = \sum\limits_{J \supseteq I, J \subseteq [n]} f_{=}(J) = \left\vert \bigcap\limits_{i \in I} A_i \right\vert = \vert A_I \vert. \)

PIE:

  • \( \sum\limits_{I \subseteq S} (-1)^{\vert S \vert - \vert I \vert} = \begin{cases}1, & S = \emptyset, \\ 0, & \text{otherwise}.\end{cases} \)
  • for all \( T \subseteq S \), \[ \sum\limits_{T \subseteq I \subseteq S} (-1)^{\vert S \vert - \vert I \vert} = \begin{cases}1, & S = T, \\ 0, & \text{otherwise}.\end{cases} \]

Bipartite perfect matching

Given a bipartite graph \( G([n], [n], E) \), # of permutations \( \pi \) of \( [n] \) satisfying that \( (i, \pi(i)) \in E \).

\( n \times n \) matrix \( A \): \( A_{ij} = \begin{cases}1, & (i, j) \in E, \\ 0, & (i, j) \notin E. \end{cases} \)

# of perfect matching in \( G = \sum\limits_{\pi \in S_n} \prod\limits_{i \in [n]} A_{i, \pi(i)} \).

  • permanent: \( \text{perm}(A) = \sum\limits_{\pi \in S_n} \prod\limits_{i \in [n]} A_{i, \pi(i)} \).
  • determinant: \( \det(A) = \sum\limits_{\pi \in S_n} (-1)^{r(\pi)} \prod\limits_{i \in [n]} A_{i, \pi(i)}. \)

Ryser's formula \( O(n!) \rightarrow O(n 2^n) \):

\[ \sum\limits_{\pi \in S_n} \prod\limits_{i \in [n]} A_{i, \pi(i)} = \sum\limits_{I \subseteq [n]} (-1)^{n - \vert I \vert} \prod_{i \in [n]} \sum_{j \in I} A_{ij}. \]

Sieve of Eratosthenes

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

Euler Totient Function

\( \phi(n) = \left\vert \left\{ 1 \leqslant a \leqslant n | \gcd(a,n) = 1 \right\} \right\vert \).

prime decomposition: \( n = p_1^{k_1} p_2^{k_2} \cdots p_{r}^{k_r} \).

\( U = [n], A_i = \left\{ 1 \leqslant a \leqslant n \ {\large|} \ p_i \vert a \right\} \).

\( \vert A_i \vert = \dfrac{n}{p_i}, \vert A_I \vert = \dfrac{n}{\prod p_i}. \)

Therefore, \( \phi(n) = \sum_{I \subseteq [r]} (-1)^{\vert I \vert} \vert A_I \vert = n \prod\limits_{i=1}^{r} \left( 1 - \dfrac{1}{p_i} \right). \)

4. Symmetry

Permutation Groups

Group \( (G, \cdot) \) with binary operator \( \cdot: G \times G \rightarrow G \)

  • closure: \( \pi, \sigma \in G \Rightarrow \pi \cdot \sigma \in G \)
  • associativity: \( \pi \cdot (\sigma \cdot \tau) = (\pi \cdot \sigma) \cdot \tau \)
  • identity: \( \exists e, e \cdot \pi = \pi \)
  • inverse: \( \pi \cdot \sigma = e, \pi = \sigma^{-1} \)

Commutative (abelian) group: \( \pi \cdot \sigma = \sigma \cdot \pi \)

  • Symmetric group \( S_n \): all permutations \[ \pi: [n] \underset{onto}{\overset{1-1}{\longrightarrow}} [n] \]
  • Cyclic group \( C_n \): rotations \[ \pi = (012\cdots n-1), C_n = \langle \pi \rangle \]
  • Dihedral group \( D_n \): rotations & reflections: generated by \( (012\cdots n-1) \) and \( \rho \) (reflection)

Group Action

Configuration \( x: [n] \rightarrow [m] \), \( X = [m]^{[n]} \)

Permutation: \( \pi: [n] \underset{onto}{\overset{1-1}{\longrightarrow}} [n] \)

Group action: \( \circ: G \times X \rightarrow X \)

  • associativity: \( (\pi \cdot \sigma) \circ x = \pi \circ (\sigma \circ x) \)
  • identity: \( e \circ x = x \)

Graph Isomorphism (GI)

  • Input: two undirected graphs \( G \) and \( H \)
  • Output: \( G \cong H ? \)
  • GI is in NP (Babai's algorithm).

String Isomorphism (SI)

  • Input: two strings \( x, y: [n] \rightarrow [m] \), and a permutation group \( G \subseteq S_n \)
  • Output: \( x \cong_G y ? \) (i.e., \( \exists \sigma \in G, \sigma \circ x = y \))

Johnson group: \( \mathbb{S}_V^{(2)} \subset S_{{V \choose 2}} \) on vertex pairs

Two graphs \( X \cong Y \) iff their string versions \( x \cong_{\mathbb{S}_V^{(2)}} y \)

Orbits

Group action \( \circ \)

Define orbit of \( x \): \( Gx = \left\lbrace \pi \circ x | \pi \in G \right\rbrace \), an equivalent class of configuration \( x \)

\( X/G = \left\lbrace Gx | x \in X \right \rbrace \)

Our goal: count \( \vert X/G \vert \)

Example: \( X = [2]^{[6]} \): \( \vert X/G \vert \) is the number of ways to put 2 colors onto a ring of 6 elements.

Let \( \vec v = (n_1, n_2, \dots, n_m), \sum n_i = n \), then \( a_{\vec v} \) is # of configurations (up to symmetry) with number of color \( i \) being \( n_i \).

Pattern inventory: (multi-variate) generating function:

\[ F_G(y_1, y_2, \dots, y_m) = \sum_{\vec v} a_{vec v} y_1^{\vec v_{n_1}} y_2^{\vec v_{n_2}} \cdots y_m^{\vec v_{n_m}} \]

Example: \( n=2, m=6, F_{D_6}(y_1, y_2) = y_1^6 + y_1^5 y_2 + 3y_1^4 y_2^2 + 3y_1^3 y_2^3 + 3y_1^2 y_2^4 + 3y_1 y_2^5 + y_2^6 \)

Burnside's Lemma

Define invariant set of \( \pi \): \( X_\pi = \left\lbrace x \in X | \pi \circ x = x \right\rbrace \).

Burnside's Lemma:

\[ \vert X/G \vert = \dfrac{1}{\vert G \vert} \sum\limits_{x \in G} \vert X_\pi \vert. \]

Define stabilizer of \( x \): \( G_x = \left\lbrace \pi \in G | \pi \circ x = x \right\rbrace \).

Lemma: \( \forall x \in X, \vert G_x \vert \vert Gx \vert = \vert G \vert. \)

\[ A(\pi, x) = \begin{cases}1, & \pi \circ x = x \\ 0, & \text{o.w.} \end{cases} \]

  • \( \vert X_\pi \vert = \sum\limits_{x \in X} A(\pi, x) \)
  • \( \vert G_x \vert = \sum\limits_{\pi \in G} A(\pi, x) \)

Double counting: \[ \sum_{\pi \in G} \vert X_\pi \vert = \sum_{\pi \in G}\sum_{x \in X} A(\pi, x) = \sum_{x \in X} \vert G_x \vert = \vert G \vert \sum_{x \in X} \dfrac{1}{\vert G_x \vert} = \overset{??}{\cdots} = \vert G \vert \vert X/G \vert \]

Cycle Decomposition

E.g. \( \dbinom{0\ 1\ 2\ 3\ 4}{2\ 4\ 0\ 1\ 3} = (02)(143) \), decompose a permutation into 2 cycles.

Invarian \( \pi \circ x = x \), forall \( i \), \( x(\pi(i)) = x(i) \), iff every cycle of \( \pi \) has the same color.

If \( X = [m]^{[n]} \) (\( m \) colors, \( n \) elements on a ring), \( \pi \) has \( k \) cycles, then \( \vert X_\pi \vert = m^k \)

Burnside's Lemma (cont'd): \[ \vert X/G \vert = \dfrac{1}{\vert G \vert} \sum\limits_{x \in G} \vert X_\pi \vert = \dfrac{1}{\vert G \vert} \sum\limits_{x \in G} m^{\text{\# of cycle in } \pi}. \]

Cycle Index

Suppose permutation \( \pi \) has \( k \) cycles of length \( l_1, l_2, \dots, l_k \),

Define monomial: \( M_n(x_1, x_2, \dots, x_n) = \prod\limits_{i=1}^k x_{l_i} \)

Cycle index: \( P_G(x_1, x_2, \dots, x_m) = \dfrac{1}{\vert G \vert} \sum\limits_{\pi \in G} M_{\pi}(x_1, x_2, \dots, x_n) \)

Burnside's Lemma: \[ \vert X/G \vert = P_G(m, m, \dots, m) = \dfrac{1}{\vert G \vert} \sum\limits_{\pi \in G} M_{\pi}(m, m, \dots, m) \]

Polya's Enumeration Formula: \[ F_G(y_1, y_2, \dots, y_m) = P_G \left( \sum_{i=1}^m y_i, \sum_{i=1}^m y_i^2, \dots, \sum_{i=1}^m y_i^n \right) \]

5. Cayley's Formula

Counting Trees

How many different trees can be formed from \( n \) distinct trees?

Cayley's Formula: there are \( n^{n-2} \) trees on \( n \) distinct vertices.

Prufer Code

By removing a leaf from a tree \( T \), \( T' \) is still a tree.

Repeatedly remove \( u_i \) from tree \( T_i \) to get \( T_{i+1} \), where \( u_i \) is the smallest leaf in \( T_i \). \( u_i \) has only one edge \( (u_i, v_i) \), we get Prufer code for \( T \) with all \( v_i \)s.

2       5
|      /
4--3--1
   |   \
   6    7

u: 2,4,5,6,3,1
v: 4,3,1,3,1,7

E.g. the tree above has prufer code \( (4,3,1,3,1,7) \).

For each vertex \( v \) in \( T \):

  • # of occurrences in \( u_1, \dots, u_{n-1} \) and \( v_{n-1} \) is \( 1 \),
  • # of occurrences in edges \( (u_i, v_i) \) id \( \deg v \),
  • # of occurrences in \( v_1, \dots, v_{n-2} \) is \( \deg v - 1 \).

For each \( i \), the edge \( (u_i, v_i) \) can be determined because \( u_i \) is the smallest number not in \( \lbrace u_1, \dots, u_{i-1} \rbrace \cup \lbrace v_i, \dots, v_{n-1} \rbrace \).

Since the last digit of Prufer code must be \( n \), there are \( n^{n-2} \) Prufer code of \( n \) elements.

Each Prufer code is decodable to a tree, thus there are \( n^{n-2} \) trees on \( n \) distinct vertices.

Double Counting

What is the # of sequences of adding directed edges to an empty graph to form a rooted tree?

From a tree:

  • pick a root (\( n \) vertices)
  • pick an order of edges (\( n-1 \) edges in total)

# of sequences are \( T_n \times n \times (n-1)! = n!T_n \)

From an empty graph (all nodes are isolated):

  • add edges one by one, each edge eliminates a tree
  • after adding \( k \) edges, there are \( n-k \) isolated trees remaining
  • when adding the next edge, choose any vertex and the root of another tree: \( n \times (n-k-1) \) methods

Therefore, we have

\[ n!T_n = \prod_{k=0}^{n-2} n(n-k-1) = n^{n-2}n! \]

Thus we reach \( T_n = n^{n-2} \) again.

Graph Laplacian

Define adjacency matrix \( A \), where

\[ A(i,j) = \begin{cases} 1, & (i,j) \in E, \\ 0, & (i, j) \notin E. \end{cases} \]

and diagonal matrix \( D \), where

\[ D(i,j) = \begin{cases} \deg i, & i = j, \\ 0, & i \neq j. \end{cases} \]

then we define graph Laplacian \( L \) as \( L = D - A \).

\( L \) can be also defined as

\[ L(i,j) = \begin{cases} \deg i, & i = j, \\ -1, & i \neq j \wedge (i, j) \in E, \\ 0, & \text{otherwise}. \end{cases} \]

Krichhoff's Matrix-Tree Theorem

Define \( L_{i,i} \) as the submatrix of \( L \) obtained by removing the \( i \)-th row and \( i \)-th column.

Denote \( t(G) \) as the number of spanning trees in \( G \).

Krichhoff's Matrix-Tree Theorem: \[ \forall i, t(G) = \det(L_{i,i}) \]

Cauchy-Binet Theorem: \[ \det(AB) = \sum_{S \in {[m] \choose n}} \det(A_{[n],S}) \det(B_{S,[n]}) \]

For all \( n \)-vertex trees: they are spanning trees of \( K_n \), thus

\( L_{i,i} = \begin{bmatrix} n-1 & -1 & \dots & -1 \\ -1 & n-1 & \dots -1 \\ \vdots & \vdots & \ddots & \vdots \\ -1 & -1 & \dots & n-1 \end{bmatrix} \)

thus we obtain Cayley Formula: \[ T_n = t(K_n) = \det(L_{i,i}) = n^{n-2}. \]

6. Existence Problems

\( \def\blue{\color{blue}} \) \( \def\red{\color{red}} \) \( \def\green{\color{green}} \)

Circuit Complexity

Gates: \( \wedge \), \( \vee \) and \( \neg \).

The complexity is defined by # of gates.

Theorem (Shannon 1949): There is a boolean function \( f: \lbrace 0, 1 \rbrace^n \rightarrow \lbrace 0, 1 \rbrace \) which cannot be computed by any circuit with \( \dfrac{2^n}{3n} \) gates.

Double Counting

  • A party of \( n \) guests, the # of guests who shake hands an odd number of times is even.
  • The sum of degrees in a graph is twice the # of edges.
  • Corollary: # of odd-degree vertices is even.

Sperner's Lemma

Divide a line \( {\blue a}{\red b} \) into small segments, color each end point red or blue.

If \( a \) and \( b \) have different color, then there exists a small segment with different colors on two ends.

Divide a triangle \( {\blue a}{\red b}{\green c} \) into small triangles (triangulation) and color each node red, blue or green (each triangle is 3-colored, each line is 2-colored).

Sperner's Lemma (1928): For all properly colored triangulation of a triangle, there exists a tricolored small triangle.

Consider a dual graph, where

  • each triangle is a vertex, as well as the outer-space
  • add an edge if two triangles share a blue-red edge

Degree of triangle nodes:

  • \( {\red R}{\green G}{\blue B} \): \( 1 \)
  • \( {\red R}{\blue B}{\blue B} \) and \( {\red R}{\blue B}{\blue B} \): \( 2 \)
  • other cases: 0

The degree of the outer-space node is odd (because \( {\blue a}{\red b} \) has different colors, there are odd number of segments with different colors).

According to handshaking lemma, the # of odd-degree vertices is even, therefore # of \( {\red R}{\green G}{\blue B} \) triangles must be even.

Pigeonhole Principle

If \( > mn \) objects are partitioned into \( n \) classes, then some class receives \( > m \) objects.

Dirichlet's Approximation

Theorem (Dirichlet 1879): Let \( x \) be a irrational number. For any natural number \( n \), there is a rational number \( \frac{p}{q} \) such that \( 1 \leqslant q \leqslant n \) and \[ \left\vert x - \dfrac{p}{q} \right\vert < \dfrac{1}{nq} \]

  • fractional part: \( \lbrace x \rbrace = x - \lfloor x \rfloor \)
  • \( (n+1) \) pigeons: \( \lbrace kx \rbrace \) for \( k = 1, \dots, n+1 \)
  • \( n \) holes: \( \left(0, \dfrac{1}{n}\right), \left(\dfrac{1}{n}, \dfrac{2}{n}\right), \dots, \left(\dfrac{n-1}{n}, 1\right) \)

There exists \( \lbrace ax \rbrace \) and \( \lbrace bx \rbrace \) in the same hole, therefore

\[ \vert (a-b) x - (\lfloor ax \rfloor - \lfloor bx \rfloor) \vert = \vert \lbrace ax \rbrace - \lbrace bx \rbrace \vert < \dfrac{1}{n} \]

Let \( q = a-b \), \( p = \lfloor ax \rfloor - \lfloor bx \rfloor \), we have

\[ |qx-p| < \dfrac{1}{n} \Leftrightarrow \left\vert x - \dfrac{p}{q} \right\vert < \dfrac{1}{nq} \]

Other Existence Problems

  • forall \( S \subseteq [2n] \) that \( |S| > n \), there exists \( a, b \in S \) such that \( a \vert b \)
    • consider sets of \( 2^km \) for different \( k \)
  • a sequence of \( > mn \) different numbers must contain either an increasing subsequence of length \( m+1 \), or a decreasing subsequence of length \( n+1 \) (Erdos-Szekeres 1935)
    • define \( x_i \) and \( y_i \) as the length of longest increasing/decreasing subsequence ending/starting at \( a_i \)
    • \( (x_i, y_i) \neq (x_j, y_j) \) if \( i \neq j \) (why?)
    • \( >mn \) pigeons, no way to put them into \( mn \) holes

7. The Probabilistic Method

Tournament

tournament

\( T(V,E) \): \( n \) players, each pair has a match, \( u \) points to \( v \) if and only if \( u \) beats \( v \).

\( k \)-paradoxical: For every \( k \)-subset \( S \) of \( V \), there is a player in \( V \setminus S \) who beats all players in \( S \).

Theorem (Erdős 1963): If \( {n \choose k} \left( 1 - 2^{-k} \right)^{n-k} < 1 \) then there is a \( k \)-paradoxical tournament of \( n \) players.

Proof: Pick a random tournament \( T \) on \( n \) players \( [n] \). (Random \( \rightarrow \) each player beat the other by probability \( 1 / 2 \)). For any \( S \in {[n] \choose k} \), define event \( A_S \) as no player in \( V \setminus S \) beat all players in \( S \).

\[ Pr[u \in S, \text{ beaten}] = 1 - (1 / 2)^k \]

\[ Pr[A_S] = \left( 1 - 2^{-k} \right)^{n-k} \]

\( \)Pr[\text{No \( k \)-paradoxical}] \leqslant \sum_{S \in {[n] \choose k}} Pr[A_S] < 1.\( \)

The Probabilistic Method

  • Pick random bal from a box, \( Pr[\text{is blue}] > 0 \Rightarrow \) there is a blue ball.
  • Define a probability space \( \Omega \), and a property \( P \): \[ \underset{x}{Pr}[P(x)] > 0 \] \( \Rightarrow \exists x \in \Omega \) with the property \( P \).

Averaging Principle

  • Average height of the students in class is \( l \). \( \Rightarrow \) there is a student of height \( \geqslant l (\leqslant l) \).
  • For a random variable \( X \),
    • \( \exists x \leqslant E[X] \), such that \( X = x \) is possible,
    • \( \exists x \geqslant E[X] \), such that \( X = x \) is possible.

Hamiltonian Path in Tournament

Hamiltonian path: a path visiting every vertex exactly once.

Theorem (Szele 1943): There is a tournament on \( n \) players with at least \( n! 2^{-(n-1)} \) Hamiltonian paths.

Proof Pick a random tournament \( T \) on \( n \) players \( [n] \). For every permutation \( \pi \) of \( [n] \), define \[ X_\pi = \begin{cases} 1, & \pi \text{ is a Hamiltonian path}, \\ 0, & \text{otherwise}.\end{cases} \]

\[ E[X_\pi] = Pr[X_\pi = 1] = (1 / 2)^{n-1} \]

\[ E[X] = \sum_\pi E[X_\pi] = n! 2^{-(n-1)} \]

Large Independent Set

An independent set \( S \): no adjacent vertices in \( S \).

Max independent set is NP-hard.

A uniform \( S \) is very unlikely to be an independent set!

Theorem Graph \( G \) has \( n \) vertices and \( m \) edges, then there exists an independent set \( S \) of size \( \dfrac{n^2}{4m} \).

Proof

  1. Sample a random \( S \): each vertex is chosen independently with probability \( p \)
  2. modify \( S \) to \( S^* \) (an independent set): \( \forall uv \in E \), if \( u, v \in S \), then delete one of \( u \), \( v \) from \( S \).

Define \( Y \): # of edges in \( S \), we have

\[ Y = \sum_{uv \in E} Y_{uv}, \ \ \ Y_{uv} = \begin{cases}1, & u, v \in S, \\ 0, &\text{otherwise}.\end{cases} \]

\[ E[\vert S \vert] = np, \ \ \ E[Y] = \sum_{uv \in E} E[Y_{uv}] = mp^2 \]

\[ E[\vert S^* \vert] \geqslant E[\vert S \vert] - E[Y] = np - mp^2 \]

Let \( p = \dfrac{n}{2m} \), we have \( E[\vert S^* \vert] \geqslant \dfrac{n^2}{4m} \).

\( \dfrac{n^2}{4m} = \dfrac{n}{2d} \), where \( d = \dfrac{2m}{n} \) is the average degree.

Markov's Inequality

For non-negative \( X \), for any \( t > 0 \), \[ Pr[X \geqslant t] \leqslant \dfrac{E[X]}{t}. \]

Proof Define \( Y \) as

\[ Y = \begin{cases}1, & X \geqslant t, \\ 0, & \text{otherwise}. \end{cases} \]

\[ Y \leqslant \lfloor \dfrac{X}{t} \rfloor \leqslant \dfrac{X}{t}, \]

\[ Pr[X \geqslant t] = E[Y] \leqslant E\left[ \dfrac{X}{t} \right] = \dfrac{E[X]}{t}. \]

Chromatic Number

Graph \( G(V,E) \), define

  • girth \( g(G) \): length of the shortest circle,
  • chromatic number \( \chi(G) \): mnimum number of color to properly color the vertices of \( G \).

Intuition: large cycles are easy to color.

Theorem (Erdős 1959) For all \( k \), \( l \), there exists a finite graph \( G \) with \( \chi(G) \geqslant k \) and \( g(G) \geqslant l \).

Define independence number \( \alpha(G) \): size of the largest independent set in \( G \).

\[ \text{if } \alpha(G) \leqslant \dfrac{n}{k}, \]

\[ \text{then } \chi(G) \geqslant \dfrac{n}{\alpha(G)} \geqslant k. \]

Theorem' For all \( k \), \( l \), there exists a finite graph \( G \) with \( \alpha(G) \leqslant k \) and \( g(G) \geqslant l \).

Define a random graph of \( \vert V \vert = n \) vertices \( G(n, p) \): forall \( u, v \in V \), \( Pr[{u, v} \in E] = p \) (independently).

A uniform random graph: \( G(n, \dfrac{1}{2}) \).

Plan: fix any large \( k \), \( l \), exists \( n \), generate a random graph \( G \sim G(n, p) \) and

\[ \begin{cases}Pr[\alpha(G) > n / k] < 1 / 2, \\ Pr[g(G) < l] < 1 / 2. \end{cases} \]

9. Extremal Set Theory

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)| \]

10. Ramsey Theory

  • In any party of six people, either at least three of them are mutual strangers or at least three of them are mutual acquaintances.
  • Color edges of \( K_6 \) with 2 colors, there must be monochromatic \( K_3 \).

Define \( R(k, l) \) as the smallest integer satisfying: if \( n \geqslant R(k, l) \), for any 2-coloring of \( K_n \) there exists a red \( K_k \) or a blue \( K_l \).

Ramsey Theorem

Ramsey Theorem: \( R(k, l) \) is finite.

  • \( R(3, 3) = 6 \)
  • \( R(k, 2) = k, R(2, l) = l \) (why?)
  • \( R(k, l) \leqslant R(k, l-1) + R(k-1, l) \) (why?)

Take \( n = R(k, l-1) + R(k-1, l) \) and an arbitrary node \( v \), split \( n-1 \) nodes into two sets \( S \) and \( T \), where edges between \( v \) and \( S \) are blue, edges between \( v \) and \( T \) are red. Then discuss on the size of \( |S| \) and \( |T| \):

  • \( |S| \geqslant R(k, l-1) \): either \( K_k \subseteq S \) or \( K_{l-1} \subseteq S \), in the latter case \( K_l \subseteq S \cup \lbrace v \rbrace \).
  • \( |T| \geqslant R(k-1, l) \): either \( K_{k-1} \subseteq T \) or \( K_l \subseteq T \), in the former case \( K_k \subseteq T \cup \lbrace v \rbrace \).

Upper Bound

By induction using \( R(k,l) \leqslant R(k,l-1) + R(k-1,l) \), we can conclude that \[ R(k,l) \leqslant {k+l-2 \choose k-1} \]

therefore \( R(k,l) \) is finite and we complete the proof of Ramsey Theorem.

Lower Bound

For a uniformly and independently random 2-coloring of \( K_n \), each edge is red/blue with probability \( 1 / 2 \).

Associate each \( k \)-size subset of \( [n] \) \( S \) with an event \( A_S \) defined as \( S \) is a monochromatic \( K_k \), we know that \[ Pr[A_S] = \dfrac{2}{2^{{k \choose 2}}} = 2^{1-{k \choose 2}} \]

For any subset \( S \) and \( T \), \( A_S \) and \( A_T \) are dependent if \( |S \cap T| \geqslant 2 \). Therefore the max degree in the dependency graph is (choose the \( 2 \) nodes in both sets first and choose other \( k-2 \) nodes) \[ d \leqslant {k \choose 2}{n-2 \choose k-2} \leqslant {k \choose 2}{n \choose k-2} \]

For some \( n = ck2^{k / 2} \) with constant \( c \), \[ e 2^{1-{k \choose 2}} (d+1) \leqslant 1 \]

and by Lovasz Local Lemma, \( Pr\left[ \bigwedge\limits_{S \in {[n] \choose k}} \overline{A_S} \right] > 0 \), thus we know that \[ R(k,k) \geqslant n = \Omega(k 2^{k / 2}) \]

\[ \Omega(k 2^{k / 2}) \leqslant R(k, k) \leqslant {2k-2 \choose k-1} = O \left( \dfrac{4^k}{\sqrt{k}} \right) \]

Multicolor

Similarly, define \( R(r; k_1, k_2, \dots, k_r) \): if \( n \geqslant R(r; k_1, k_2, \dots, k_r) \), for any \( r \)-coloring of \( K_n \), there exists a monochromatic \( k_i \)-clique with color \( i \).

The mixing color trick:

\[ R(r; k_1, \dots, k_{r-2}, k_{r-1}, k_r) \leqslant R(r-1; k_1, \dots, k_{r-2}, R(2; k_{r-1}, k_r)) \]

Ramsey Theorem: \( R(r; k_1, k_2, \dots, k_r) \) is finite.

Hypergraph

If \( n \geqslant R_t(r; k_1, k_2, \dots, k_r) \), then for any \( r \)-coloring of \( {[n] \choose t} \) there exists a monochromatic \( {S \choose t} \) with color \( i \) and \( |S| = k_i \) for smoe \( i \).

A complete \( t \)-uniform hypergraph \( {[n] \choose t} \)

\( r \)-coloring function \( f: {[n] \choose t} \rightarrow \lbrace 1, 2, \dots, r \rbrace \)

Partition of Set Family

If \( n \geqslant R_t(r; k_1, k_2, \dots, k_r) \), then for any \( r \)-partition of \( {[n] \choose t} = C_1 \cup \dots \cup C_r \), there exists an \( S \subseteq [n] \) such that \( |S| = k_i \) and \( {S \choose t} \subseteq C_i \) for some \( i \).

Erdos-Rado partition arrow \( n \rightarrow (k_1, k_2, \dots, k_r)^t \)

Theorem by Ramsey:

  • \( R_t(r; k_1, k_2, \dots, k_r) \) is finite.
  • \( R_t(r; k) \overset{\Delta}{=} R_t(r; k, \dots, k) \) is finite.

Happy Ending Problem

Any 5 points in the plane with no three on a line, has a subset of 4 points that form a convex quadrilateral.

Theorem (Erdos-Szekeres 1935): \( \forall m \geqslant 3 \), \( \exists N(m) \) such that any set of \( n \geqslant N(m) \) points in the plane with no three on a line, contains \( m \) points that are the vertices of a convex \( m \)-gon. (凸\( m \)边形)

A convex polygon:

  • The line between any two nodes in the polygon is completely in the polygon.
  • No vertice is covered by the triangles formed by other three vertices.

Result: \( N(m) = R_3(2; m, m) \) (why?)

For any set of points in the plane with no 3 on a line, denoted as \( X \), \( |X| \geqslant N(m) \). For all \( f: {X \choose 3} \rightarrow \lbrace 0, 1 \rbrace \), \( \exists S \subseteq X \), \( |S| = m \) that there is a monochromatic \( {S \choose 3} \).

We claim that \( S \) is a convex \( m \)-gon. (why?) For all \( a, b, c \in X \), define \( \Delta_{abc} \) as the # of points in triangle \( abc \). \[ f(\lbrace a, b, c \rbrace) = |\Delta_{abc}| \bmod 2 \]

In this case, if there is point \( d \) in triangle \( abc \), then we have \[ f(abc) = f(abd) + f(acd) + f(bcd) + 1 \] which is impossible because \( {S \choose 3} \) cannot be monochromatic if this equation holds.

Data Structures

  • Data universe \( [N] \)
  • Key \( x \in [N] \)
  • Data set \( S \in {[N] \choose n} \)

Problem: is \( x \in S \)?

Solution: sorted table as data structure

Complexity: \( \geqslant \log_2 n \) memory accesses in the worst case

Theorem (Yao 1981): If \( N \geqslant 2n \), on sorted table, any search algorithm requires \( \Omega(\log n) \) accesses in the worst-case.

Proof by induction on \( n \) using equation (具体看讲义) \[ 1 + \log \dfrac{n}{2} = \log n \]

期末复习

1 - 基本计数

balls per binany\( \leqslant 1 \)\( \geqslant 1 \)
\( n \) distinct balls, \( m \) distinct bins\( m^n \)\( (m)_n \)\( m!{n \brace m} \)
\( n \) identical balls, \( m \) distinct bins\( \left({m \choose n}\right) \)\( {m \choose n} \)\( {n-1 \choose m-1} \)
\( n \) distinct balls, \( m \) identical bins\( \sum\limits_{k=1}^{m} {n \brace k} \)\( \begin{cases}1 \text{ if } n \leqslant m \\ 0 \text{ if } n > m\end{cases} \)\( {n \brace m} \)
\( n \) identical balls, \( m \) identical bins\( \sum\limits_{k=1}^m p_k(n) \)\( \begin{cases}1 \text{ if } n \leqslant m \\ 0 \text{ if } n > m\end{cases} \)\( p_m(n) \)

其中:

  • 二项式系数 \[ {n \choose k} = \dfrac{n!}{k!(n-k)!} \]
  • \( n \)个不同的篮子放\( k \)个不同的球,每个篮子最多一个(单射、\( n \)的\( k \)个元素的排列): \[ (n)_k = \begin{cases} \dfrac{n!}{(n-k)!} & k \leqslant n, \\ 0, & k > n. \end{cases} \]
  • \( n \)个不同的篮子放\( k \)个相同的球(\( n \)大小集合的\( k \)-multiset,一个球代表对应的元素出现一次;插板法): \[ \left({n \choose k}\right) = {n+k-1 \choose n-1} = {n+k-1 \choose k} \]
  • \( n \)个相同的篮子放\( k \)个不同的球,每个篮子至少一个球(集合划分成恰好\( k \)份,考虑最后一个元素加入前\( k \)个子集或者单独成一个子集): \[ {n \brace m} = k{n-1 \brace k} + {n-1 \brace k-1} \]
  • \( n \)个相同的篮子放\( k \)个相同的球,每个篮子至少一个球(整数划分成恰好\( k \)份):
    • \( p_k(n) = p_{k-1}(n-1) + p_k(n-k) \)(考虑所有项都大于1或者把1去掉)
    • \( p_k(n) = \sum\limits_{j=1}^k p_j(n-k) \)(把整数\( n \)划分成\( k \)份等价于划分成若干份,其中最大值为\( k \))

2 - 生成函数

普通生成函数:\( G(x) = \sum\limits_{n \geqslant 0} a_n x^n \)

求解生成函数的四步方法:

  • 写出\( a_n \)的递归定义(如\( a_n = a_{n-1} + a_{n-2} \))
  • 两边同时乘以\( x^n \),左边即为生成函数\( G(x) \),并将右边化为\( G(x) \)的形式
  • 求解\( G(x) \),得到关于\( x \)的函数
  • 对\( G(x) \)进行级数展开,得到\( a_n \)
    • 泰勒展开:\( G(x) = \sum\limits_{n \geqslant 0} \dfrac{G^{(n)}(0)}{n!} x^n \)
    • 几何级数展开:\( \dfrac{1}{1-z} = \sum\limits_{n \geqslant 0} z^n \)
    • Newton's Formula:\( (1+x)^\alpha = \sum\limits_{n \geqslant 0} {\alpha \choose n} x^n \)

常见的生成函数操作:

  • shift:\( x^kG(x) = \sum\limits_{n \geqslant k} g_{n-k} x^n \)
  • addition:\( F(x) + G(x) = \sum\limits_{n \geqslant 0} (f_n + g_n) x^n \)
  • convolution:\( F(x)G(x) = \sum\limits_{n \geqslant 0} \sum\limits_{n=0}^k f_k g_{n-k} x^n \)
  • differentiation:\( G'(x) = \sum\limits_{n \geqslant 0} (n+1) g_{n+1} x^n \)

卡特兰数:\( C_0 = 1 \),\( C_n = \sum\limits_{k=0}^{n-1}C_k C_{n-1-k} = \dfrac{1}{n+1} {2n \choose n} \)

3 - 筛法

集合求并:\( \left\vert \bigcup\limits_{i=1}^n A_i \right\vert = \sum\limits_{I \subseteq [n]} (-1)^{|I|-1} \left\vert \bigcap\limits_{i \in I} A_i \right\vert \)

记\( S_k = \sum\limits_{|I|=k} |A_I| \),则有

\[ |A_1 \cup \dots \cup A_2| = - S_0 + S_1 - S_2 + S_3 + \dots + (-1)^{n-1} S_n \] \[ |\bar{A_1} \cap \dots \cap \bar{A_2}| = S_0 - S_1 + S_2 - S_3 + \dots + (-1)^{n} S_n \]

\( [n] \)到\( [m] \)的满射的数量:

  • 定义坏事件\( A_i \)为\( [m] \)中的\( i \)不在值域中,有\( |A_i| = (m-1)^{n} \)个映射满足条件,
  • 定义坏事件\( A_I \)为\( [m] \)中的子集\( I \)不在值域中,\( |A_i| = (m-|I|)^{n} \),
  • 带入筛法得到满射的数量是\( \sum\limits_{k=1}^m (-1)^{m-k} {m \choose k} k^n \)。

进而得到推论

\[ {n \brace m} = \dfrac{1}{m!}\sum\limits_{k=1}^m (-1)^{m-k} {m \choose k} k^n \]

错排问题:

  • 定义坏事件\( A_I \)为在新排列中\( I \)中元素的位置没变,有\( (n-|I|)! \)种排列
  • 带入求得错排的个数约为\( \dfrac{n!}{e} \)

有限制位置条件的排列:

  • 将排列转换为一组二维坐标
  • 假设\( B \)是一个不符合条件的位置的集合
  • \( r_k \)表示在\( B \)中选\( k \)个不同的位置的方法
  • 则满足条件的\( n \)排列的个数为\( N_0 = \sum\limits_{k=0}^n (-1)^k r_k (n-k)! \)

莫比乌斯反演:作业没做到,先不复习

Polya计数法不考

5 - Cayley公式

\( n \)个不同的点组成的树的个数为\( n^{n-2} \)。

Repeatedly remove \( u_i \) from tree \( T_i \) to get \( T_{i+1} \), where \( u_i \) is the smallest leaf in \( T_i \). \( u_i \) has only one edge \( (u_i, v_i) \), we get Prufer code for \( T \) with all \( v_i \)s.

2       5
|      /
4--3--1
   |   \
   6    7

u: 2,4,5,6,3,1
v: 4,3,1,3,1,7

E.g. the tree above has prufer code \( (4,3,1,3,1,7) \).

For each \( i \), the edge \( (u_i, v_i) \) can be determined because \( u_i \) is the smallest number not in \( \lbrace u_1, \dots, u_{i-1} \rbrace \cup \lbrace v_i, \dots, v_{n-1} \rbrace \).

用到的思想:

  • 双重计数(数两遍)
  • 编码与解码(将一棵树转换为一个编码)
  • 构造双射求出个数

6 - 存在性问题

鸽笼原理:将\( mn \)个物体分到\( n \)个类别中,有些类别有多于\( m \)个物体。

  • 组合中存在两个数可以互相整除(考虑2的幂次)
  • 单调增/减序列(将最长增/减序列的长度转换为二维坐标)
  • Dirichlet's approximation:将\( [0, 1] \)划分为\( n \)个区间,填入\( n+1 \)个数

7 - 概率法

Theorem: Let \( G(V, E) \) be a graph on \( n \) vertices with \( m \) edges. Then \( G \) has an independent set with at least \( \dfrac{n^2}{4m} \) vertices.

证明某些事件都(不)发生的概率\( > 0 \),从而证明存在。

  • 设计事件
    • 边的方向以\( 1 / 2 \)的概率随机
    • 点/边以\( p \)为概率被选入集合中(此后求解使期望最小/大的\( p \)值)
  • 求解概率
    • 直接计算概率,可能会用到\( (1-p)^x = e^{-px} \)
    • 利用\( E \left[ \sum\limits_{i=1}^n a_i X_i \right] = \sum\limits_{i=1}^n a_i \cdot E[X_i] \)求随机变量的期望

Lovasz Local Lemma:

  • 条件1:对任意的\( i \),\( Pr[A_i] \leqslant p \)
  • 条件2:事件的依赖图中的最大度数为\( p \),且\( ep(d+1) \leqslant 1 \)
  • 则\( Pr\left[ \bigwedge\limits_{i=1}^n \bar{A_i} \right] > 0 \)

8 - 极值图论

Mantel's Theorem: Suppose \( G(V, E) \) is a graph on \( n \) vertices without triangles, then \( |E| \leqslant \dfrac{n^2}{4} \).

Turan's Theorem: Let \( G(V, E) \) be a graph with \( |V| = n \). If \( G \) has no \( r \)-clique, \( r \geqslant 2 \), then \( |E| \leqslant \dfrac{r-2}{2(r-1)} n^2 \).

9 - 极值集合论

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 \).

Erdos-Ko-Rado Theorem:

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

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

\[ |\mathcal{F}| \leqslant {n \choose \lfloor n/2 \rfloor}. \]

10 - Ramsey理论

Define \( R(k, l) \) as the smallest integer satisfying: if \( n \geqslant R(k, l) \), for any 2-coloring of \( K_n \) there exists a red \( K_k \) or a blue \( K_l \).

Ramsey Theorem:

  • \( R(k, l) \) is finite.
  • \( R(r; k_1, k_2, \dots, k_r) \) is finite.
  • \( R_t(r; k_1, k_2, \dots, k_r) \) is finite.
  • \( R_t(r; k) \overset{\Delta}{=} R_t(r; k, \dots, k) \) is finite.

Theorem (Erdos-Szekeres 1935): \( \forall m \geqslant 3 \), \( \exists N(m) \) such that any set of \( n \geqslant N(m) \) points in the plane with no three on a line, contains \( m \) points that are the vertices of a convex \( m \)-gon. (凸\( m \)边形)

\[ N(m) = R_3(2; m, m) \]

11 - 匹配论

System of distince representatives (SDR) for a sequence of sets \( S_1, S_2, \dots, S_m \) is a sequence of distince elements \( x_1, x_2, \dots, x_m \) such that \( x_i \in S_i \).

Hall's Theorem: The sets \( S_1, S_2, \dots, S_m \) have a system of distince representatives (SDR) if and only if \( \left\vert \bigcup\limits_{i \in I} S_i \right\vert \geqslant |I| \) for all \( I \subseteq [m] \).

The condition \( \left\vert \bigcup\limits_{i \in I} S_i \right\vert \geqslant |I| \) is called the Hall's condition.