Ramsey Properties of Random Subgraphs of Pseudo-Random Graphs

Abstract

Let $G=(V,E)$ be a $d$-regular graph of order $n$. Let $G_p$ be the random subgraph of $G$ for which each edge is selected from $E(G)$ independently at random with probability $p$. For a fixed graph $H$, define $m(H):=$max$\{e(H')/(v(H')-1):H' \subseteq H\}$. We prove that $n^{(m(H)-1)/m(H)}/d$ is a threshold function for $G_p$ to satisfy Ramsey, induced Ramsey, and canonical Ramsey properties with respect to vertex coloring, respectively, provided the eigenvalue $\lambda$ of $G$ that is second largest in absolute value is significantly smaller than $d$.

As a consequence, it is also shown that $\displaystyle n^{(m(H)-1)/m(H)}/d$ is a threshold function for $G_p$ to contain a family of vertex disjoint copies of $H$ (an $H$ packing) that covers $(1-o(1))n$ vertices of $G$. Using a similar argument, the sharp threshold function for $G_p$ to contain $H$ as a subgraph is obtained as well.