Extremal Graph Theory

Notation

• We will denote a complete graph of order $a$ (also called $a$-clique) as $\mathbb K[a]$.
• Any general graph of order $a$ will be denoted by $\mathbb G[a]$.
• If a graph’s edges are monochromatic in color $c$, we denote it by $\mathbb G^c[a]$.
• If a graph’s vertices are monochromatic in color $c$, we denote it by $\mathbb G_c[a]$.
• the colored degree of a vertex is the number of edges of a particular color emerging out of that vertex. $\#c(v)$ denotes the number of $c$-colored edges emerging out of $v$.

---

1 - OG-Ramsey Theorem

let, $m,n \in \mathbb N$ and $m \ge n \geq 2$. Define $R(m,n)$ to be the smallest number $R$ for which any coloring of the edges of $\mathbb K[R]$ with the set $\{r,b\}$ (denoting red and blue), contains $\mathbb K^r[m]$ or $\mathbb K^b[n]$ .

Ramsey Theorem: $R(m,n)$ is finite, and is at most ${{n+m-2}\choose{m-1}}$.

Lemma 1.1: If $R(m+1,n) \leq {{n+m-1}\choose{m}}$, and $R(m,n+1) \leq {{n+m-1}\choose{m-1}}$, then ${R(m+1,n+1) \leq {{n+m}\choose{m}}}$.

Proof:

Suppose $R(m+1,n) \leq {{n+m-1}\choose{m}}$ and $R(m,n+1) \leq {{n+m-1}\choose{m-1}}$. we will show that ${R(m+1,n+1) \leq {{n+m}\choose{m}}}$. Indeed, ${{n+m}\choose{m}} = {{n+m-1}\choose{m-1}} + {{n+m-1}\choose{m}}$. So, construct an arbitrary coloring of $\mathbb K[{{n+m}\choose{m}}]$ with the set $\{r,b\}$.

First, suppose $\exists v^* \in \mathbb K[{{n+m}\choose{m}}]$ such that ${\#b(v^*) \ge {{n+m-1}\choose{m}}}$. then $v^*$ is adjacent to some $\mathbb K^*[{{n+m-1}\choose{m}}]$ via all blue edges. By our hypothesis, $\mathbb K^*[{{n+m-1}\choose{m}}]$ either contains $\mathbb K^r[m+1]$ (in which case we are done), or $\mathbb K^b[n]$ which forms a $\mathbb K^b[n+1]$ with $v^*$.

Otherwise, $\forall v \in \mathbb K[{{n+m}\choose{m}}]$, we have ${\#b(v) < {{n+m-1}\choose{m}}}$. Therefore, it must be the case that${{\#r(v) > {{n+m}\choose{m}}-{{n+m-1}\choose{m}}} - 1}$. Equivalently, ${\#r(v) \ge {{n+m-1}\choose{m-1}}}$. Hence any $v$ is adjacent to some $\mathbb K[{{n+m-1}\choose{m-1}}]$ via all red edges. By our hypothesis, $\mathbb K[{{n+m-1}\choose{m-1}}]$ either contains $\mathbb K^b[n+1]$ (in which case we are done), or $\mathbb K^r[m]$ which forms a $\mathbb K^r[m+1]$ with $v$. $\square$

Lemma 1.2: If $R(m,2) \leq {{m}\choose{m-1}} = m$, and $R(2,n) \leq {{n}\choose{1}} =n$. In particular $R(2,2) = 2.$

Proof:

Color $\mathbb K[m]$ with $\{r,b\}$. We either have a blue edge ($\mathbb K^b[2]$ ), or $\mathbb K^r[m]$ . Similarly, Color $\mathbb K[n]$ with $\{r,b\}$. We either have a red edge ($\mathbb K^r[2]$ ), or $\mathbb K^b[n]$ . $\square$

lemma 1.2 acts as the base case of the induction, with lemma 1.1 acting as the inductive step, which together prove Ramsey’s theorem.

---

Multicolor Ramsey Theorem

for $1\le i\le n$ , let $C = \{c_i\}$ be a color set, and $(a_i)$ be an $n$-tuple of natural numbers ($a_i\geq2)$.

denote $R(a_i)$ to be the smallest number $R$ for which in any coloring of the edges of $\mathbb K[R]$ with $C$, at least one of $\mathbb K^{c_i}[a_i]$ is in $\mathbb K[R]$.

Multicolor Ramsey Theorem: $R(a_i)$ is finite.

Proof: we induct on $n$ (the base case $n = 2$ is the Ramsey theorem). suppose for some $n$, $R(a_i)$ is finite. then, we claim that $R(a_1,a_2,...a_n,a_{n+1}) \leq R(R(a_i),a_{n+1})$ (which is itself a two color Ramsey number and hence finite).

let $C' =C \cup \{c_{n+1}\}$. construct an arbitrary coloring of the edges $\mathbb K[R(R(a_i),a_{n+1})]$ with the color set $C'$. Now, transform this coloring in the following way: whenever the color of an edge is in $C$, color it with a rouge color $c^*$ instead. now, in this Transformed coloring of $\mathbb K[R(R(a_i),a_{n+1})]$, there are only two colors, namely $c^*$ and $c_{n+1}$. if we find $\mathbb K^{c_{n+1}}[a_{n+1}]$, we are done. So, suppose we find $\mathbb K^{c^*}[R(a_i)]$. In that case, reverse the transformation such that all edges in $\mathbb K^{c^*}[R(a_i)]$ are colored as per the initial coloring with the color set $C$. By our induction hypothesis, $\mathbb K^{c^*}[R(a_i)]$ contains at least one of $\mathbb K^{c_i}[a_i]$. $\square$

Wikipedia has a funny proof about going color blind initially and then recovering our sight (and a better upper bound) of $R(a_1,a_2,...a_n,a_{n+1}) \leq R(R(a_1,a_2,..a_{n-1}),R(a_n,a_{n+1}))$.

(essentially repeat the same argument with any $c_i$- colored edge with $c^*$ if and only if $1\leq i \leq n-1$. and replaces any $c_n$ or $c_{n+1}$ - colored edge with $c^{**}$, hence$\mathbb K[R(R(a_1,a_2,..a_{n-1}),R(a_n,a_{n+1}))]$ either contains $\mathbb K^{c^*}[R(a_1,a_2,..a_{n-1})]$ or $\mathbb K^{c^{**}}[R(a_n,a_{n+1})]$).

---

Bounding the Monochromatic Triangle Number

let $n\geq 2$ define $\triangle(n) = R(3,3,.._{n\ times}, 3)$ that is, $\triangle(n)$ is the smallest number $R$ for which any coloring of the edges of $\mathbb K[R]$ with an $n$-set contains a monochromatic $\mathbb K[3]$.

Consider $\mathbb K[((n+1)\triangle(n)) + 2]$. Color it arbitrarily with an $n+1$ set. the degree of $v_0$ in this graph is $((n+1)\triangle(n)) + 1$. hence at least $\lfloor \triangle(n) + 1/(n+1)\rfloor = \triangle(n)$ edges out of $v_0$ are all colored $c^*$. hence, $v_0$ is adjacent to some $\mathbb K^*[\triangle(n)]$ via all $c^*$ edges. if some edge in $\mathbb K^*[\triangle(n)]$ is colored $c^*$, we have a monochromatic triangle $\mathbb K^{c^*}[3]$. Else, all edges of $\mathbb K^*[\triangle(n)]$ are colored with at most $n$ colors. hence for some color $c$, $\mathbb K^c[3]$ exists in $\mathbb K^*[\triangle(n)]$.

Hence we get the following bound: $\triangle(n+1) \leq (n+1)\triangle(n) + 2$. And $\triangle(2) = 6$.

by looking at the above relation, we could guess that $\triangle(n) \le a(n!)$ could work. Indeed, from our guess we have $\triangle(n+1) \le a(n+1)! \le a(n+1)! +2$ (the rightmost part of this inequality shows that $a(n!)$ does satisfy our recurrence inequality given above). however, $\triangle (2) = 6$ hence $a = 3$. So finally, $\triangle(n) \le 3(n!)$

---

2 - Forbidding Subgraphs and Extremal Problems

We will show a slightly fresh perspective on the general Ramsey problem, and Indeed show that finding the Ramsey number is an extremal problem.

General Ramsey Problem

Let $(\mathbb G_i) \ 1\le i \le n$ be a collection of graphs. $R(\mathbb G_i)$ is the smallest number of vertices that a complete graph can have, such that if we partition the edges of this complete graph, into $n$ non empty (color) classes, the edge-induced subgraph of one of the classes, contains some $\mathbb G_i$.

We give an example of such a problem:

If the edges of a $t-$clique is colored with at most $t$/2 colors, then, it must a monochromatic connected graph on $t$ vertices.

proof: by the pigeon hole principle, there must be a color class with at least $t(t-1)/2|C|$ edges. Since we have at most $t/2$ colors, that color class must contain at least $t-1$ edges.

The language of average degree here, is useless. Instead, we ask the question, what is the largest number of edges a graph on $n$ vertices can have, such that it does not contain an $s+1$ clique?

This leads us an extremal problems, where we want, (for a fixed number of vertices), “lots” of edges, and also want to forbid some subgraph

---

Turan Problems

Definition: $T(n,\mathbb H)$ is the largest number of edges, that an $n$ vertex graph can have, while being $\mathbb H$-free.

In particular, Turan showed us that a complete $s$-partite graph with nearly equal vertices in each partition $\lfloor n/s\rfloor , \lceil n/s\rceil$ will give us a graph with maximum edges, and will be $\mathbb K[s+1]$ free.

We will denote Turan graphs by $\mathscr{K}(n,s)$, where the fancy letter K is used to denote the fact that not only is the graph complete and $s$-partite on $n$ vertices, but there are nearly equal vertices in each partition. Among all complete s-partite graphs, it’s intuitively clear that the one with most parts (hence nearly equal vertices), will have most edges. We will need the number of edges of $\mathscr {K}(n,s)$ quite often, so here goes: first, $n = as + b, \ 0\le b < s$. Then upon doing some algebra, we have the following equation:

$$|E(\mathscr{K}(n,s))| = \frac{(s-1)(n^2-b^2)}{s} + {{b}\choose{2}}$$

But more useful is workable upper and lower bounds, without the remainder $b$ chiming in.

$$\frac{(s-1)n^2}{2s} - \frac{n}{4} <|E(\mathscr{K}(n,s))|<\frac{(s-1)n^2}{2s}$$

In particular, whenever $n$ is a multiple of $s$,

$$|E(\mathscr{K}(n,s))| = \frac{n^2}{2}\Big(1-\frac{1}{s}\Big)$$

---

Anti-Turan Problem

define $\overline{T} (n,\mathbb H)$ to be the smallest number of edges , that an $n$ vertex graph can have, so that no matter how we put these edges, we’re guaranteed to have $\mathbb H$ as a subgraph. This problem is intimately linked with the two color Ramsey number for $\mathbb H$. In particular, if $n \ge R(2,\mathbb H)$, then for every edge configuration resulting in $\mathbb G[n], \bar{\mathbb G}[n]$, at least one of them must contain $\mathbb H$. In particular, we look at all the configurations where $\mathbb G$ and $\bar{\mathbb G}$ have nearly equal number edges, namely${\lfloor n(n-1)/4\rfloor , \lceil n(n-1)/4\rceil}$. Hence, it is clear that in any case, all configurations of at least ${\lceil n(n-1)/4\rceil}$ edges is sufficient. Using $R(2,\mathbb K[s]) \le 4^s$, we have that for large enough $n$

Any graph on $n$ vertices and at least ${\lceil n(n-1)/4\rceil}$ edges, contains any subgraph of order close to $\log(n)/log(4).$

if $n< R(2,\mathbb H)$, then there are some arrangements of edges of $\mathbb G[n]$ such that neither $\mathbb G$, nor its compliment contains $\mathbb H$ . (this follows from the fact that the graph induced by red edges is complementary to the one induced by blue edges).

Take any such arrangement, where neither $\mathbb G[n]$ nor $\bar{\mathbb G} [n]$ contains $\mathbb H$ as a subgraph. one of these graphs contains at least $\lceil n(n-1)/4 \rceil$ edges. so even having more than half of all possible edges is not good enough. So in the cases that $n< R(2,\mathbb H)$ what can we say about anti-Turan problems? at least when $\mathbb H$ is a clique?

The general link: Suppose we have a $\mathbb G[n]$, and $|E(\mathbb G)| \ge T(n,\mathbb H) + 1$. Now suppose that $\mathbb G$ is $\mathbb H$-free. This would contradict the definition of $T(n,\mathbb H)$. Hence, no graph whose edges are more than $T(n,\mathbb H)$ is $\mathbb H$ free. So we have $\overline{T}(n,\mathbb H) = T(n,\mathbb H) + 1$.

---

Mantel’s Theorem (Special case of Turan’s Theorem)

The maximum number of edges that a triangle free graph on $n$ vertices can have is $\lfloor n^2/4\rfloor$, where equality occurs on the Turan graph of two parts, $\mathscr{K}(n,2)$.

for the following arguments, will consider an graph on $n$ vertices and $m$ edges, which is triangle free.

Proof 1: if $xy$ is an edge, then they cannot have a common neighbor, hence, $d(x) + d(y) \le n$. Using a counting argument, it is not difficult to show that $\sum_{xy\in E} d(x) + d(y) = \sum_{v\in V} d(x)^2$.

Using QM-AM inequality, we have that $\sum_{v\in V} d(x)^2 \ge {(\sum_{v\in V} d(x))}^2/n$. Thus, we have ${nm \ge 4m^2/n}$ or $m\le n^2/4$.

Noticing the sharp points of the inequalities, we can convince ourself that the extremal number of edges occurs in the Turan graph of two parts.

Proof 2: let $A$ be (an) independent set of maximum vertices. then, for any vertex $v$ the set of neighbors of $v$, $N(v)$ must be an independent set. hence $d(v) \le |A|$. Let $B = V-A$. in our original graph, since, $A$ is an independent set, all edges must have at least one endpoint in $B$. so adding up the degrees of all vertices in $B$ gives us an overcount of the number of edges. Hence, $E\le |A||B|$ (since any vertex $b \in B$ has $d(b) \le |A|$. using AM-GM, we have that ${E\le {(|A|+|B|/2)}^2 = n^2/4}$.

It is even easier to deduce the nature of the extremal graph here, observing the sharp points of each inequality. In particular, placing the condition that all edges must have exactly one endpoint in $B$ already gives us Bi-parted-ness. setting $d(v) = |A|$ gives us completeness.

---

3 - Schur’s Theorem

let $C$ be an $n$-set of colors. Then, $\forall n, \ \exists \ T(n) \in \mathbb N$ such that if $\mathbb T =\{1,... T(n)\}$ is colored with $C$, then $\exists x<y<z \in \mathbb T$ such that $x + y = z$ and $x,y,z$ are all the same color.

Proof:

construct an arbitrary coloring of $\mathbb T$ with $C$. Now, construct a complete graph $\mathbb K[T(n)]$ whose vertex set is $\mathbb T$. color the edge $ab$ with the color of $|a-b|$ for each $a,b \in \mathbb T$. Suppose we find a monochromatic triangle $i,j,k$ then, (WLOG suppose $i<j<k$). then $x =j-i, \ y = k-j$ and $z = k-i$ all have the same color. Indeed $x + y = z$. Therefore, $T(n) \leq \triangle(n)\le 3(n!)$. $\square$

---

Fat Schur’s Theorem

$\forall t,n \in \mathbb N$, There exists $N(t,n)$ such that if the set $[N] = \{1,...N\}$ is colored with an $n$-set, there exists a monochromatic set $\{a_1,a_2,...a_{t-1}, \sum_{i=1}^{t-1}a_i\}$.

Proof:

We show that $N(t,n)\le \rho(t,n)$. Consider an arbitrary coloring of the set $[\rho]$. Construct a coloring of the edges of $\mathbb K[\rho]$ such that the color of the edge $xy$ is the color of $|x-y| \in [\rho]$. Then, for some color $c^*$ we can find $\mathbb K^{c^*}[t]$. Then, let $V(\mathbb K^{c^*}[t]) = \{v_1,v_2,...v_t\}$. where $v_i<v_{i+1}$.

consider the set $V^* = \{v_{i+1} - v_{i}\}$, then each $v^*\in V^*$ has color $c^*$. but $\sum_{v^*\in V^*}v^* = v_t -v_1$. Which is an edge in $\mathbb K^{c^*}[t]$, and therefore also has color $c^*$. Hence $V^*\cup\{\sum_{v^*\in V^*} v^*\}$ produces the desired set. $\square$

---

4 - Anti-Fermat’s Theorem

let $p$ be a prime, and $\mathbf{C}_{p-1}$ b e the cyclic (commutative) group of order $p-1$. Depict the elements of $\mathbf{C}_{p-1}$ as $\{0,1,...p-2\}$, where each number $t$ co-responds to the anti-clockwise rotation by $\frac{2\pi}{t}$ of a regular $p-1$ gon. $\forall a,b \in \mathbf{C}_{p-1}$, define $a\circ b = a +b$ modulo $p-1$ to be the group operator.

now, let $0 \le m\leq p-2$. Define $\mathbf{C}^m_{p-1} = \{x^m | x\in \mathbf{C}_{p-1}\}$ (where $x^m$ is $x$ composed on itself $m$ times). Indeed, if $m \neq 0$, then $\mathbf{C}^m_{p-1} = \{mx \ (mod \ p-1) \ | x\in \mathbf{C}_{p-1}\}$ is subgroup of $\mathbf{C}_{p-1}$. Intuitively, we can imagine $\mathbf{C}^m_{p-1}$ as a regular polygon whose vertices is the subset of $\{0,1,...p-2\}$ which contains $0$ and all multiples of $m$ in $\{0,1,...p-2\}$. ie, $\mathbf{C}^m_{p-1}$ covers the congruence class of $0$ modulo $m$ contained in $\{0,1,...p-2\}$. if we rotated $\mathbf{C}^m_{p-1}$ by $1$ unit anti-clockwise, then now it covers the congruence class of $1$ modulo $m$, and so on. So the entire set $\{0,1,...p-2\}$ can be covered by disjoint subsets, each co-responds to a rotation of $\mathbf{C}^{m}_{p-1}$.

Hence, we have the following beautiful result: Let $r\leq m$ be the number of congruence classes modulo $m$ contained in $\{0,1,...p-2\}$. Let $(a_i)$ be elements of $\mathbf{C}_{p-1}$, and let $a_i\circ\mathbf{C}^{m}_{p-1}$ denote the congruence class modulo $m$, obtained by the orbit of $C^{m}_{p-1}$ under the rotative action of $a_i$. Then $\mathbf{C}_{p-1} = \bigcup_{i=1}^{r} a_i\circ\mathbf{C}^{m}_{p-1}$

Now, let $\mathbb Z^*_p$ denote the multiplicative group obtained by removing $0$ from the congruence classes modulo $p$. $\mathbb Z^*_p$ is isomorphic to $\mathbf{C}_{p-1}$ by the bijection induced by $t \mapsto r_{t-1}$. Moreover, the subgroup $G_m = \{x^m | x \in \mathbb Z^*_p \}$ is isomorphic to $\mathbf{C}^{m}_{p-1}$ by the same bijection ($m \neq 0$).

Hence, there are elements $(t_i) \in \mathbb Z^*_p$ such that $\mathbb Z^*_p = \bigcup_{i=1}^{r} t_iG_m$ is a partition of $\mathbb Z^*_p$. Color the $i$th block in the partition entirely with color $c_i$ for each $1\le i\le r$. since $r\le m$, we need at most $m$ colors to do so. And, for a particular choice of $m$, the prime $p$ can be made sufficiently large. In particular, if $p \ge T(m)$ as defined in Schur’s theorem, there is a monochromatic solution to ${a + b = c}$ where $a<b<c$ are in $\mathbb Z^*_p$. Indeed, then $a,b,c$ must all colored $c_j$ and hence must all be in the block $t_jG_m$. Hence, $a = t_jx^m, \ b = t_jy^m, \ c +t_j z^m$ for some $x,y,z \in \mathbb Z^*_p$.

Therefore, (given that $gcd(t_j,p) = 1$) we have $x^m + y^m = z^m$ in $\mathbb Z^*_p$.

Anti-Fermat’s Theorem: $\forall m\ge 3$, there exists a prime $p(m)$ such that the Fermat equation ${x^m + y^m = z^m}$ has a solution modulo $p$. In particular, it’s sufficient to choose a prime $p \ge 3(m!)$.

One way to eliminate integer solutions to a polynomial equation is to eliminate solutions modulo all primes. In particular, if an equation has no solutions modulo any prime, then it has no solutions at all. The above theorem clearly shows that such an approach would not work on Fermat’s equation.

---

A Note on rho(t,n)

define $\rho(t,n) = R(t,t,.._{n \ times}..t)$. That is, $\rho(t,n)$ is the smallest number $\rho$ for which any coloring of the edges $\mathbb K[\rho]$ with an $n$-set, contains $\mathbb K^{c^*}[t]$ for some color $c^*$.

notice that $\triangle(n) = \rho(3,n) \le 3(n!)$. This might make us conjecture something like ${\rho(k,n) \le k(n!)}$, which is utter nonsense. put $n = 2$, and we get $\rho(t,2) = R(t,t) \le 2t$. (garbage, false, untrue).

the best (upper) bound on $R(t,t)$ is proportional (for a constant factor smaller than 1) to $4^{s-1}$.

so we stop here.

---

5 - Erdos Discrepancy Problem, Van der Waerden’s Theorem

It seems that Hilbert spaces are generalizations of Finite dimensional Vector spaces into infinite dimensional ones while preserving some properties. For whatever definition of $1$ (I mean in some chosen Field), The unit sphere in a Hilbert space is the set of all infinite dimensional vectors, whose norm/modulus is $1$. Tao recently proved that for any arbitrary point on the unit sphere of a Hilbert space, There must subsequence obtained by choosing indices from some homogenous arithmetic progression $d,2d,3d,...$ such that the partial sums can be made arbitrarily large.

In particular, let $<f(1),f(2),.....>$ be an arbitrary infinite sequence of vectors that lives on the unit sphere. Then, For every $C>0$ we have a $d$ and $k$ for which $|\sum_{i=0}^{k} f(di) | > C$.

Erdos particularly conjectured that for $f(i)\in \{-1,1\}$ we have $d,k$ for each integer $C$ such that $|\sum_{i=0}^{k} f(di) | > C$.

In fact, if we relax and allow for indices not in homogenous AP, but rather in any AP, then the result becomes elementary:

Consider a finite set of vectors on the unit sphere $V_n = \{v_1,v_2,..v_n : \ |v_i| = 1\}$. Construct an arbitrary infinite sequence $F =<f(1),f(2),....>$ where $f(i) \in V_n$ . We want to know if for every Integer $C$, does there exist an arithmetic progression (defined by some triple $(t,d,k)$: $t$ for the base point, $d$ for the common difference, $k$ for the number of terms) ${A =\{t +(i-1)d \ | \ 1 \le i\le k\}}$ such that $|\sum_{a\in A} f(a) | > C$?

Indeed, color the index $x$ of $F$ $c_i$ if and only if $f(x) = v_i$. That is, each vector co-responds to a color.

---

Van der Waerden’s Theorem

Van-der-Waerden Theorem:

$\forall n,k \in \mathbb N$ $\exists W(n,k)$ so that if $[W] = \{1,2,...,W\}$ is colored by an $n-$set, we have a monochromatic arithmetic progression of length $k.$ ie, there exists a subset ${A^* =\{t +(i-1)d \ | \ 1 \le i\le k\}}$ whose all elements are colored with a color $c^*$.

Indeed, The Van-der-Waerden Theorem implies that $\forall a^* \in A^*$ $f(a^*) = v^*$ for some $v^* \in V_n$ (because the color of an index co-responds to a unique vector in our coloring of $F$).

hence $|\sum_{a^*\in A^*} f(a^*) | = |kv^*| =k|v^*| = k$. In particular, it is sufficient to set $k = C+1$.

---

The Fan Lemma

From now on, an arithmetic progression $a +rd, a+(r+1)d, .. , a+(k)d$ will be denoted by $a +[r,k]d$.

Definition (Fan): a fan of radius $k$, degree $d$, focused at $a$, is the $d-$tuple ${F = <a+ [0,k]r_j>}$, for $1\le j \le d$.

The arithmetic progression $a + [1,k]r_j$ is the jth Spoke of the fan $F$.

Definition (Polychromatic Fan): The defined fan $F$ is called polychromatic if each of its $d$ spokes are monochromatic AP’s (of length $k$) for different colors $c_1,c_2,..c_d$ and its focus $a$ is colored $c^* \neq c_1,c_2,..c_d.$

Definition (Shift): The $x$ -shift of a fan $F$ is the $d$-tuple $<x+a + [0,k]r_j>$.

Suppose for the common difference $D$, we have fully disjoint series of shifted fans $F_1, F_{1+D}, F_{1+2D},....F_{1+kD}$ (no two fans have even a single common point). Moreover suppose each fan in the series is polychromatic, and has the exact same coloring pattern! (the picture below should illustrate what we mean).

(indeed the picture should look like the exact same, EXACTLY SAME colored fan, shifted $k$ times in such a way that the base point’s form a $k$-length AP)

Then the series of fans can be written as $0D + F, \ 1D + F, \ 2D +F,\ ..., \ kD +F$. (The entirety of each of these fans live in completely disjoint blocks of $\mathbb N)$.

Now, for a particular $j$, select the $k^{th}$ element of the $j^{th}$ spoke of the first fan, $0D + F$, the ${(k-1)^{th}}$ element of the $j^{th}$ spoke of the second fan $1D +F$ and so on.

in particular, we have the series ${a + kr_j, \ a+D +(k-1)r_j, \ a+2D +(k-2)r_j, \ . . ., \ a +kD +(k-k)r_j}$

indeed, the above series is an arithmetic progression, $(a +kr_j) + [0,k](D-r_j)$ for each ${1 \le j \le d}$. We will show that these AP’s could be the spokes of a new fan focused at $a +kD$. ineed, all of our progressions are of the form $(a + kr_j) +I(D-r_j)$. where $I$ goes from $0$ to $k$.

Write $I' = I-k$. then all our progressions are of the form $a +kD +[0,k](r_j-D)$. Indeed each of these $d$ progressions could be focused as spokes at $a + kD$. but notice that even the basepoints of all our inital fans could also be focused at $a + kD!$ because our basepoints are of the form $a + kD +[0,k](-D)$. Indeed each of these spokes are monochromatic, and are of different color. even the basepoint is of a different color because each of our shifted fans is polychromatic.

Therefore the fan $F^* = <a +kD +[0,k]r^*_j>$ where $r^*_0 = -D$ and $r^*_j = (r_j-D)$ for $1\le j \le d$. Therefore, $F^*$ is a “weakly” polychromatic fan of radius $k$, focused at $a+kD$, with degree $d+1$. so either $F^*$ is polychromatic, or $F^*$ has a monochromatic $k+2$ length AP.

Call the above argument the Fan Lemma.

---

Proof of Van der Waerden’s Theorem

But where are we going to find such shifted fans?

recall the van-der warden number $W(n,k)$. indeed, $W(n,1)$ and $W(n,2)$ exist. (Any $1$ number is a monochromatic AP of length $1$, by $PHP$, $W(n,2) = n+1$. suppose for $k\ge 1$ ${W(n,k-1)}$ exists for all $n$.

In particular, we will show that for each $d = 1$ to $n$, there exists $M(d) \in \mathbb N$ such that any $n-$coloring of $[M(d)]$ contains a $k$ term monochromatic AP, or a polychromatic fan of degree $d$, and radius $k-1$, at some focus.

Base case ($d = 1$): notice that an interval $[W(n,k-1)]$ contains a monochromatic AP of length $(k-1)$.

call it let the common difference (which itself has an upper bound ofc) be $T$ for this ap, ${a + [0,k-2]T}$. Then, join in the term $a + (k-1) T$ to this ap, this either has the same color as the rest of the progression (giving a monochromatic $k$ term AP) or a polychromatic fan of degree $1$, focused at $a + (k-1) T$.

Inductive step: suppose for some $d<n$, there exists $M(d) \in \mathbb N$ such that any $n-$coloring of $[M(d)]$ contains a $k$ term monochromatic AP, or a polychromatic fan of degree $d$, and radius $k-1$, at some focus.

Now, The number of different coloring patterns an [$M(d)]$ block due to an $n-$set is $n^{M(d)}$.

denote each of these coloring patterns themselves by new colors. $($let each of the $n^{M(d)}$ coloring patterns be mapped to a unique NEW color).

Then, by imagining each $[M(d)]$ length block be indexed b it’s first element, club the entire block together, fuzzing it to its new color).

then consider $W(n^{M},k-1)$ blocks. then, we have a monochromatic “block” AP of length ${(k-1)}$. if we find a $k$ length monochromatic AP in any 1 block, we are done. so suppose all blocks have a polychromatic fan of degree $d$, and radius $k-1$, at some focus.

Since we have a monochromatic “block” AP of length $k-1$, EACH fan in the block has the exact same coloring pattern!!!! (Since the entirety of each block has the same coloring pattern!!)

Therefore, by the Fan Lemma, we either have a polychromatic fan of degree $d+1$, and radius $k-1$, or a monochromatic $k$-length AP. In the latter case, our induction (main) is closed. In general our inner Induction is now closed.

Closing the argument: In the former case, let $d = n$ then, if we have a polychromatic fan of degree $n$ and radius $k-1$, then each of the $n$ spokes are assigned a different color, so the focus CANNOT be a different color from each of the spokes, so we have a contradiction. hence, a $k$ -length AP. $\square$

---

6 - Probabilistic Method, Lower Bound for Ramsey Type Numbers

we would like a lower bound for $R(n,n)$ for example. We use the crude-union bound. the probability that there exists a monochromatic $\mathbb K[n]$ in $\mathbb K[T]$ is less than or equal to ${{T}\choose{n}}2^{1-{{n}\choose{2}}}$.

so it’s okay to set ${{T}\choose{n}}2^{1-{{n}\choose{2}}} <1$. even the largest $T$ which satisfies the given inequality is strictly smaller than $R(n,n)$. using ${{T}\choose{n}} < (Te/n)^n$ and simplifying we get the following result.

$$T< \frac{n2^{\frac{n}{2}}}{e\sqrt 2 2^{\frac{1}{n}}}$$

so, in fact,

$$R(n,n)\ge \frac{n2^{\frac{n}{2}}}{e\sqrt 2 2^{\frac{1}{n}}}$$

for large,$n$ noting that $R$ is an integer, we have

$$R(n,n) > \frac{n2^{\frac{n}{2}}}{e\sqrt 2}$$

---

7 - Path Number

define $P(m,n) = R(\mathbb P[m],\mathbb K[n])$ . that is the smallest number $R$ for which a red-blue coloring of the edges of $\mathbb K[R]$ either contains a red $\mathbb P[m]$ or a blue $\mathbb K[n]$. Note, that path length is usually measured by the number of edges, but here $m$ denotes the number of vertices in the path.

Upper Bound

we claim that $P(m+1,n+1) \le P(m+1,n) + P(m,n+1) = T$.

construct a red-blue coloring of $\mathbb K[T]$. the degree of any vertex is ${P(m+1,n) + P(m,n+1) -1}$. suppose there exists $v^*$ such that $\#r(v^*) \ge P(m,n+1)$

indeed, if we have a blue $\mathbb K[n+1]$ , we are done. if we have a red $\mathbb P[m]$, join to $v^*$ by red edge. and we are done.

Else, all vertices have $\#r(v) < P(m,n+1)$. hence $\#b(v) > P(m+1,n) -1$. So indeed, ${\#b(v) \ge P(m+1,n)}$.

if we have a red $\mathbb P[m+1]$, we are done. if we have a blue $\mathbb K[n]$, $v$ is adjacent to $\mathbb K[n]$ via all blue edges, hence, we are done.

notice that given $P(m,2) = m, P(n,2) = n$, we can use a double induction (using the above inequality) to show that $P(m,n) \le (m-1)(n-1) + 1$.

Exact Value via Descent

we claim that $P(m,n) = (m-1)(n-1) + 1$.

suppose $P(m,n) \le (m-1)(n-1)$. This will act as a base case for our inductive descent into absurdity.

we will show that if $r < min((m-1)(n-2)),((m-2,n-1))$ , ${P(m,n) \le (m-1)(n-1) -r }$ implies $P(m,n) \le (m-1)(n-1) -r -1$. that is we can safely delete a vertex.

let $T' = (m-1)(n-1) - r$. construct a red-blue coloring of $\mathbb K[T']$. indeed, suppose ${P(m,n) \le (m-1)(n-1) -r }$.

given that $r < min((m-1)(n-2)),((m-2,n-1))$, if we find a red , the remaining vertices are $(m-1)(n-2) - r$ in number, which is greater than zero. So delete one vertex from this. Similarly, if we find a blue $\mathbb K[n]$, the remaining vertices are $(m-2)(n-1) - r$ in number, which is greater than zero, so we can delete 1 vertex from this.

Hence, the induction is closed reaching ${ r = min((m-1)(n-2)),((m-2,n-1))}$.

so suppose $m<n$. then, $r = (m-2)(n-1)$.

indeed, it must be that ${P(m,n) \le (m-1)(n-1) - (m-2)(n-1)}$. Hence, $P(m,n) \le n-1$. Color all edges of $\mathbb K[n-1]$ blue. Then, we neither have a blue $\mathbb K[n]$ nor a red $\mathbb P[m]$.

Similarly, let $m\ge n$. Then, $r =(m-1)(n-2)$. we get $P(m,n) \le m-1$. color all edges of $\mathbb K[m-1]$ red. we neither have a blue $\mathbb K[n]$ nor a red $\mathbb P[m]$.

The thing is, our induction step is correct. Therefore, the base case must be wrong. Hence $P(m,n) > (m-1)(n-1)$. Arriving at the desired result.

Multicolor Path Ramsey Numbers

Define $P^*(a_1,a_2,...a_n) = R(\mathbb P[a_1],\mathbb P[a_2],... , \mathbb P[a_n])$.

Now, notice that $P(a_1,a_2,...a_n) \le P(a_1, P^*(a_2,..a_n)) = (a_1-1)(P^*(a_2,..a_n) - 1) + 1$.

Applying this recursively, we get that $P^*(a_1,a_2,...a_n) \le \prod_{i=1}^{n} (a_i -1) + 1.$ Setting each ${a_i = a}$, we obtain the desired result.

---

8 - AP Path Number Lemma

let $V = v_1,v_2,...v_N$ be a subset of the integers, written in increasing fashion. if the edges of complete graph on $V$ as the vertex set, is colored such that $v_iv_j \mapsto |v_j-v_i|$, then if we have a monochromatic, $k$-path, we have a $k$-length AP in $V$.

Because we have the following series of equalities $|{u_2-u_1| = |u_3 -u_2| .... |u_k -u_{k-1}| = d}$,

suppose, $u_{i}>u_{i-1}$. then $|u_{i+1}-u_{i}| = u_i - u_{i-1}$. now suppose $u_{i+1}<u_i$. then, ${u_i -u_{i+1} = u_i - u_{i-1}}$. Hence, $u_{i+1} = u_{i-1}$, which is a contradiction, (all of our vertices are unique numbers). hence, our path has an entire sequence of increasing vertices. (up to a reversal of the path).

Therefore, we have an increasing sequence of numbers $u_1<u_2<..<u_k$ and $u_{i+1}-u_i = d$

(is this an if and only if condition!!!!????) The answer is YES.

---

9 - Density, Arithmetic Progressions, and Szemeredi

Now, let $\mathbb A = \{a_1<a_2,....\}$ be an infinite subset of $\mathbb N$. (which is normalized such that $a_1 =1$) let a finite subset of $\mathbb A$ be denoted by $A$.

then, define the color-density of $A$ to be the number of absolute differences in $A$. (denoted by $\gamma(A)$). That is, $\gamma(A) = \Bigm| \{ \ |{a_j-a_i}| \ : a_j,a_i \in A\}\Bigm|$.

Now, if $|A| \ge \phi(\gamma(A),k)$, then $A$ contains a $k-$length arithmetic progression. (by AP path number lemma).

now, define $\mathbb A(N) = \mathbb A \ \cap \ \{1,2, ...N\}$.

Then, The density sequence of $\mathbb A$ is $d_N = |\mathbb A(N)|/N$. hence, if for each $N$, if ${|\mathbb A(N)| \ge \phi(\gamma( \mathbb A(N)),f(N))}$, then $\mathbb A(N)$ contains at least a $f(N)$ length AP.

Moreover, if $f(N)$ is increasing (however slow), and unbounded, then $\mathbb A$ contains arbitrarily long AP’s.

In this case, we have the following term-wise lower bound on the natural density sequence of $\mathbb A$.

$$d_N(\mathbb A) \ge \frac{\phi(\gamma( \mathbb A(N)),f(N))}{N}$$

conversely, if for some infinite set $\mathbb A \subset \mathbb N$, eventually, the density sequence $d_N(\mathbb A)$ follows the (term wise) the above upper bound, then it must contain arbitrarily long arithmetic progressions (for increasing and unbounded $f(N)$.)

The above inequality talks about the sufficiency for the density for our chosen set in some sense .

indeed,

$${|\mathbb A(N)| \ge \phi(\gamma( \mathbb A(N)),f(N))}$$

Hence, by allowing $f(N)$ to be a horrendously slow growing (yet unbounded) function, and for good upper bounds on $\gamma$ it should be possible to make $\mathbb A$ sparse. How sparse? that’s for another day. (of course $f(N)$ has to be eventually floored for $\phi$, because he only accepts integer inputs).

Essentially, Szemeridi’s theorem could be proven if there exists increasing and unbounded $f(n)$ so that $g(n) \ge\phi(\gamma( \mathbb A(n)),f(n))/n$ is decreasing. But for our crude upper bound on $\phi$ given below, we give a slick proof that since $f(n)$ is unbounded, not only is $g$ non decreasing, but also unbounded (curtsey of @Steen82 from stack exchange) |

$$\frac{\phi(\gamma( \mathbb A(n)),f(n))}{n} \le \frac{(f(n)-1)^{n-1} + 1}{n} = g(n)$$

since $f(n)$ is unbounded and increasing, there must be a $k$ such that $f(k) \ge 3$. hence, ${f(n+k) \ge 3 }$, for all $n$. hence, we have the following inequality:

$$g(n+k) \ge \frac{(f(n+k)-1)^{n+k-1} + 1}{n+k} \ge \frac{2^{n+k-1} + 1}{n+k}$$

So we need better upper bounds on $\phi(n,k)$.

I guess, the better idea is to first get good bounds on $\gamma (\mathbb A(n)).$ in particular, for a fixed $|\mathbb A(n)|$ , what’s the LARGEST $\gamma(\mathbb A(n))$ could in induce?

In other words, if $d(n)$ denotes the fraction of points we could pick in the inteval $[n]$, how could we pick it to maximize $\gamma$ for that interval?

In even more different words, what is a decent relationship between $\gamma (\mathbb A(n)).$ and $|\mathbb A(n)|$ ?

---

10 - The other Erdos-Gallai Theorem

Proposition: Suppose we have a connected graph $\mathbb G[n]$ on $n$ vertices. let $\omega(\mathbb G)$ denote the minimum degree of all verticles of $\mathbb G$. Wlog suppose $2w(\mathbb G) < n-1$. Then, there exists a path on $2w(\mathbb G) + 1$ vertices in $\mathbb G$.

Proof: supppose the longest path in $\mathbb G$ is $P = v_1,v_2,... v_m$. ( $m<n$ , because $m = n$ is trivial) Consider the induced subgraph of $\mathbb G$ induced by $v_1,v_2,...v_m$. call it $\mathbb G(P)$. we claim that $\mathbb G(P)$ does not have a cycle with $m$ edges (notice that the cycle with $m$ edges in $\mathbb G(P)$ will contain all $v_1,v_2,...,v_m$), Because if it did have one, since $m<n$, there must be a vertex not in $\mathbb G(P)$ which is connected to the cycle in $\mathbb G(P)$. so, we could cutoff the edge of the cycle at the point where the external vertex joins it, and create a larger path. (see picture below) Resulting in a contradiction.

Now, also notice that in $\mathbb G$, all the neighbors of $v_1$ and $v_m$ must be among $v_1,v_2,...v_m$. because if even one had an “external” neighbor, we could increase the path length by 1, giving a contradiction.

In particular, both $v_m$ and $v_1$ must have at least $\omega(\mathbb G)$ neighbors in $\mathbb G(P)$.

Suppose $v_i$ was a neighbor of $v_m$. then we claim that $v_{i+1}$ cannot be a neighbor of $v_1$. else, we have the following cycle with $m$ edges: $v_1,v_2,.. ,v_i ,v_m,v_{m-1},... v_{i+1},v_1$. Which is disallowed as stated earlier.

Hence, for every neighbor of $v_m$ in $P$, there is a non neighbor of $v_1$ in $P$. but there are at least $\omega(\mathbb G)$ neighbors of $v_m$ in $P$. Therefore, there are at least $\omega (\mathbb G)$ non-neighbors of $v_1$ in $P$. hence including $v_m$, there are at least $2\omega(\mathbb G) + 1$ vertices in $P.$ $\square$

We could restate the proposition in the following way:

Lemma 1: If $\mathbb G[n]$ is a connected graph with minimum degree $\omega(\mathbb G)$, then there exists a path of length (number of edges) $\min(2\omega(\mathbb G),n-1)$.

next define the average degree of a graph $\mathbb G[n]$ , $\langle\mathbb G[n]\rangle = 2|E(\mathbb G)|/n$.

Lemma 2: Now, we claim that if $\mathbb G$ is not connected, there exists a component $\mathbb H$ of $\mathbb G$ such that $\langle\mathbb H\rangle \ge \langle\mathbb G\rangle$.

Proof: Since there are no edges between (connected) components of $\mathbb G$, let $\mathbb H_i$ for $i = 1$ to $p$ be all the components of $\mathbb G$. Now suppose that for each $i$, $\langle\mathbb H_i\rangle <\langle\mathbb G\rangle$. that is, $2|E(\mathbb H_i)| \ / h_i < \langle\mathbb G\rangle$. (Where $h_i$ is the order of $\mathbb H_i)$. Hence, we have the following inequality:

$$2\cdot\sum_{i=1}^{p} \big|E(\mathbb H_i)\big | < \langle\mathbb G\rangle\cdot\sum_{i=1}^{p} h_i$$

Therefore, upon rearrangement, and noting that $\sum_{i=1}^{p} \big|E(\mathbb H_i)\big| = \big|E(\mathbb G)|$, and $\sum_{i=1}^{p} h_i = n$, we get the contradiction $\langle\mathbb G\rangle < \langle\mathbb G\rangle$. $\square$

Erdos-Gallai Theorem: Any graph $\mathbb G$, must contain a path of length of at least $\langle\mathbb G\rangle$.

Proof: we induct on the order $n$, of $\mathbb G$. Suppose the claim is true for all graphs of order $k$, $k<n$.

consider any graph $\mathbb G[n]$. Suppose $\mathbb G$ is connected. Further, suppose there exists a vertex $v$, such that $d(v) \le \frac{1}{2} \langle\mathbb G\rangle$. Notice that $\langle\mathbb G\rangle = ( \ 2(d(v)) + (n-1)\langle\mathbb G-v\rangle\ )/n$. Hence, we have:

$$n\langle\mathbb G\rangle - (n-1)\langle\mathbb G-v\rangle\ = \ 2d(v) \le \langle\mathbb G\rangle$$ $$\langle\mathbb G -v \rangle \ge \langle\mathbb G\rangle$$

Hence, by the induction hypothesis, $\mathbb G -v$ must contain a path of length at least $\langle\mathbb G -v\rangle \ge \langle\mathbb G\rangle$.

Now, Suppose $\mathbb G$ is connected, and all vertices have $d(v) > \frac{1}{2} \langle\mathbb G\rangle$. then the minimum degree of the graph $\mathbb \omega (\mathbb G) > \frac{1}{2}\langle\mathbb G\rangle$ . Hence, it must contain a path of length $\min (2\omega(\mathbb G),n-1)$. But $\langle\mathbb G \rangle < 2\omega(\mathbb G).$ and $\langle\mathbb G\rangle \le n-1$ (equality holding for complete graphs) hence, $\mathbb G$ must contain a path of length $\langle\mathbb G\rangle$ .

Finally let $\mathbb G$ be disconnected. Then, there exists a (connected) component $\mathbb H$ of $\mathbb G$, such that $\langle\mathbb H\rangle \ge \langle\mathbb G\rangle$. (see lemma 2) but since the order of $\mathbb H$ is strictly smaller than $n$, by the induction hypothesis, $\mathbb H$ contains a path of length at least $\langle\mathbb H\rangle \ge \langle\mathbb G\rangle$. $\square$

The original Erdos-Gallai Theorem was stated this way:

If the average degree of a graph $\mathbb G$ is greater than $t-2$, then there exists a path on $t$ vertices in $\mathbb G$.

We know that we will have a path of length at least $\langle\mathbb G\rangle >t-2$. Hence, we have a path of length at least $t-1$ edges, or $t$ vertices.

---

The Multicolor Path-AP Upper Bound

$\phi(n,t)\le nt$

Proof: construct an arbitrary coloring of the edges of $\mathbb K[nt]$ with $n$ colors.

Notice that there is a color class of size (number of edges) at least $t(nt-1)/2$. Consider a subgraph which contains all vertices, and only the same-colored $t(nt-1)/2$ edges. The average degree of this graph is $t - \frac{1}{n}$. Hence By the Erdos-Gallai theorem, this subgraph contains a $t$ vertex path. (which is monochromatic). $\square$

---

Sources, Acknowledgements, Remarks

I can’t recall every source that contributed to these notes. I will keep updating this list as I remember or rediscover them. If you recognize something I’ve written here that traces back to a source I haven’t credited, please let me know. Also there are theorems here without proof for which I should locate a proof or a source and put it in, will do.

• MIT 18.225: Graph Theory and Additive Combinatorics (Fall 2023), Lectures 1-3
• Van der Waerden’s Theorem proof walkthrough - I was not able to proof the Van der Waerden theorem myself, and used this video for help along with Terrence Tao’s article, in particular I only understand the combinatorial proof.
• Terrence Tao: The Erdos Discrepency Problem - I do not claim to understand all the work presented in the talk, a lot of the the talk was beyond my knowledge at the time of working on this, and is still that way.
• Some stack exchange threads that helped me
  • Is there a better upper bound for the Ramsey number for monochromatic paths? - Existence of a subsequence that has positive limit given the original sequence - Need for constructive examples for two sequences on the positive reals with certain properties
• Finally, some of the arguments here are in my opinion poorly worded, I will eventually make them better, moreover, if you find errors and typos which are guaranteed to exist in, hit me up on twitter.