A note on Ramsey numbers for minors

Abstract

Let $R_h(k;\ell )$ be the smallest integer $n$ such that any edge coloring of a complete graph on $n$ vertices in $\ell$ colors results in a monochromatic $K_k$-minor, in other words, a graph with Hadwiger number $k$, i.e., a graph that could be transformed into a clique $K_k$ on $k$ vertices via a sequence of edge contractions and vertex deletions. More generally, for a graph $F$ and integer $\ell$ let $R_h(F;\ell )$ be the smallest integer $n$ such that any edge coloring of a complete graph on $n$ vertices in $\ell$ colors results in a monochromatic $F$-minor. In 2001 Thomason and in 2005 Myers and Thomason asymptotically determined the extremal numbers for clique minors and $F$-minors, respectively. They found the respective explicitly computable leading constants ${\hat{I}}^2=\mathrm{0.265656...}$ and ${\hat{I}}^3(F)\cdot {\hat{I}}^2$ for these extremal numbers. We determine $R_h(F;2)$ for every graph $F$ as $$R_h(F;2)=({\hat{I}}^3(F)+o(1))|V(F)|\sqrt{{\log }_2(|V(F)|)},$$ where the $o(1)$-term tends to zero as $|V(F)|\to \infty$. In particular, $$R_h(k;2)=(1+o(1))k\sqrt{{\log }_{2}k}.$$ When $\ell \gg k\gg 1$, we show that $$R_h(k;\ell )=(2{\hat{I}}^2+o(1))\ell k\sqrt{{\log }_{2}k}.$$

9 pages. An improved tight bound on $R_h(k)$ is obtained and a more general Ramsey number for arbitrary minors is determined asymptotically. Comments are welcome