All Random Solved Random Open
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].

See also the entry 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$.

See also the entry on the graphs problem collection.

Additional thanks to: Jesse Goodman, Mehtaab Sawhney
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.
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.
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'.
Additional thanks to: Zachary Chase
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.