1 solved out of 6 shown (show only solved or open)
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 -$500
Let $\alpha\in[0,1/2)$ and $n,t\geq 1$. Let $F^{(t)}(n,\alpha)$ be the largest $m$ such that we can $2$-colour the edges of the complete $t$-uniform hypergraph on $n$ vertices such that if $X\subseteq [n]$ with $\lvert X\rvert \geq m$ then there are at least $\alpha \binom{\lvert X\rvert}{t}$ many $t$-subsets of $X$ of each colour.

For fixed $n,t$ as we change $\alpha$ from $0$ to $1/2$ does $F^{(t)}(n,\alpha)$ increase continuously or are there jumps? Only one jump?

For $\alpha=0$ this is the usual Ramsey function. A conjecture of Erdős, Hajnal, and Rado (see [562]) implies that $F^{(t)}(n,0)\asymp \log_{t-1} n$ and results of Erdős and Spencer imply that $F^{(t)}(n,\alpha) \asymp_\alpha (\log n)^{\frac{1}{t-1}}$ for $\alpha$ close to $1/2$.

Erdős believed there might be just one jump, occcurring at $\alpha=0$.

OPEN
Let $\alpha>0$ and $n\geq 1$. Let $F(n,\alpha)$ be the largest $k$ such that in any 2-colouring of the edges of $K_n$ any subgraph $H$ on at least $k$ vertices contains more than $\alpha\binom{\lvert H\rvert}{2}$ many edges of each colour.

Prove that for every fixed $0\leq \alpha \leq 1/2$, as $n\to\infty$, $F(n,\alpha)\sim c_\alpha \log n$ for some constant $c_\alpha$.

It is easy to show with the probabilistic method that there exist $c_1(\alpha),c_2(\alpha)$ such that $c_1(\alpha)\log n < F(n,\alpha) < c_2(\alpha)\log n.$
OPEN - $250 Give an asymptotic formula for$R(3,k)$. It is known that there exists some constant$c>0$such that for large$k$$c\frac{k^2}{\log k}\leq R(3,k) \leq (1+o(1))\frac{k^2}{\log k}.$ The lower bound is due to Kim [Ki95], the upper bound is due to Shearer [Sh83], improving an earlier bound of Ajtai, Komlós, and Szemerédi [AjKoSz80]. The lower bound has been improved to $\left(\frac{1}{4}-o(1)\right)\frac{k^2}{\log k}$ independently by Bohman and Keevash [BoKe21] and Pontiveros, Griffiths and Morris [PGM20]. The latter collection of authors conjecture that this lower bound is the true order of magnitude. See also [544]. SOLVED -$250
Prove that $R(4,k) \gg \frac{k^3}{(\log k)^{O(1)}}.$
Spencer [Sp77] proved $R(4,k) \gg (k\log k)^{5/2}.$ Ajtai, Komlós, and Szemerédi [AKS80] proved $R(4,k) \ll \frac{k^3}{(\log k)^2}.$ This is true, and was proved by Mattheus and Verstraete [MaVe23], who showed that $R(4,k) \gg \frac{k^3}{(\log k)^4}.$

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

OPEN
Let $F(n,\alpha)$ denote the largest $m$ such that there exists a $2$-colouring of the edges of $K_n$ so that every $X\subseteq [n]$ with $\lvert X\rvert\geq m$ contains more than $\alpha \binom{\lvert X\rvert}{2}$ many edges of each colour.

Prove that, for every $0\leq \alpha\leq 1/2$, $F(n,\alpha)\sim c_\alpha\log n$ for some constant $c_\alpha$ depending only on $\alpha$.

It is easy to show that, for every $0\leq \alpha\leq 1/2$, $F(n,\alpha)\asymp_\alpha \log n.$

Note that when $\alpha=0$ this is just asking for a $2$-colouring of the edges of $K_n$ which contains no monochromatic clique of size $m$, and hence we recover the classical Ramsey numbers.