Unimodality of Binomial Coefficients and Sperner’s Theorem If we examine the binomial coefficients in a row of Pascal’s triangle, we notice that the numbers increase for a while and then decrease. A sequence of numbers with this property is called unimodal. Theorem Let $n$ be a positive integer. The sequence of binomial coefficients $$ {{n} \choose {0}}, {{n} \choose {1}}, \ldots, {{n} \choose {n}} $$ is a unimodal sequence. Mor precisely, $$ {{n} \choose {0}} < {{n} \choose {1}} < \ldots < {{n} \choose {\lfloor n/2\rfloor}} $$ and $$ {{n} \choose {\lceil n/2 \rceil}} > \ldots {{n} \choose {n-1}} > {{n} \choose {n}} $$...

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 $$...

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: $$ {n \choose k} = {{n-1} \choose k} + {{n-1} \choose {k-1}} $$...

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!...

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