Ramsey Theory

Definition 4.1   A subset $S\subset G$ is product-free if it contains no solutions to $xy=z$. It is triangle-free if it contains no solution to $xyz=1$, with $x,y,z$ not all the same. Let $\alpha(G)$ be the size of the largest triangle-free subset of $G$. Let $\widetilde\alpha(G)=\frac{\alpha(G)}{\vert G\vert}$.

We showed that for abelian groups we could find a product-free subset of size $\frac{2}{7}\vert G\vert$. We cannot achieve such a constant fraction in a triangle-free subset. That is, there exists a sequence of groups such that $\widetilde\alpha(G)\to 0$, but the instructor can only show that it goes to 0 very slowly.

The sequence of groups $G_k={\mathbb{Z}}_3^k$ model higher-dimensional versions of the Set game. $\alpha(G_k)$ is the number of cards that can contain no Set.

Conjecture 4.2   $L=3$.

Theorem 4.3 (van der Waerden)   For all $k$ and $r$, if we color the natural numbers with $r$ colors, we can find a monochromatic arithmetic progression of $k$ terms.

Theorem 4.4 (Szemerédi, 1974)   For all $k,\varepsilon$, there exists $N$ such that for any $S\subset[N]$ with $\vert S\vert\ge\varepsilon N$, $S$ contains a $k$-term arithmetic progression.

This theorem, conjectured by Erdos-Turán and sometimes called the ``density version of van der Waerden's theorem'' was proved by Szemerédi using a Ramsey-type theorem for graphs (The Szemerédi Lemma). A noteworthy later proof due to Furstenberg uses a fixed-point theorem and ergodic theory.

Definition 4.5   An ordered collection of $t$ elements $x_1,\ldots,x_t$ of $[t]^N$ is a combinatorial line if for each of the $N$ coordinates, the $t$ elements all have the same value $x_{1i}=x_{2i}=\ldots=x_{ti}$ or $x_{ji}=j$ for all $j$.

Theorem 4.6 (Hales-Jewett)   For all $t$ and $r$, there exists $N$ sucht if we color $[t]^N$ by $r$ colors, there exists a monochromatic combinatorial line.

This is called the ``combinatorial essence'' of van der Waerden's theorem. Also, there are two more parameters: it should be that we color the $a$-dimensional spaces and fine a $b$-dimensional space, all of whose $a$-dimensional subspaces are the same color.