Graph Ramsey Theory

Tight paths versus cliques

Let

$P_s$ denote a tight path of length

$s$ (meaning with

$s$ edges), i.e.,

$P_s = \{123, 234,345,\dots, s\ s+1\ s+2\}.$

E.g.,

$P_3 = \{123,234,345\}$

Known:

$\Omega(t^2/\log t) \le r_3(P_3, K_t) \le O(t^2)$

Add remark

Problem 1.02.

[Dhruv Mubayi] Improve the bounds. Is it

$o(t^2)$ ? Perhaps the lower bound is the truth.

Related results:

(Phelps–Rödl)

$r_3(P_2, K_t) = \Theta(t^2/\log t)$ . This is the same as giving the minimum independence number of a linear triple system on

$n$ points.

(Mubayi–Cooper)

$r_3(P_s,K_t) = \Theta(t^2)$ for fixed

$s \geq 4$

Here is the construction giving the lower bound for

$r_3(P_s,K_4)$ for

$s \geq 4$ . Consider the 3-uniform

$t^2$ -vertex hypergraph with the vertex set being points of a

$t \times t$ grid, i.e.,

$V = [t] \times [t]$ , and three points form an edge if and only if they form an L-shape, i.e.,

$\{(x_1,y_2),(x_1,y_1),(x_2,y_1)\} \quad \text{for all } 1 \le x_1 < x_2 \le t \text{ and } 1 \le y_1 < y_2 \le t.$ This hypergraph has independence number

$2t -1$ and is

$P_4$ -free.

Extensions to hypergraphs:

Fix uniformity

$k$ . Let

$P_s^{(k)}$ denote the tight

$k$ -uniform path of length

$s$ . So previously

$P_s$ meant

$P_s^{(3)}$ .

Known:

$\Omega(t^{k-1} / \log t) \le r_k(P_s^{(k)},K_t^{(k)}) \le O(t^{k-1})$ .

Question: Is it true that for fixed

$k$ , and

$s$ sufficiently large (in terms of

$k$ ), one has

$r_k(P_s^{(k)},K_t^{(k)}) = \Theta(t^{k-1})$ .

Remark. [Conlon] for what $H$ is $r_3(H, K_t)$ polynomial in $t$ ? E.g., is it so when $H$ is the Fano plane?
Remark. [Mubayi] (Samotij–Mubayi) If a $3$ -uniform hypergraph does not contain a copy of the Fano plane, then one can find a subset $S$ of vertices of polynomial size (i.e., $\geq |V|^\epsilon$ ) such that there is a partition $S = S_1 \cup S_2$ with $|S_1| = |S_2|$ where no triple has at least one vertex in both $S_1$ and $S_2$ .

Paths in 3-colorings of 6-chromatic graphs

$P_k$ denotes a path of length

$k$ , i.e., with

$k$ edges

Fact:

$r(P_3,P_3,P_3) = 6$

Add remark

Problem 1.04.

[András Gyárfás] Is it true that in any 3-edge-coloring of a graph of chromatic number at least 6, there is a monochromatic path of length 3?

Known: (Garrison) For

$k \ne 3$ , if we

$k$ -edge-color an

$\ell$ -chromatic graph and

$\ell \ge r(\underbrace{P_3,\dots,P_3}_{k \text{ times}})$ , then we get a monochromatic

$P_3$ . (That is,

$k=3$ is the only unknown case.)

Remark. For $k\ne 3$ , this follows from $\operatorname{ex}(n,P_3)\le n$ (look at the majority color).

4-color Ramsey number of triangles

Add remark

Problem 1.06.

[Fan Chung] Find

$r(3,3,3,3)$ . Is it 51?

Known:

$51 \le r(3,3,3,3) \le 62$ . Lower bound due to (Chung 1973), and upper bound due to (Fettes–Kramer–Radziszowski 2004).

Hypergraph size Ramsey numbers

The size Ramsey number

$\hat r(n,n)$ is the minimum number

$m$ for which there exists a graph with

$m$ edges such that every 2-edge-coloring of it produces a monochromatic

$K_n$ . Similarly define

$\hat r_3(n,n)$ for the corresponding 3-uniform size Ramsey number.

For graphs,

$\hat r (n,n) = \binom{r(n,n)}{2}$ .

Add remark

Problem 1.08.

[Andrzej Dudek] (Dudek–Rödl) Is

$\hat r_3(n,n) = \binom{r_3(n,n)}{3}$ ?

In particular,

Dudek–Rödl) Let

$N = r_3(n,n)$ . Is it true that every 2-edge-coloring of

$K_N^{(3)}-e$ contains a monochromatic

$K_n^{(3)}$ ? Here

$K_N^{(3)} - e$ denotes

$K_N^{(3)}$ with one edge deleted.

Lower bound: (Dudek–La Fleur–Mubayi–Rödl)

$\hat r_3(n,n) \ge \text{poly}(n) r_3(n,n)^2$

Remark. $r_3(4,4) = 13$ ( $\ge$ Seymour; $\le$ Radziszowski). So does it work for $n=4$ ? This is a matter of computational verification.

Online Ramsey numbers

The online Ramsey number

$\tilde r(s,n)$ is defined via a game as follows. Initially there are infinitely many vertices and no edges. Each turn, the builder adds an edge to the graph, and the painter colors the edge blue or red. We define

$\tilde r(s,n)$ to be the minimum

$m$ such that the builder can force a win in

$m$ moves, i.e., force a red

$K_s$ or a blue

$K_n$ .

Note:

$\tilde r(s,n) \le \hat r (s,n) = \binom{r(s,n)}{2}$ .

(Conlon) For infinitely many

$n$ ,

$\tilde r(n,n) \le (0.99)^n \binom{r(n,n)}{2}$ . The constant

$0.99$ can probably be made much smaller.

Note that if

$\tilde r(n,n) \ge (1.999)^n$ for all

$n$ , then

$r(n,n) \ge (\sqrt 2 + \delta)^n$ for some

$\delta > 0$ . This is a possible strategy for improving lower bounds on diagonal Ramsey numbers. More modestly, we can ask:

Add remark

Problem 1.1.

[Jacob Fox] Show that

$\tilde r(n,n) \ge (\sqrt 2 + \epsilon)^n$ for some

$\epsilon > 0$ .

Related: (Conlon–Fox–Grinshpun)

$\tilde r(3,n) = \tilde \Theta(n^3)$ , where

$\tilde\Theta$ means up to a

$\text{poly\,log}(n)$ factor. The lower bound is proved via a lopsided local lemma.

Erdős–Hajnal for tournaments

Let

$T^*$ denote the following tournament on

$6$ vertices labeled by

$\{1, 2, \dots, 6\}$ : orient

$6 \to 1, 6 \to 3, 5 \to 2, 4 \to 1$ , and orient all remaining pairs

$i \to j$ where

$i < j$ .

Add remark

Problem 1.12.

[Maria Chudnovsky] Does there exist

$\epsilon > 0$ such that if

$T_n$ is an

$n$ -vertex tournament not containing

$T^*$ as a subtournament, then

$T_n$ contains a transitive tournament with

$\ge n^\epsilon$ vertices?

Remark. [Berger–Choromanski–Chudnovsky] This is the smallest tournament for which this conclusion is not known.
Remark. Such a statement for all tournaments is equivalent to the Erd\H os–Hajnal conjecture.

Local trees of triangles

A tree of triangles is any graph built recursively by starting with a triangle, and then adding two edges at a time that forms a single new triangle with an existing edge.

Known: Given any tree

$T$ of triangles, there exists

$k$ such that if

$G \xrightarrow{k} K_3$ (the

$k$ above the arrow means with

$k$ colors), then

$G$ contains

$T$ .

Add remark

Problem 1.14.

[Vojte̋ch Rödl] For every

$\ell$ , does there exist a graph

$G \xrightarrow{2} K_3$ which on every

$\ell$ vertices induces a subgraph of a tree of triangles.

The property in the conclusion of the question will be referred to as locally a tree of triangles.

Does there exist any finite graph where every edge is in at least two triangles and the graph is locally a tree of triangles? (Solved by J. Verstraete)

(Nes̋etr̋il–Rödl) Partial results

Ramsey minimal graphs

Let

$G \xrightarrow{r} K_k$ be minimal, i.e.,

$G - e \not\xrightarrow{r} K_3$ for any

$e \in E(G)$ . Let

$\mathcal{M}_r(k)$ denote the family of such graphs

$G$ . Let

$s_r(k) = \min\{\delta(G) : G \in \mathcal{M}_r(k)\}$ where

$\delta(G)$ is the minimum degree of

$G$ .

Add remark

Conjecture 1.16.

[Tibor Szabó] Conjecture: (Fox–Grinshpun–Liebenau–Person–Szabó)

$s_r(k) \le s_r(k+1)$ for all

$k$ .

Results:

$s_2(k) = (k-1)^2$ (Erd\H os–Burr–Lovász 1976)

$\Omega(r^2 \log r) \le s_r(3) \le O(r^2(\log r)^2 )$

$\Omega\left(\frac{r^2 \log r }{ \log\log r}\right) \le s_r(k) \le O\left(r^2 (\log r)^{8(k-1)^2}\right)$ for

$k \ge 4$

Conjecture: (Fox–Grinshpun–Liebenau–Person–Szabó)

$s_r(k) = \Theta(r \cdot f_{k,k+1}(r)^2)$ where

$f_{k,k+1}$ is the Erdős-Rogers function, to be discussed in Dudek’s talk.

Conjecture:

$s_r(3) = \Theta(r^2 \log r)$

Remark. This would follow from the extension of the triangle-free process to $r$ colors.

Ramsey numbers of knots

Theorem. (Negami) Fix a knot

$K$ . If

$n$ if large enough, any linear spatial embedding of

$K_n$ contains

$K$ .

Linear spatial embedding of a graph means placing the vertices of the graph in

$\mathbb{R}^3$ and drawing edges as straight lines between the vertices.

“Contains” would mean either \\ (i) a cycle homeomorphic to

$K$ , or \\ (ii) a cycle isotopic to

$K$ \\ The distinction is that (ii) does not allow reflections.

Known: Any linear spatial embedding of

$K_7$ contains a homeomorphic copy of a trefoil knot.

Add remark

Problem 1.18.

[David Conlon] If

$K$ has

$k$ crossings, how big does

$n = n(k)$ have to be?

Known: (Negami) at most 5-fold exponential

(Conlon–Fox)

$n(k) \le 2^{2^{ck}}$

Question: Is it polynomial in

$k$ ?

Lower bound:

$n(K) \ge \sqrt{\nu(K)}$ , where

$\nu(K)$ is the crossing number of a knot.

We can also ask the same question for links. For the simplest nontrivial link of two unknots (i.e., Hopf link), the answer is 6.

Semi-algebraic Ramsey numbers

Suppose that that for each

$n$ we have a

$k$ -uniform hypergraph

$H_n$ where

$V(H_n)$ is a set of

$n$ points in the plane, say

$V(H_n) = \{v_1, \dots, v_n\} \subseteq \mathbb{R}^2$ , and the edges are defined by a

$2k$ -variable polynomial

$f$ , namely

$\{v_{i_1}, \dots, v_{i_k}\} \in E(H_n) \Leftrightarrow f(v_{i_1},\dots, v_{i_k}) \ge 0, \qquad i_1 < i_2 < \dots < i_k.$

Add remark

Problem 1.2.

[Andrew Suk] What is the size of the largest homogeneous set (i.e., clique or independent set) that is guaranteed to exist in every such

$H_n$ ?

Let

$r_f(n) = \min_{H_n} \max\{\alpha(H_n), \omega(H_n)\}$ denote the above quantity.

Known: From bounds on Ramsey numbers we have

$r_f(n) \ge c \underbrace{\log \dots \log}_{k-1 \text{ times}} n$ .

Question: (Bukh–Matous̋ek) Can this be improved to a constant number of logs?

Known: (Bukh–Matous̋ek) In dimension 1, two logs suffice, and this is tight.

(Conlon–Fox–Pach–Sudakov–Suk)

$r_f(n) \ge c \underbrace{\log \dots \log}_{k-2 \text{ times}} n$ .

If the dimension is high enough, this is sharp (i.e., in

$\mathbb{R}^{c(k)}$ ).

Variant: Unbalanced version

$R_f^{(k)}(s,n)$ , where the superscript means

$k$ -uniform.

Problem: (Conlon–Fox–Pach–Sudakov–Suk) Is

$R_f^{(3)}(4,n)$ polynomial in

$n$ ?

Results: (Suk)

$R_f^{(3)}(4,n) = e^{e^{O(\sqrt{\log n})}}$ . (Clearly

$R_f^{(3)}(4,n) = 2^{O(n^2\log n)}$ from Ramsey number bounds).

Motivation:

$R_f^{(4)}(5,n)$ connected to Erdős-Szekeres problem on

$n$ points in convex position.

Question: (Fox) Is

$R_f^{(2)}(3,n) = n^{1 + o(1)}$ ?

Large cliques in straight edge intersection graphs

Add remark

Problem 1.22.

[János Pach] If

$K_n$ is drawn in the plane with straight line edges, can we always find

$\Omega(n)$ pairwise crossing edges?

Known: (Aronov–Erd\H{os}–Kleitman–Pach) Can get

$\Omega(\sqrt{n})$ .

Results: (Csaba–Fox–Pach) For some

$\epsilon > 0$ , if edges are curves and each pair crosses

$O(1)$ times, then we get

$\Omega(n^{\epsilon})$ pairwise crossing curves.

Chromatic number of graphs with everywhere high independence number

Add remark

Problem 1.24.

[Jacque Verstraete] Is there an

$\epsilon > 0$ so that

$\chi(G) \le d^{1-\epsilon}$ for every graph

$G$ of maximum degree

$d$ such that

$\alpha(H) \geq \frac13 |V(H)|$ for every subgraph

$H \subseteq G$ ?

Motivation: Kneser graphs

$KG_{3n,n}$ satisfies the constraint and has chromatic number

$\Theta(\log d)$ .

Note that any graph satisfying the constraint is

$K_4$ -free, and it is known (Shearer) that

$\alpha(G) \ge \frac{cn\log d}{d \log\log d}$ if

$G$ is

$K_4$ -free, and hence

$\chi(G) \le \frac{n}{\alpha(G)} \le \frac{d \log\log d}{c \log d}$ .

Burr–Erdős for hypergraphs

A graph

$G$ is \emph{

$d$ -degenerate} if every

$H \subseteq G$ has

$\delta(H)\le d$ .

Conjecture: (Burr–Erdős)

$r(G,G) \le c(d) n$ if

$G$ is an

$n$ -vertex

$d$ -degenerate graph.

Known: (Kostochka–Sudakov)

$r(G,G) \le n^{1+o_d(1)}$ .

If

$G$ is a 3-uniform

$d$ -degenerate hypergraph, the statement can be false. There is a 1-degenerate 4-uniform

$G$ such that

$r_4(G,G) \ge 2^{\Omega(n^{1/3})}$ .

Perhaps we can redefine degeneracy for

$k$ -uniform hypergraphs: call a

$k$ -uniform hypergraph

$d$ -degenerate if the 2-graph obtained by replacing every edge by a graph clique

$K_k^{(2)}$ is

$d$ -degenerate as a graph.

Add remark

Problem 1.26.

[Jacob Fox] (Conlon–Fox–Sudakov) Is

$r_f(H,H) \le c_k(d) n$ for all

$n$ -vertex

$d$ -degenerate (in the above sense)

$k$ -uniform hypergraph

$H$ ?

Cycle versus cliques

Easy:

$r(C_m, K_n) \ge (m-1)(n-1) + 1$ .

Conjecture: (Erdős)

$r(C_m, K_n) = (m-1)(n-1) + 1$ if

$m \ge n$ .

Known: (Bondy–Erdős 1973) True if

$m \ge n^2$ . (Nikiforov) True if

$m \ge 4n + 6$ .

Add remark

Problem 1.28.

[Jozef Skokan] Why should

$m \ge n$ ?

Easy:

$r(P_m,K_n) = (m-1)(n-1) + 1$ for all

$m, n$ .

Local conditions for distinct distances

Add remark

Problem 1.3.

[Andrew Suk] Question: (Erdős 1986) What is the least possible number of distinct distances among

$n$ points in the plane if every 5 of them span at least 9 distinct distances?

Conjecture:

$\Omega(n^2)$

Best known:

$\Omega(n)$ .

Related to

$F(r,s,9)$ .

Ramsey number of simplices

Add remark

Problem 1.32.

[Jacob Fox] Estimate

$r_k(k+1) := r_k(k+1,k+1)$ .

Bounds:

$2^{\Omega(k)} \le r_k(k+1) \le 2^{2^{.^{.^{.^{2^C}}}}}$ , where the tower of

$2$ ’s has height

$\approx k$ .

C.f. (Duffus–Lefmann–Rödl) for

$r_k(k+2)$ .

Hypergraph triangles versus cliques

Known: (Kim, Ajtai–Komlós–Szemerédi)

$r(3,t) = \Theta(t^2/\log t)$ .

Let

$\triangle$ denote the 3-uniform hypergraph with vertex set

$[6]$ and edges

$\{123,345,561\}$ .

Known:

$\Omega\left(\frac{t^{3/2}}{(\log t)^{3/4}}\right) = r_3(\triangle, K_t^{(3)}) = O(t^{3/2})$

Add remark

Conjecture 1.34.

[Jacque Verstraete] (Kostochka–Mubayi–Verstraete)

$r_3(\triangle, K_t^{(3)}) = o(t^{3/2})$ .

Ramsey goodness for hypergraphs

A graph

$G$ is \emph{

$t$ -good} if

$r(G,K_t) = (t-1)(v(G) - 1) + 1.$

$G$ is \emph{

$H$ -good} is

$r(G, H) = (\chi(H)-1)(v(G) - 1) + \sigma(H)$ where

$\sigma(H)$ is the size of the smalles color class in any

$\chi(H)$ -coloring of

$H$ .

Intuition: graphs that are

$H$ -good tend to be poor expanders.

\medskip

Let

$F$ denote the Fano plane. A 3-uniform hypergraph

$H$ is \emph{

$F$ -good} if

$r(H,F) = 2(v(H)-1) + 1.$ Construction giving

$\ge$ :

$v(H)-1$ vertices on the left,

$v(H)-1$ vertice on the right, color an edge red if it stays in one part, and blue if it contains vertices in both parts.

Add remark

Problem 1.36.

[Ramsey goodness for hypergraphs] Which

$H$ are

$F$ -good?

Increasing paths in edge labelings

Label the edges of

$K_n$ with numbers

$1, 2, \dots, \binom{n}{2}$ . For each

$v \in V(K_n)$ , let

$t(v)$ be the length of the longest increasing path from

$v$ .

Add remark

Problem 1.38.

[Ron Graham] Is it true that

$\max_v t(v) \ge cn$ for some

$c > 0$ ?

Furthermore, is it true that for any graph

$G$ , edges labeled

$1, 2, \dots, |E(G)|$ , we always have

$\sum_{v \in V(G)} t(v) \ge |E(G)|$ ?

Known: (Calderbank–Chung–Sturtevant 1984). There exists a labeling with

$\max_v t(v) \le n/2$ .

Known: (Graham–Kleitman 1973)

$\max_v t(v) \ge (1+o(1)) \sqrt{n}$ for

$K_n$

Recently claimed to be improved to

$\ge (\sqrt{2} + o(1)) \sqrt{n}$ by a group of graduate students.

Directed paths in Eulerian digraphs

The following is a special case of a conjecture of Bollobás and Scott on weighted paths in directed graphs (see: A proof of a conjecture of Bondy concerning paths in weighted digraphs. J. Combin. Theory Ser. B 66 (1996), no. 2, 283–292):

Add remark

Problem 1.4.

[Jacques Verstraete] Does every Eulerian digraph of average degree

$d$ have a directed path of length

$\Omega(d)$ ?

Getting

$\Omega(\sqrt{d})$ is not too hard.

Ordered Ramsey numbers

An ordered graph on

$N$ vertices is a graph whose vertices have been labeled with

$\{1,\dots,N\}$ . We say that an ordered graph

$G$ on

$\{1,\dots,N\}$ contains another ordered graph

$H$ on

$\{1,\dots,n\}$ if

$H$ occurs as a subgraph of

$G$ with vertices appearing in the correct order.

Let

$r_<(H)$ denote the minimum

$N$ such that every 2-edge coloring of

$K_N$ contains a monochromatic ordered copy of

$H$ . Similarly for

$r_<(H_1, H_2)$ .

Add remark

Problem 1.42.

[David Conlon, Jacob Fox, Choongbum Lee, and Benny Sudakov] Does there exist

$\epsilon > 0$ such that

$r_<(K_3,M) = O(n^{2-\epsilon})$ for every ordered matching

$M$ on

$n$ vertices.

Known:

$r_<(K_3, M) \le r_< (K_3, K_n) = \Theta(n^2/\log n)$ .

Known: There exists an ordered matching

$M$ on

$n$ vertices such that

$r_<(K_3, M) = n^{4/3 + o(1)}$ .

Question: Does there exist a constant

$c > 0$ such that for every sufficiently large

$n$ there exists a 100-regular graph

$H$ on

$n$ vertices such that

$r_<(H) \ge n^{1 + c}$ for every ordering of

$H$ ?

Ramsey meets Erdős–Szekeres

Let

$g(s,n)$ be the minimum

$N$ such that for every set of

$N$ points in general position in the plane, and every red/blue coloring of the pairs, there are

$s$ points in convex position, with all pairs red, or

$n$ points in convex position with all pairs blue.

Known:

$4^n < g(n,n) < 2^{O( n^2 \log n)}$

$2^{n-1} < g(s,n) < r(4^s, 4^n) < (4^n)^{4^s}$

Add remark

Problem 1.44.

[Dhruv Mubayi] Improve these bounds.

Euclidean Ramsey sets

Let

$X$ be a finite set in

$\mathbb{E}^n$ (

$n$ -dimensional Euclidean space). We say that

$X$ is Ramsey if for all positive integers

$r$ there exists

$N = N(X,r)$ such that if one colors the points of

$\mathbb{E}^N$ with

$r$ colors, then there exists a monochromatic set congruent to

$X$ .

For example, if

$X$ consist of two points, then

$X$ is Ramsey. (Consider an

$r$ -coloring of the

$2r+1$ vertices of a unit simplex simplex in

$\mathbb{E}^{2r}$ ).

A set is spherical if it lies on some sphere.

Theorem. (Erdős–Graham–Montgomery–Rothschild–Spencer–Straus). Every Ramsey set is spherical.

Conjecture. ($1000) Every finite spherical set is Ramsey. A ``warm up'': \textbf{Conjecture.} ($100) Every 4-point subset of a circle is Ramsey. A rival conjecture: \textbf{Conjecture.} (Leader--Russell--Walters) A finite set is Ramsey if and only if it is a subset of some set with a transitive symmetry group. For 3-point sets: \textbf{Conjecture.} Let

$T$ be a set of three points in

$\mathbb{E}^2$ . Then there exists a 3-coloring of

$\mathbb{E}^2$ with no monochromatic copy of

$T$ . \textbf{Conjecture.} In any 2-coloring of

$\mathbb{E}^2$ , every 3-point set

$X$ occurs monochromatically (as some congruent copy), except possibly for the three points that form some specific equilateral triangle. (Example coloring: half-open horizontal stripes of height

$\sqrt{3}/2$ in alternating colors will stop the three vertices of a unit equilateral triangle from occurring monochromatically). \emph{Known:} If

$T$ is a set of 3 collinear points, then there exists a 16-coloring of

$\mathbb{E}^N$ with no monochromatic copy of

$T$ .

Add remark

Problem 1.46.

[Ron Graham] What is the minimum number of colors needed above?

Folkman graphs

A Folkman graph is a

$K_4$ -free graph such that every 2-edge-coloring contains a monochromatic triangle.

Folkman showed that such a graph exists, but he required an enormous number of vertices. Proofs of existence of smaller Folkman graphs were given by Frankl–Rödl, Spencer, Lu, Dudek–Rödl, Lange–Radziszowski–Xu.

Add remark

Problem 1.48.

[Ron Graham] ($100) Find a Folkman graph with fewer than 100 vertices.

Candidate construction: (Exoo) take

$\mathbb{Z}_{127}$ as vertices, and join

$i$ with

$j$ if

$i-j$ is a cubic residue mod 127, and then delete 33 vertices (three independent sets of size 11).

van der Waerden numbers

Let

$W(n,m)$ denote the least

$N$ so that any red/blue coloring of

$\{1, \dots, N\}$ contains either a red

$n$ -term arithmetic progression or a blue

$m$ -term arithmetic progression.

Let

$W(n) = W(n,n)$ .

Some data:

$\begin{tabular}{c|ccccc} $n$ & 2 & 3 & 4 & 5 & 6 \\ \hline $W(n)$ & 3 & 9 & 35 & 178 & 1132 \end{tabular}$

Known: (Berlekamp)

$W(n+1) \ge n 2^n$ for

$n$ prime.

(Gowers)

$W(n) \le 2^{2^{2^{2^{2^{n+9}}}}}$ .

Conjecture: ($1000)

$W(n) \le 2^{n^2}$ . Let

$W^*(n)$ denote the size of the smallest subset

$S$ of

$\mathbb{N}$ such that any 2-coloring of

$S$ has a monochromatic

$n$ -term arithmetic progression. \emph{Known:} (Elkies)

$W^*(3) = W(3).$

$W^*(4) \le 27 < W(4) = 35.$

Add remark

Problem 1.5.

[Ron Graham] Does

$W(n) - W^*(n) \to \infty$ ?

\medskip

Off diagonal van der Waerden numbers

$W(k,3)$

From computed values,

$W(k,3)$ seems to grow quadratically in

$k$ .

Known:

$k^{2-o(1)} < W(k) < e^{O(k \log^5 k)}$ .

Question: Does

$W(k)$ grow polynomially in

$k$ ?

Graph Ramsey Theory

1. First Section

Tight paths versus cliques

Problem 1.02.

Paths in 3-colorings of 6-chromatic graphs

Problem 1.04.

4-color Ramsey number of triangles

Problem 1.06.

Hypergraph size Ramsey numbers

Problem 1.08.

Online Ramsey numbers

Problem 1.1.

Erdős–Hajnal for tournaments

Problem 1.12.

Local trees of triangles

Problem 1.14.

Ramsey minimal graphs

Conjecture 1.16.

Ramsey numbers of knots

Problem 1.18.

Semi-algebraic Ramsey numbers

Problem 1.2.

Large cliques in straight edge intersection graphs

Problem 1.22.

Chromatic number of graphs with everywhere high independence number

Problem 1.24.

Burr–Erdős for hypergraphs

Problem 1.26.

Cycle versus cliques

Problem 1.28.

Local conditions for distinct distances

Problem 1.3.

Ramsey number of simplices

Problem 1.32.

Hypergraph triangles versus cliques

Conjecture 1.34.

Ramsey goodness for hypergraphs

Problem 1.36.

Increasing paths in edge labelings

Problem 1.38.

Directed paths in Eulerian digraphs

Problem 1.4.

Ordered Ramsey numbers

Problem 1.42.

Ramsey meets Erdős–Szekeres

Problem 1.44.

Euclidean Ramsey sets

Problem 1.46.

Folkman graphs

Problem 1.48.

van der Waerden numbers

Problem 1.5.