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?

  • $\begingroup$ By "without replacement" of the vertices, what happens to the edges that connect to non chosen vertices? $\endgroup$ Nov 13, 2014 at 0:20
  • $\begingroup$ 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. $\endgroup$
    – Dimitris
    Nov 13, 2014 at 1:13
  • $\begingroup$ Ok, and what is the quantity $d_{av}$? $\endgroup$ Nov 13, 2014 at 3:22
  • $\begingroup$ Sorry, forgot to mention, it's the average degree. $\endgroup$
    – Dimitris
    Nov 13, 2014 at 3:50
  • $\begingroup$ Why does not $c=d_{av}$ force $G'=G$? $\endgroup$
    – daniello
    Nov 13, 2014 at 9:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.