Effective Bounds for Induced Size-Ramsey Numbers of Cycles

The induced size-Ramsey number r̂ᵢndᵏ(H) r ^ ind k ( H ) of a graph H is the smallest number of edges a (host) graph G can have such that for any k -coloring of its edges, there exists a monochromatic copy of H which is an induced subgraph of G . In 1995, in their seminal paper, Haxell, Kohayakawa and Łuczak showed that for cycles, these numbers are linear for any constant number of colours, i.e., r̂ᵢndᵏ(Cₙ)≤ Cn r ^ ind k ( C n ) ≤ C n for some $$C=C(k)$$ C = C ( k ) . The constant C comes from the use of the regularity lemma, and has a tower type dependence on k . In this paper we significantly improve these bounds, showing that r̂ᵢndᵏ(Cₙ)≤ O(k¹⁰²)n r ^ ind k ( C n ) ≤ O ( k 102 ) n when n is even, thus obtaining only a polynomial dependence of C on k . We also prove r̂ᵢndᵏ(Cₙ)≤ eO(klog k)n r ^ ind k ( C n ) ≤ e O ( k log k ) n for odd n , which almost matches the lower bound of eΩ (k)n e Ω ( k ) n . Finally, we show that the ordinary (non-induced) size-Ramsey number satisfies r̂ᵏ(Cₙ)=eO(k)n r ^ k ( C n ) = e O ( k ) n for odd n . This substantially improves the best previous result of eO(k²)n e O ( k 2 ) n , and is best possible, up to the implied constant in the exponent. To achieve our results, we present a new host graph construction which, roughly speaking, reduces our task to finding a cycle of approximate given length in a graph with local sparsity.