0 solved out of 6 shown

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

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

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

OPEN

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.
Is $c(3m+2)=3^m$? Does $c(n)^{1/n}\to \alpha$ for some $\alpha <2$?

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

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.