On the threshold Ramsey multiplicity conjectures for paths and even cycles

Abstract

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 threshold Ramsey multiplicity $m(H)$ of $H$ is the minimum number of monochromatic copies of $H$ over all red/blue edge-colorings of $K_{r(H)}$. Let $P_t$ and $C_t$ be a path and a cycle on $t$ vertices, respectively. In this paper, by using combinatorial and local random construction, we show that $$m(C_{2t})\le t^{-{\hat{I}}^3+o(1)}\frac{(2t-1)!}{2},m(P_{2t+1})\le t^{-{\hat{I}}^3+o(1)}\frac{t}{2}(2t)!,$$ and $$m(P_{2t})\le \left(\frac{7}{8}+o(1)\right)\frac{(2t)!}{2},$$ for sufficiently large $t$, where ${\hat{I}}^3=1/(1+\sqrt{2})$. These results disprove two conjectures on the threshold Ramsey multiplicity for even cycles and paths, due to Conlon, Fox, Sudakov, and Wei.

21 pages, 3 figures