A Note on Lower Bounds for Induced Ramsey Numbers

Abstract

We say that a graph F strongly arrows a pair of graphs (G,H) and write F →ind$\mathop \to \limits^{{\rm{ind}}} $(G,H) if any 2-coloring of its edges with red and blue leads to either a red G or a blue H appearing as induced subgraphs of F. The induced Ramsey number, IR(G,H) is defined as min{|V (F)| : F →ind$\mathop \to \limits^{{\rm{ind}}} $ (G,H)}. We will consider two aspects of induced Ramsey numbers. Firstly we will show that the lower bound of the induced Ramsey number for a connected graph G with independence number α and a graph H with clique number ω is roughly ω2α2${{{\omega ^2}\alpha } \over 2}$. This bound is sharp. Moreover we will also consider the case when G is not connected providing also a sharp lower bound which is linear in both parameters.

Keywords

• induced ramsey number
• 05d10
• 05c55