# The largest connected component of a random subgraph

Let a graph on $|V|$ vertices and $|E|$ edges. We randomly sample $s= c \cdot \frac{|V|}{{d_{\text{av}}}}$ vertices, without replacement, where $d_{\text{av}}$ is the average degree of $G$ and $c$ is some big constant. Let $G'$ be the subgraph induced by these $s$ vertices.

What is the size of the largest connected component of $G'$?

I'm tempted to say $O(\log(s))$, under a mild assumption like |E| = o(|V|^2). Some intuition comes from the fact that the probability of 2 vertices in $G'$ being friends is $\sim \frac{E}{V^2} = \frac{{d_{\text{av}}}}{|V|}=1/s$; if $G'$ was an Erdős–Rényi then, it would be below the giant component threshold. Obviously, the edges in $G'$ are not independent, so the result does not immediately hold.

Examples where the O(log(s)) claim is true: star, cycle graph, union of cliques of size o(n).

Any ideas?

• By "without replacement" of the vertices, what happens to the edges that connect to non chosen vertices? – Ryan Nov 13 '14 at 0:20
• Not sure I understand the question. $G'$ sits on the vertices selected, and the edges of $G'$ are only the ones between the induced vertices. – Dimitris Nov 13 '14 at 1:13
• Ok, and what is the quantity $d_{av}$? – Ryan Nov 13 '14 at 3:22
• Sorry, forgot to mention, it's the average degree. – Dimitris Nov 13 '14 at 3:50
• Why does not $c=d_{av}$ force $G'=G$? – daniello Nov 13 '14 at 9:14