Ramsey properties of random subgraphs of pseudo-random graphs (Q456320)

Summary: 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 \(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.