Let $R_r(k)$ denote the diagonal $r$-colour Ramsey number. We prove that there exist absolute constants $c,K>0$ such that $R_r(k)\le r^{rk}\exp\!\left(-c\frac{k}{r\log^2(2r)}\right)$ for every $r\ge2$ and every $k\ge Kr^2\log^6(2r)$. This improves the exponential saving in a recent bound of Yang and Mao by a factor of order $r\log^2(2r)$. The proof proceeds through an off-diagonal bound, which asymptotically improves the classical multinomial bound throughout a neighbourhood of the diagonal.
In this paper we determine the Ramsey number $R(3,3,k)$ up to a constant factor, showing that $$R(3,3,k) = \Theta\bigg( \frac{k^3}{(\log k)^2} \bigg).$$ The proof of the lower bound combines the Hefty-Horn-King-Pfender construction for $R(3,k)$ with the method of Alon and R\"odl. Using the same proof, we also determine...
Bruno Andrades, Marcelo Campos, Robert Morris· 0 citations
We prove that there is an absolute positive constant $c$ such that every bipartite graph with $N$ vertices in each part and at least $N^2/2$ edges contains a complete bipartite graph $K_{t,t}$ whenever $N\ge c\, 2^{t}$. This improves the classical K\H{o}v\'ari-S\'os-Tur\'an bound requiring $N$ of order $t\,2^t $. As a...
We provide an explicit algebraic construction showing that, uniformly for integers $3 \leq s \leq t$, as $t \to \infty$, \[ R( s,t ) \geq t^{(1-o(1)) \log s / \log(\log s + 1) }. \] For large fixed $s$, this improves the dependence on $s$ in the general off-diagonal construction of Alon and Pudl\'ak. In particular, $R(...
We exhibit two explicit circulant graphs of prime order $251$ that are $K_4$-free and have independence number $19$. Consequently \[R(4,20)\ge 252.\] These improve the bound $R(4,20)\ge 237$ given by Nagda, Raghavan, Thakurta and the long standing bound $R(4,21)\ge 242$ recorded in Radziszowski's dynamic survey. The gr...
The van der Waerden number $w(k)$ is the smallest positive integer $N$ such that every two-coloring of $\{1,2,\ldots,N\}$ contains a monochromatic $k$-term arithmetic progression. We prove that $w(k) \geq (1-o(1))k2^{k-1}$ holds for all positive integers $k$. This verifies a conjecture of Erd\H{o}s. In 1968, Berlekamp...
Marcelo Campos, Jacob Fox, C. Schildkraut· 0 citations
Let $f(k)$ denote the smallest integer such that every oriented graph $D$ with chromatic number at least $f(k)$ contains every oriented tree on $k$ vertices. Burr (1980) showed that $f(k)\le (k-1)^2$ and conjectured that $f(k)=2k-2$. Bessy, Gon\c{c}alves and Reinald (2025) proved that $f(k)=O(k^{3/2})$. In this paper,...
