Ramsey properties of random subgraphs of pseudo-random graphs

Jia Shen¹

¹University of Science and Technology of China

The electronic journal of combinatorics, Tome 19 (2012) no. 3

Résumé

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.

Détail

DOI : 10.37236/2468

Classification : 05C80, 05C55, 05D10, 05D40
Mots-clés : random subgraph, pseudo-random, Ramsey property, \(H\)-packing