Ramsey-Problems

We will denote a complete graph of order $a$ (also called $a$ -clique) as $K [a]$ .
Any general graph of order $a$ will be denoted by $G [a]$ .
If a graph’s edges are monochromatic in color $c$ , we denote it by $G^{c} [a]$ .
If a graph’s vertices are monochromatic in color $c$ , we denote it by $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 N$ and $m \geq n \geq 2$ . Define $R (m, n)$ to be the smallest number $R$ for which any coloring of the edges of $K [R]$ with the set ${r, b}$ (denoting red and blue), contains $K^{r} [m]$ or $K^{b} [n]$ .

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

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

Proof:

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

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

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

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

Proof:

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

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.

for $1 \leq i \leq n$ , let $C = {c_{i}}$ be a color set, and $(a_{i})$ be an $n$ -tuple of natural numbers ( $a_{i} \geq 2)$ .

denote $R (a_{i})$ to be the smallest number $R$ for which in any coloring of the edges of $K [R]$ with $C$ ,

at least one of $K^{c_{i}} [a_{i}]$ is in $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 $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 $K [R (R (a_{i}), a_{n + 1})]$ , there are only two colors, namely $c^{*}$ and $c_{n + 1}$ . if we find $K^{c_{n + 1}} [a_{n + 1}]$ , we are done. So, suppose we find $K^{c^{*}} [R (a_{i})]$ . In that case, reverse the transformation such that all edges in $K^{c^{*}} [R (a_{i})]$ are colored as per the initial coloring with the color set $C$ . By our induction hypothesis, $K^{c^{*}} [R (a_{i})]$ contains at least one of $K^{c_{i}} [a_{i}]$ .

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 $K [R (R (a_{1}, a_{2}, . . a_{n - 1}), R (a_{n}, a_{n + 1}))]$ either contains $K^{c^{*}} [R (a_{1}, a_{2}, . . a_{n - 1})]$ or $K^{c^{* *}} [R (a_{n}, a_{n + 1})]$ ).

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

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

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

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

2 : Schur’s Theorem

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

proof:

construct an arbitrary coloring of $T$ with $C$ . Now, construct a complete graph $K [T (n)]$ whose vertex set is $T$ . color the edge $a b$ with the color of $| a - b |$ for each $a, b \in 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 △ (n) \leq 3 (n!)$ .

3 : Anti-Fermat’s Theorem

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

now, let $0 \leq m \leq p - 2$ . Define $\bold C_{p - 1}^{m} = {x^{m} | x \in \bold C_{p - 1}}$ (where $x^{m}$ is $x$ composed on itself $m$ times). Indeed, if $m = 0$ , then $\bold C_{p - 1}^{m} = {m x (m o d p - 1) | x \in \bold C_{p - 1}}$ is subgroup of $\bold C_{p - 1}$ . Intuitively, we can imagine $\bold C_{p - 1}^{m}$ 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, $\bold C_{p - 1}^{m}$ covers the congruence class of $0$ modulo $m$ contained in ${0, 1, . . . p - 2}$ . if we rotated $\bold C_{p - 1}^{m}$ 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-responding to a rotation of $\bold C_{p - 1}^{m}$ .

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 $\bold C_{p - 1}$ , and let $a_{i} \circ \bold C_{p - 1}^{m}$ denote the congruence class modulo $m$ , obtained by the orbit of $C_{p - 1}^{m}$ under the rotative action of $a_{i}$ . Then $\bold C_{p - 1} = ⋃_{i = 1}^{r} a_{i} \circ \bold C_{p - 1}^{m}$

Now, let $Z_{p}^{*}$ denote the multiplicative group obtained by removing $0$ from the congruence classes modulo $p$ . $Z_{p}^{*}$ is isomorphic to $\bold C_{p - 1}$ by the bijection induced by $t \mapsto r_{t - 1}$ . Moreover, the subgroup $G_{m} = {x^{m} | x \in Z_{p}^{*}}$ is isomorphic to $\bold C_{p - 1}^{m}$ by the same bijection ( $m = 0$ ).

Hence, there are elements $(t_{i}) \in Z_{p}^{*}$ such that $Z_{p}^{*} = ⋃_{i = 1}^{r} t_{i} G_{m}$ is a partition of $Z_{p}^{*}$ . Color the $i$ th block in the partition entirely with color $c_{i}$ for each $1 \leq i \leq r$ . since $r \leq 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 \geq T (m)$ as defined in Schur’s theorem, there is a monochromatic solution to $a + b = c$ where $a < b < c$ are in $Z_{p}^{*}$ . Indeed, then $a, b, c$ must all colored $c_{j}$ and hence must all be in the block $t_{j} G_{m}$ . Hence, $a = t_{j} x^{m}, b = t_{j} y^{m}, c + t_{j} z^{m}$ for some $x, y, z \in Z_{p}^{*}$ .

Therefore, (given that $g c d (t_{j}, p) = 1$ ) we have $x^{m} + y^{m} = z^{m}$ in $Z_{p}^{*}$ .

Anti-Fermat’s Theorem: $\forall m \geq 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 \geq 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.

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

notice that $△ (n) = ρ (3, n) \leq 3 (n!)$ . This might make us conjecture something like $ρ (k, n) \leq k (n)!$ , which is utter nonsense. put $n = 2$ , and we get $ρ (t, 2) = R (t, t) \leq 2 t$ . (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.

Fat Schur’s Theorem

$\forall t, n \in 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) \leq ρ (t, n)$ . Consider an arbitrary coloring of the set $[ρ]$ . Construct a coloring of the edges of $K [ρ]$ such that the color of the edge $x y$ is the color of $| x - y | \in [ρ]$ . Then, for some color $c^{*}$ we can find $K^{c^{*}} [t]$ . Then, let $V (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_{t} - v_{1}$ . Which is an edge in $K^{c^{*}} [t]$ , and therefore also has color $c^{*}$ . Hence $V^{*} \cup {\sum_{v^{*} \in V^{*}}}$ produces the desired set.

Erdos Discrepancy Problem, Van-Der Warden 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$ , 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, 2 d, 3 d, . . .$ 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 (d i) | > 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 (d i) | > 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)$ integers $a$ for the base point $, d$ for the common difference, $k$ for the number of terms) $A = {t + (i - 1) d | 1 \leq i \leq 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}$

Van-der-warden Theorem :

$\forall n, k \in 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 \leq i \leq k}$ whose all elements are colored with a color $c^{*}$ .

Indeed, The wan-der Warden 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^{*}) | = | k v^{*} | = k | v^{*} | = k$ . In particular, it is sufficient to set $k = C + 1$ .

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

define a fan of radius $k$ , degree $d$ , focused at $a$ , to be the $d -$ tuple $F =< a + [0, k] r_{j} >$ , for $1 \leq j \leq d$ .

The arithmetic progression $a + [1, k] r_{j}$ is the jth Spoke of the fan $F$ .

The defined fan $F$ is called polychromatic 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^{*} = c_{1}, c_{2}, . . c_{d} .$

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 + 2 D}, . . . . F_{1 + k D}$ (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 $0 D + F, 1 D + F, 2 D + F, . . ., k D + F$ . (The entirety of each of these fans live in completely disjoint blocks of $N)$ .

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

in particular, we have the series $a + k r_{j}, a + D + (k - 1) r_{j}, a + 2 D + (k - 2) r_{j}, . . ., a + k D + (k - k) r_{j}$

indeed, the above series is an arithmetic progression, $(a + k r_{j}) + [0, k] (D - r_{j})$ for each $1 \leq j \leq d$ . We will show that these AP’s could be the spokes of a new fan focused at $a + k D$ . ineed, all of our progressions are of the form $(a + k r_{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 + k D + [0, k] (r_{j} - D)$ . Indeed each of these $d$ progressions could be focused as spokes at $a + k D$ . but notice that even the basepoints of all our inital fans could also be focused at $a + k D!$ because our basepoints are of the form $a + k D + [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.

Untitled

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

Call the above argument the $f a n$ lemma.

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 $P H P$ , $W (n, 2) = n + 1$ . suppose for $k \geq 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 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.

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

suppose for some $d < n$ , there exists $M (d) \in 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 $f a n$ 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.

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.

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 $K [n]$ in $K [T]$ is less than or equal to $(\binom{T}{n}) 2^{1 - (\binom{n}{2})}$ .

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

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

so, in fact,

R (n, n) \geq \frac{n 2^{\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{n 2^{\frac{n}{2}}}{e \sqrt{2}}

Path Number:

define $P (m, n) = R (P [m], K [n])$ . that is the smallest number $R$ for which a red-blue coloring of the edges of $K [R]$ either contains a red $P [m]$ or a blue $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.

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

construct a red-blue coloring of $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^{*}) \geq P (m, n + 1)$

indeed, if we have a blue $K [n + 1]$ , we are done. if we have a red $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) \geq P (m + 1, n)$ .

if we have a red $P [m + 1]$ , we are done. if we have a blue $K [n]$ , $v$ is adjacent to $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) \leq (m - 1) (n - 1) + 1$ .

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

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

we will show that if $r < m i n ((m - 1) (n - 2)), ((m - 2, n - 1))$ , $P (m, n) \leq (m - 1) (n - 1) - r$ implies $P (m, n) \leq (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 $K [T^{'}]$ . indeed, suppose $P (m, n) \leq (m - 1) (n - 1) - r$ .

given that $r < m i n ((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 $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 = m i n ((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) \leq (m - 1) (n - 1) - (m - 2) (n - 1)$ . Hence, $P (m, n) \leq n - 1$ . Color all edges of $K [n - 1]$ blue. Then, we neither have a blue $K [n]$ nor a red $P [m]$ .

Similarly, let $m \geq n$ . Then, $r = (m - 1) (n - 2)$ . we get $P (m, n) \leq m - 1$ . color all edges of $K [m - 1]$ red. we neither have a blue $K [n]$ nor a red $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.

Define $P^{*} (a_{1}, a_{2}, . . . a_{n}) = R (P [a_{1}], P [a_{2}], . . ., P [a_{n}])$ .

Now, notice that $P (a_{1}, a_{2}, . . . a_{n}) \leq 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}) \leq \prod_{i = 1}^{n} (a_{i} - 1) + 1.$ Setting each $a_{i} = a$ , we obtain the desired result.

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_{i} v_{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.

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

then, define the color-density of $A$ to be the number of absolute differences in $A$ . (denoted by $γ (A)$ ). That is, $γ (A) = | {| a_{j} - a_{i} | : a_{j}, a_{i} \in A} |$ .

Now, if $| A | \geq ϕ (γ (A), k)$ , then $A$ contains a $k -$ length arithmetic progression. (by AP path number lemma).

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

Then, The density sequence of $A$ is $d_{N} = | A (N) | / N$ . hence, if for each $N$ , if $| A (N) | \geq ϕ (γ (A (N)), f (N))$ , then $A (N)$ contains at least a $f (N)$ length AP.

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

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

d_{N} (A) \geq \frac{ϕ (γ (A (N)), f (N))}{N}

conversely, if for some infinite set $A \subset N$ , eventually, the density sequence $d_{N} (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,

| A (N) | \geq ϕ (γ (A (N)), f (N))

Hence, by allowing $f (N)$ to be a horrendously slow growing (yet unbounded) function, and for good upper bounds on $γ$ it should be possible to make $A$ sparse. How sparse? that’s for another day. (of course $f (N)$ has to be eventually floored for $ϕ$ , 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) \geq ϕ (γ (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{ϕ (γ (A (n)), f (n))}{n} \leq \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) \geq 3$ . hence, $f (n + k) \geq 3$ , for all $n$ . hence, we have the following inequality:

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

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

I guess, the better idea is to first get good bounds on $γ (A (n)) .$ in particular, for a fixed $| A (n) |$ , what's the LARGEST $γ (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 $γ$ for that interval?

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

The other Erdos-Gallai Theorem:

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

Proof: supppose the longest path in $G$ is $P = v_{1}, v_{2}, . . . v_{m}$ . ( $m < n$ , because $m = n$ is trivial) Consider the induced subgraph of $G$ induced by $v_{1}, v_{2}, . . . v_{m}$ . call it $G (P)$ . we claim that $G (P)$ does not have a cycle with $m$ edges (notice that the cycle with $m$ edges in $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 $G (P)$ which is connected to the cycle in $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.

![Untitled](/img/user/Support/Figures/Untitled 1.png)

Now, also notice that in $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 $ω (G)$ neighbors in $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.

![Untitled](/img/user/Support/Figures/Untitled 2.png)

Hence, for every neighbor of $v_{m}$ in $P$ , there is a non neighbor of $v_{1}$ in $P$ . but there are at least $ω (G)$ neighbors of $v_{m}$ in $P$ . Therefore, there are at least $ω (G)$ non-neighbors of $v_{1}$ in $P$ . hence including $v_{m}$ , there are at least $2 ω (G) + 1$ vertices in $P .$

We could restate the proposition in the following way:

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

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

Lemma 2: Now, we claim that if $G$ is not connected, there exists a component $H$ of $G$ such that $⟨ H | \geq ⟨ G |$ .

Since there are no edges between (connected) components of $G$ , let $H_{i}$ for $i = 1$ to $p$ be all the components of $G$ . Now suppose that for each $i$ , $⟨ H_{i} | < ⟨ G |$ . that is, $2 | E (H_{i}) | / h_{i} < ⟨ G |$ . (Where $h_{i}$ is the order of $H_{i})$ . Hence, we have the following inequality:

2 \cdot \sum_{i = 1}^{p} | E (H_{i}) | < ⟨ G | \cdot \sum_{i = 1}^{p} h_{i}

Therefore, upon rearrangement, and noting that $\sum_{i = 1}^{p} | E (H_{i}) | = | E (G) |$ , and $\sum_{i = 1}^{p} h_{i} = n$ , we get the contradiction $⟨ G | < ⟨ G |$ .

Erdos-Gallai Theorem:

Any graph $G$ , must contain a path of length of at least $⟨ G |$ .

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

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

n ⟨ G | - (n - 1) ⟨ G - v | = 2 d (v) \leq ⟨ G |

⟨ G - v | \geq ⟨ G |

Hence, by the induction hypothesis, $G - v$ must contain a path of length at least $⟨ G - v | \geq ⟨ G |$ .

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

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

The original Erdos-Gallai Theorem was stated this way:

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

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

The OG upper-bound:

$ϕ (n, t) \leq n t$

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

Notice that there is a color class of size (number of edges) at least $t (n t - 1) / 2$ . Consider a subgraph which contains all vertices, and only the same-colored $t (n t - 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).