Theorem $$ \text{For every } k \in \mathbb{N}, \text{we have } R(k)\ge 2^{k/2} $$Before we start the proof, let’s look at 3 ingredients we need: The probabilistic method The union bound The binomial estimate The probabilistic method Let $\Omega$ be the set of all possible outcomes of an experiment. Suppose that each outcome is equally likely. Let $A \subseteq \Omega$ be an event. $$ \text{If } \operatorname{Prob}(A) < 1 \text{, then } \operatorname{Prob}(A^c) > 0 $$Union Bound Let $\Omega$ be the set of all possible outcome of an experiment. Suppose that each outcome is equally likely. Let $A_1, \ldots, A_t \subseteq \Omega$ be some events. Then: ...

General Ramsey on normal graph Notation General notation for Ramsey theory: $K_n \to (K_s,K_t)$ is the assertion that for any coloring of the edges of $K_n$ with red and blue, we can always find a red $K_s$ or a blue $K_t$. $K_n \not \to (K_s,K_t)$ is the assertion that there exists a coloring of the edges of $K_n$ with red and blue with no red $K_s$ nor blue $K_t$. Notation Off-diagonal Ramsey numbers: ...

Erdos-Szekeres Theorem Given $r, s$ any sequence of distinct real numbers with length at least $(r-1)(s-1)+1$ contains a monotonically increasing subsequence of length $r$ or a monotonically decreasing subsequece of length $s$. That is, given the subsequence: $a_1, a_2, ..., a_{(s-1)(r-1)+1}$, we can find: Indicies $i_1 < i_2 < ...< i_r$ so that $a_{i1} < a_{i2} < ...< a_{ir}$ OR Indicies $j_1 < j_2 < ...< j_r$ so that $a_{j1} > a_{j2} > ... > a_{jr}$ Example: $s = 3, r = 3$, Sequence: $10, 11, 7, 8$ has no such property. ...

Permutation of Sets Definition permutation A permutation of a set $S$ can be thought of as a listing of the elements $S$ in some order. $P(n, r)$ denotes the number of $r$-permutations of an $n$-element set. Definition $r$-permutation An $r$-permutation of a set $S$ is a string $a_1, a_2, ... a_r$ where $a_i \in S, \forall i \in [r]$ and $a_i \neq a_j$ for $i \neq j$. Note: $[r] = {1, 2, ..., r}$ ...

Texture Synthesis & Hole Filling Texture Texture depicts spacially repeating patterns. Texture Synthesis Create new samples of a given texture. Many applications: virtual environments, hole-filling, texturing surfaces. The challenge: Need to model the whole spectrum: from repeated to stochastic texture. One idea: Compute statistics of input texture Generate a new texture that keeps those same statistics. But it is hard to model those probabilities distributions. Another idea: ==Efros & Leung algorithm== ...

Pigeonhole Principle If $n+1$ objects are distributed into $n$ boxes, then at least one box contains two or more of the objects. Proof For each $i\in \set{1, ..., n}$, let $a_i = $ number of objects in box $i$. Then, $a_1 + ... + a_n = n+1$ Let $a_j = \text{max } a_i$. Then, \begin{align*} n+1 &\leq n\cdot a_j \\ \frac{n+1}{n} &\leq a_j \\ 1 < \frac{n+1}{n} &\leq a_j\\ 1 &< a_j \end{align*} Note that this conclusion doesn’t hole if you have $n$ objects or less. ...

Binomial Coefficient and Binomial Identity Pascal’s Triangle \begin{matrix} {0 \choose 0}\\ {1 \choose 0} & {1 \choose 1}\\ {2 \choose 0} & {2 \choose 1} & {2 \choose 2}\\ {3 \choose 0} & {3 \choose 1} & {3 \choose 2} & {3 \choose 3}\\ {4 \choose 0} & {4 \choose 1} & {4 \choose 2} & {4 \choose 3} & {4 \choose 4}\\ .\\ .\\ . \end{matrix} Pascal’s Formula For all integers $n$ and $k$ with $1 \leq k \leq n - 1$, we have: ...

Definition A combination of a set $S$ is a term usually used to denote an unordered selection of the element of $S$. It is simply a selection of a subset of $S$. $r$-combination = $r$-subset. $n\choose r$ is the number of $r$-subset in the set of size $n$. Theorem For $0 \leq r \leq n$, we have: $$ P(n, r) = r! {n \choose r} \text{ and } {n \choose r} = \frac{n!}{r!(n-r)!} $$ Proof ...

Deterministic Finite Automaition Definition: $(Q, s, A, \delta)$ $Q$: A set of all the possible state. $s \in Q$ : starting state. The state to start the machine. $A \subseteq Q$: The set of states we accept. Return “good” when we end there. $\delta$: A function $Q \times \Sigma \rightarrow Q$. The set of all transition functions. There is an interesting DFA design question. The question is as follows: Given a bit-string (a string that contains only 0s and 1s), design a DFA that accepts the string if and only if the number represented by the string is divisible by 5. ...

Gomory’s Theorem If you move two cells of a $8 \times 8$ chessboard of opposite colors, the remaining cells can be fully domino tiled. Proof Draw a closed path that passes through every square exactly once. (Draw a big C and then draw back and forth horizontally) Choose the two cells to be removed, and the closed path we have will be sperated into two paths. If we lable the close path we chose in the beginning from 1 to 64 in the order we drew it, white cells have odd numbers, and black cells have even numbers (or reversed). ...