组合数学

6 - Existence Problems

2019-10-23 14:00 CST
2020-01-02 00:52 CST
CC BY-NC 4.0

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