For graphs $F$ and $H$, the Ramsey number $R(F,H)$ is the minimum integer $N$ such that every $N$-vertex graph contains $F$ or its complement contains $H$. If $F$ is connected and $|F|\ge\sigma(H)$, a construction of Burr gives $R(F,H)\ge(\chi(H)-1)(|F|-1)+\sigma(H)$, where $\sigma(H)$ denotes the minimum order of a color class in a proper $\chi(H)$-coloring of $H$. Burr proved that this bound is attained for $F=C_n$ when $n$ is sufficiently large. Allen, Brightwell and Skokan conjectured that equality already holds whenever $n\geq |H| \chi(H)$, while Haslegrave, Hyde, Kim and Liu subsequently proved it whenever $n\ge C|H|\log^4\chi(H)$. Pokrovskiy and Sudakov conjectured that the optimal linear condition $n\geq C|H|$ suffices; this conjecture was also highlighted by Montgomery in his 2026 ICM survey (see Conjecture 9.2). In this paper, we resolve this conjecture by proving that there is an absolute constant $C>0$ such that $R(C_n,H)=(\chi(H)-1)(n-1)+\sigma(H)$ for every nonempty graph $H$ and every $n\ge C|H|$. This gives the first bound linear in $|H|$, and is best possible up to a constant factor. Our proof builds on the framework of Haslegrave, Hyde, Kim and Liu, and combines some new ideas in expansion and switching cycle lengths.
For graphs $F$, $G$, and $H$, we write $F \to (G, H)$ if every red/blue edge-coloring of $F$ contains either a red copy of $G$ or a blue copy of $H$. The Ramsey number $R(G, H)$ is the smallest integer $N$ such that $K_N \to (G, H)$. Let $H := K_k + nK_h$ be the generalized book graph, and let $G := K_{p+1}(a_1, a_2, \...
The Ramsey number $r(H)$ of a graph $H$ is the minimum positive integer $N$ such that every red/blue edge-coloring of the complete graph $K_N$ on $N$ vertices contains a monochromatic copy of $H$. The Ramsey multiplicity $M(H,n)$ is the minimum number of monochromatic copies of $H$ over all red/blue edge-colorings of $...
Ting Huang, Jun-Ying Lu, Jia-Bao Yang et al.· 0 citations
For a graph $G$, let $e(G)$ denote the number of edges of $G$, and let $c(G)$ be the number of distinct cycles in $G$. Morrison, Roberts and Scott asked whether, for every fixed graph $H$ and all large $n$, some $n$-vertex $H$-free graph maximizes both $e(G)$ and $c(G)$. In this paper, we show that the answer is no for...
For a graph $H$, the anti-Ramsey number $\operatorname{ar}(n,H)$ is the maximum number of colors in an edge-coloring of $K_n$ containing no rainbow copy of $H$, where a copy is rainbow if its edges have pairwise distinct colors. Let $s,t$ be nonnegative integers with $s+t\ge2$, and let $H_{s,t}$ be a graph consisting o...
Given graphs $H$ and $F$, the generalized Tur\'{a}n number ${\rm ex}(n,H,F)$ is the maximum number of copies of $H$ in an $n$-vertex $F$-free graph. Alon and Shikhelman (J. Combin. Theory Ser. B, 2016) initiated the systematic study of generalized Tur\'{a}n problems. Recently, Gao, Wu and Xue (J. Graph Theory, 2026) as...
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.
