OPEN - $250

Find the value of $\lim_{k\to \infty}R(k)^{1/k}$.

Erdős offered \$100 for just a proof of the existence of this constant, without determining its value. He also offered \$1000 for a proof that the limit does not exist, but says 'this is really a joke as [it] certainly exists'. Erdős proved
\[\sqrt{2}\leq \liminf_{k\to \infty}R(k)^{1/k}\leq \limsup_{k\to \infty}R(k)^{1/k}\leq 4.\]
The upper bound has been improved to $4-\tfrac{1}{128}$ by Campos, Griffiths, Morris, and Sahasrabudhe [CGMS23].

This problem is #3 in Ramsey Theory in the graphs problem collection.

OPEN - $100

Give a constructive proof that $R(k)>C^k$ for some constant $C>1$.

Erdős gave a simple probabilistic proof that $R(k) \gg k2^{k/2}$.
Equivalently, this question asks for an explicit construction of a graph on $n$ vertices which does not contain any clique or independent set of size $\geq c\log n$ for some constant $c>0$. Cohen [Co15] (see the introduction for further history) constructed a graph on $n$ vertices which does not contain any clique or independent set of size
\[\geq 2^{(\log\log n)^{C}}\]
for some constant $C>0$. Li [Li23b] has recently improved this to
\[\geq (\log n)^{C}\]
for some constant $C>0$.

This problem is #4 in Ramsey Theory in the graphs problem collection.

OPEN

Let $G$ be a graph of maximum degree $\Delta$. Is $G$ the union of at most $\tfrac{5}{4}\Delta^2$ sets of strongly independent edges (sets such that the induced subgraph is the union of vertex-disjoint edges)?

Asked by Erdős and Nešetřil in 1985 (see [FGST89]). This bound would be the best possible, as witnessed by a blowup of $C_5$. The minimum number of such sets required is sometimes called the strong chromatic index of $G$.

The weaker conjecture that there exists some $c>0$ such that $(2-c)\Delta^2$ sets suffice was proved by Molloy and Reed [MoRe97], who proved that $1.998\Delta^2$ sets suffice (for $\Delta$ sufficiently large). This was improved to $1.93\Delta^2$ by Bruhn and Joos [BrJo18] and to $1.835\Delta^2$ by Bonamy, Perrett, and Postle [BPP22].

Erdős and Nešetřil also asked the easier problem of whether $G$ containing at least $\tfrac{5}{4}\Delta^2$ many edges implies $G$ containing two strongly independent edges. This was proved independently by Chung-Trotter and Gyárfás-Tuza.

SOLVED

A minimal cut of a graph is a minimal set of vertices whose removal disconnects the graph. Let $c(n)$ be the maximum number of minimal cuts a graph on $n$ vertices can have.

Does $c(n)^{1/n}\to \alpha$ for some $\alpha <2$?

Asked by Erdős and Nešetřil, who also ask whether $c(3m+2)=3^m$. Seymour observed that $c(3m+2)\geq 3^m$, as seen by the graph of $m$ independent paths of length $4$ joining two vertices.

Solved by Bradač [Br24], who proved that $\alpha=\lim c(n)^{1/n}$ exists and \[\alpha \leq 2^{H(1/3)}=1.8899\cdots,\] where $H(\cdot)$ is the binary entropy function. Seymour's construction proves that $\alpha\geq 3^{1/3}=1.442\cdots$. Bradač conjectures that this lower bound is the true value of $\alpha$.

OPEN

Let $h(n)$ be minimal such that, for every graph $G$ on $n$ vertices, there is a set of vertices $X$ of size $\lvert X\rvert\leq h(n)$ such that every maximal clique (on at least $2$ vertices) in $G$ contains at least one vertex from $X$.
Let $H(n)$ be maximal such that every triangle-free graph on $n$ vertices contains an independent set on $H(n)$ vertices.
Does $h(n)=n-H(n)$?

It is easy to see that $h(n)\leq n-\sqrt{n}$ and that $h(n)\leq n-H(n)$. Conjectured by Erdős and Gallai, who were unable to make progress even assuming $G$ is $K_4$-free. Erdős remarked that this conjecture is 'perhaps completely wrongheaded'.

OPEN

If $G$ is a graph with at most $k$ edge disjoint triangles then can $G$ be made triangle-free after removing at most $2k$ edges?

A problem of Tuza. It is trivial that $G$ can be made triangle-free after removing at most $3k$ edges. The examples of $K_4$ and $K_5$ show that $2k$ would be best possible.