In a recent breakthrough, OpenAI proved that the $k$-color Ramsey number of the triangle $C_3$ grows super-exponentially, more precisely, they proved that $R_k(C_3)\ge k^{k/3-o(k)}$. In this short note, we present a modification of their recursive construction that works for multicolor Ramsey numbers of fixed odd cycles. More precisely, for $p\ge 1$, let $\mathcal{O}_p=\{C_3,C_5,\ldots,C_{2p+1}\}$. We show that \[ R_k(\mathcal{O}_p)\ge (\log^{(p-1)}k)^{k/3-o(k)} \] for every fixed $p$, where $\log^{(p-1)}$ denotes the $(p-1)$-fold iterated logarithm. This immediately implies that for every fixed odd cycle, the multicolor Ramsey number is superexponential in the number of colors. The presented proof was found autonomously by ChatGPT 5.6 Pro/Sol.
The set-coloring Ramsey number $R(k;r,s)$ is the least $N$ such that every assignment of an $s$-element subset of $[r]$ to each edge of $K_N$ yields a copy of $K_k$ whose edges share a common color. For every fixed prime power $q$, we construct infinitely many positive integer triples $(r,j,s)$ with $j\sim(q-1)^{-2/3}r...
A longstanding fundamental problem of Burr, Erd\H{o}s, Faudree, Rousseau and Schelp (\emph{Trans. Amer. Math. Soc.}, 1982) is to determine the exact value of the least integer $f(m)$, for odd $m\ge3$, such that every tree $T_n$ on $n\ge f(m)$ vertices satisfies $R(T_n,C_m)=2n-1$. We settle this problem for all sufficie...
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...
We provide a general upper bound on multicolor ordered Ramsey numbers in terms of the interval chromatic number and the degeneracy of an ordered graph. We extend previous results by Conlon, Fox, Lee, and Sudakov (2017) by showing that for every $n$-vertex ordered graph $G^<$ with degeneracy $d\geq2$, and interval chrom...
We study the forbidden poset analog of the maximal anti-Ramsey problem introduced for graphs by Burr, Erd\H os, Graham, and S\'os. For integers $m\le 2^n$ and poset $P=(P,\preceq)$, we introduce $\mathrm{ar_m}(n,m,P)$ (and $\mathrm{ar^*_m}(n,m,P)$) to denote the minimum integer $k$ such that there exists a family $\mat...
Binlong Li, Balázs Patkós, Chang-Xin Wang· 1 citation
The \emph{ordered Ramsey number} $r_<(G,H)$ of ordered $k$-graphs $G$ and $H$ is the least integer $N$ such that every red-blue edge-coloring of the naturally ordered complete $k$-graph on $[N]$ contains a blue ordered copy of $G$ or a red ordered copy of $H$. We prove that there is an absolute constant $c>0$ such that...
Wen Chen, Zi-Han He, Qi-Zhong Lin et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
