Ramsey properties of random subgraphs of pseudo-random graphs
type: Item
instance of: scholarly article
title: Ramsey properties of random subgraphs of pseudo-random graphs
zbMATH Open document ID: 1252.05206
author: Jia Shen
published in: The Electronic Journal of Combinatorics
publication date: 2012-10-24T00:00:00Z
full work available at URL: v19i3p2
review text: 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.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05D10
Mathematics Subject Classification ID: 05D40
zbMATH DE Number: 6098344
zbMATH Keywords: random subgraph
zbMATH Keywords: pseudo-random
zbMATH Keywords: Ramsey property
zbMATH Keywords: \(H\)-packing
MaRDI profile type: MaRDI publication profile
description: scientific article; zbMATH DE number 6098344