Discrete Math, 4th day, 6/24/04
REU 2004

Instructor: László Babai
Scribes: Eric Patterson and Travis Schedler

Definition 4.1   A graph $G$ is $k$-edge-connected between vertices $x$ and $y$ if there are $k$ edge-disjoint paths between $x$ and $y.$

Definition 4.2   A graph $G$ is $k$-vertex-connected between vertices $x$ and $y$ if there are $k$ vertex-disjoint paths between $x$ and $y.$

Suppose we found $57$-edge-disjoint paths between $x$ and $y,$ and we think $57$ is optimal. How can we demonstrate that $58$ such paths cannot be found?

Ben's Conjecture: If there are no more than $57$ edge-disjoint paths from $x$ to $y,$ then there is a partition $V=A\dot{\cup} B$ such that $x\in A,$ $y\in B,$ and the maximum number of edges between $A$ and $B$ is less than or equal to $57.$

Definition 4.3   An $\left(x,y\right)$-cut of a graph $G=\left(V,E\right)$ is a partition $V=A\dot{\cup} B$ such that $x\in A$ and $y\in B.$

Theorem 4.4 (Menger's Theorem)   The maximum number of edge-disjoint paths between $x$ and $y$ equals the minimum number of edges between the two parts of an $\left(x,y\right)$-cut.

Puzzles

Set Game. The Set game is played with a deck of cards. Each card has four properties with three possible values: a shape (oval,diamond,squiggle), a color (red, green, purple), a shading (blank, solid, shaded), and a number (1,2,3). Each card is distinct, so there are $3^4=81$ cards. Twelve cards are placed face up on a table. The objective is to find a ``set'' among the twelve cards. A ``set'' is formed by three cards so that each property is either the same on all cards or different on all cards. The first player to find a ``set'' gets that ``set,'' after which three new cards from the deck are placed face up to replace them. The player who finds the most ``sets'' wins.

We can generalize the Set game so that there are $n$ properties on each card, and each property has three possible values. In this $n$-dimensional Set game we have $3^n$ cards. We are interested in how many cards we can draw from the deck without finding a ``set.'' Let $\alpha(n)$ denote the maximum number.

Let $\mathbb{Z}_3$ be the set $\{0,1,2\}$ with addition mod $3,$ so $2+2=1$ for example. Let $\mathbb{Z}_3^n$ be the set $\{(x_1,\dots,x_n):\ x_i\in \mathbb{Z}_3\}.$ For $\underline{x}=(x_1,\dots,x_n)$ and $\underline{y}=(y_1,\dots,y_n)$ in $\mathbb{Z}_3^n,$ we define addition by $\underline{x}+\underline{y}=(x_1+y_1,\dots,x_n+y_n).$ In the Set game ($n=4$), the cards correspond to the quadruples in $\mathbb{Z}_3^4;$ for instance [oval, green, blank, 3] $\leftrightarrow \left[1,1,0,2\right].$

Observation 4.5   Three distinct elements $\underline{x}, \underline{y},\underline{z} \in \mathbb{Z}_3^4$ form a set if and only if $\underline{x}+\underline{y}+ \underline{z}=\underline{0}.$

Similarly, we can work in $\mathbb{Z}_3^n$ for the $n$-dimensional Set game. So an alternative definition for $\alpha(n)$ is the maximum number of elements of $\mathbb{Z}_3^n$ without a solution to $\underline{x}+\underline{y}+\underline{z}=\underline{0}$ where $\underline{x},\underline{y},\underline{z}$ are distinct.

Definition 4.6   A function $f:\mathbb{N} \to \mathbb{R}$ is supermultiplicative if $f(n+m)\geq f(n)\cdot f(m).$

Observe that $2^n \leq \alpha(n) \leq 3^n,$ so $2\leq L \leq 3$ by the previous two exercises, where $L=\lim_{n\to \infty}\sqrt[n]{\alpha(n)}.$

Conjecture 4.7 (Open Problem)   $\lim_{n\to \infty} \sqrt[n]{\alpha(n)}=3.$

Theorem 4.8 (Van der Waerden, 1928)   If we color the positive integers with $k$ colors, then for all $\ell$ there is an $\ell$-term arithmetic progression in one color.

Theorem 4.9 (Szemerédi, 1975)   For all $\epsilon > 0$ and $\ell,$ there is an $N$ such that if $A\subseteq \{1,\dots,N\}$ and $\vert A\vert\geq \epsilon N,$then $A$ contains an $\ell$-term arithmetic progression.

History:

• Erdos and Turán conjectured this result in 1936.
• In 1952, K. F. Roth found an analytic proof of the result for $\ell = 3.$ This result, in addition to another major result, were part of his Fields Medal citation in 1958.
• In the late 1960s, E. Szemerédi found a combinatorial proof for $\ell = 3.$
• Later, E. Szemerédi found a combinatorial proof for $\ell=4.$
• In 1975, E. Szemerédi found a combinatorial proof of the whole conjecture.
• Subsequently, Furstenberg found an analytic proof of Szemerédi's Theorem. His methods led to further generalizations. For example:

Theorem 4.10   $\alpha(n)=o(3^n).$

On April 8, 2004, a major breakthrough was announced in a very old problem that has fascinated mathematicians for ages:

Theorem 4.11 (Green-Tao, 2004)   For all $\ell,$ there is an $\ell$-term arithmetic progression among prime numbers.

Ben Green and Terence Tao announced this result in their paper ``The Primes Contain Arbitrarily Long Arithmetic Progressions.'' The proof uses Szemerédi's Theorem and the ideas of Furstenberg's proof. It is posted on arXiv.