1. First Section

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)$Problem 1.02.
[Dhruv Mubayi] Improve the bounds. Is it $o(t^2)$? Perhaps the lower bound is the truth.
Related results:
(Phelps–Rö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 3uniform $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 Lshape, 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.
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^{k1} / \log t) \le r_k(P_s^{(k)},K_t^{(k)}) \le O(t^{k1})$.
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^{k1})$.
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 3colorings of 6chromatic graphs
$P_k$ denotes a path of length $k$, i.e., with $k$ edges
Fact: $r(P_3,P_3,P_3) = 6$Problem 1.04.
[András Gyárfás] Is it true that in any 3edgecoloring of a graph of chromatic number at least 6, there is a monochromatic path of length 3?
Remark. For $k\ne 3$, this follows from $\operatorname{ex}(n,P_3)\le n$ (look at the majority color).


4color Ramsey number of triangles
Problem 1.06.
[Fan Chung] Find $r(3,3,3,3)$. Is it 51? 
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 2edgecoloring of it produces a monochromatic $K_n$. Similarly define $\hat r_3(n,n)$ for the corresponding 3uniform size Ramsey number.
For graphs, $\hat r (n,n) = \binom{r(n,n)}{2}$.Problem 1.08.
[Andrzej Dudek] (Dudek–Rödl) Is $\hat r_3(n,n) = \binom{r_3(n,n)}{3}$?
In particular,
Dudek–Rödl) Let $N = r_3(n,n)$. Is it true that every 2edgecoloring 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–Rö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:Problem 1.1.
[Jacob Fox] Show that $\tilde r(n,n) \ge (\sqrt 2 + \epsilon)^n$ for some $\epsilon > 0$. 
Erdő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$.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$.Problem 1.14.
[Vojte̋ch Rö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–Rö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$.Conjecture 1.16.
[Tibor Szabó] Conjecture: (Fox–Grinshpun–Liebenau–Person–Szabó) $s_r(k) \le s_r(k+1)$ for all $k$.
Results: $s_2(k) = (k1)^2$ (Erd\H os–Burr–Lová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(k1)^2}\right)$ for $k \ge 4$
Conjecture: (Fox–Grinshpun–Liebenau–Person–Szabó) $s_r(k) = \Theta(r \cdot f_{k,k+1}(r)^2)$ where $f_{k,k+1}$ is the ErdősRogers 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 trianglefree 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.Problem 1.18.
[David Conlon] If $K$ has $k$ crossings, how big does $n = n(k)$ have to be?
Known: (Negami) at most 5fold 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. 
Semialgebraic 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. \]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}_{k1 \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}_{k2 \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$?
Motivation: $R_f^{(4)}(5,n)$ connected to ErdősSzekeres 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
Problem 1.22.
[János Pach] If $K_n$ is drawn in the plane with straight line edges, can we always find $\Omega(n)$ pairwise crossing edges?
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
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)$. 
Burr–Erdős for hypergraphs
A graph $G$ is \emph{$d$degenerate} if every $H \subseteq G$ has $\delta(H)\le d$.
Conjecture: (Burr–Erdő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 3uniform $d$degenerate hypergraph, the statement can be false. There is a 1degenerate 4uniform $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 2graph obtained by replacing every edge by a graph clique $K_k^{(2)}$ is $d$degenerate as a graph.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 (m1)(n1) + 1$.
Conjecture: (Erdős) $r(C_m, K_n) = (m1)(n1) + 1$ if $m \ge n$.
Known: (Bondy–Erdős 1973) True if $m \ge n^2$. (Nikiforov) True if $m \ge 4n + 6$.Problem 1.28.
[Jozef Skokan] Why should $m \ge n$? 
Local conditions for distinct distances
Problem 1.3.
[Andrew Suk] Question: (Erdő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?
Best known: $\Omega(n)$.
Related to $F(r,s,9)$. 
Ramsey number of simplices
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–Rödl) for $r_k(k+2)$. 
Hypergraph triangles versus cliques
Known: (Kim, Ajtai–Komlós–Szemerédi) $r(3,t) = \Theta(t^2/\log t)$.
Let $\triangle$ denote the 3uniform 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})$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) = (t1)(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 3uniform 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.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$.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: (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 Bollobá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):Problem 1.4.
[Jacques Verstraete] Does every Eulerian digraph of average degree $d$ have a directed path of length $\Omega(d)$? 
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 2edge coloring of $K_N$ contains a monochromatic ordered copy of $H$. Similarly for $r_<(H_1, H_2)$.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 100regular graph $H$ on $n$ vertices such that $r_<(H) \ge n^{1 + c}$ for every ordering of $H$? 
Ramsey meets Erdő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^{n1} < g(s,n) < r(4^s, 4^n) < (4^n)^{4^s}$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. (Erdő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 4point subset of a circle is Ramsey. A rival conjecture: \textbf{Conjecture.} (LeaderRussellWalters) A finite set is Ramsey if and only if it is a subset of some set with a transitive symmetry group. For 3point sets: \textbf{Conjecture.} Let $T$ be a set of three points in $\mathbb{E}^2$. Then there exists a 3coloring of $\mathbb{E}^2$ with no monochromatic copy of $T$. \textbf{Conjecture.} In any 2coloring of $\mathbb{E}^2$, every 3point set $X$ occurs monochromatically (as some congruent copy), except possibly for the three points that form some specific equilateral triangle. (Example coloring: halfopen 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 16coloring of $\mathbb{E}^N$ with no monochromatic copy of $T$.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 2edgecoloring 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–Rödl, Spencer, Lu, Dudek–Rödl, Lange–Radziszowski–Xu.Problem 1.48.
[Ron Graham] ($100) Find a Folkman graph with fewer than 100 vertices. 
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}{cccccc} $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 2coloring of $S$ has a monochromatic $n$term arithmetic progression. \emph{Known:} (Elkies) $W^*(3) = W(3).$ $W^*(4) \le 27 < W(4) = 35.$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^{2o(1)} < W(k) < e^{O(k \log^5 k)}$.
Question: Does $W(k)$ grow polynomially in $k$?
Cite this as: AimPL: Graph Ramsey Theory, available at http://aimpl.org/graphramsey.