Graph Ramsey Theory

    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)$

    $P_k$ denotes a path of length $k$, i.e., with $k$ edges

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

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

    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:

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

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

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

    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.

    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. \]

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

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

Conjecture: (Erdős) $r(C_m, K_n) = (m-1)(n-1) + 1$ if $m \ge n$.

Known: (Bondy–Erdős 1973) True if $m \ge n^2$. (Nikiforov) True if $m \ge 4n + 6$.

    Known: (Kim, Ajtai–Komlós–Szemeré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})$

    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.

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

    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):

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

    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}$

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

    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–Rödl, Spencer, Lu, Dudek–Rödl, Lange–Radziszowski–Xu.

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