Locally seeded embeddings, and Ramsey numbers of bipartite graphs with sublinear bandwidth

Abstract

A seminal result of Lee asserts that the Ramsey number of any bipartite $d$-degenerate graph $H$ satisfies $\log r(H)=\log n+O(d)$. In particular, this bound applies to every bipartite graph of maximal degree $\Delta$. It remains a compelling challenge to identify conditions that guarantee that an $n$-vertex graph $H$ has Ramsey number linear in $n$, independently of $\Delta$. Our contribution is a characterization of bipartite graphs with linear-size Ramsey numbers in terms of graph bandwidth, a notion of local connectivity. We prove that for any $n$-vertex bipartite graph $H$ with maximal degree at most $\Delta$ and bandwidth $b(H)$ at most $\exp (-C\Delta \log \Delta )n$, we have $\log r(H)=\log n+O(1)$. This characterization is nearly optimal: for every $\Delta$ there exists an $n$-vertex bipartite graph $H$ of degree at most $\Delta$ and $b(H)\le \exp (-c\Delta )n$, such that $\log r(H)=\log n+\Omega (\Delta )$. We also provide bounds interpolating between these two bandwidth regimes.

Main result of the paper is known (due to Choongbum Lee, arXiv:1504.06285)