<p>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.</p>

<p>What is the size of the largest connected component of $G'$?</p>

<p>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. </p>

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

<p>Any ideas? </p>

CC BY-SA 3.0
2014-11-13T00:20:30.423Z
By "without replacement" of the vertices, what happens to the edges that connect to non chosen vertices?
Ryan Dougherty
CC BY-SA 3.0
2014-11-13T01:13:28.217Z
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
CC BY-SA 3.0
2014-11-13T03:22:05.217Z
Ok, and what is the quantity $d_{av}$?
Ryan Dougherty
CC BY-SA 3.0
2014-11-13T03:50:24.227Z
Sorry, forgot to mention, it's the average degree.
Dimitris
CC BY-SA 3.0
2014-11-13T09:14:42.467Z
Why does not $c=d_{av}$ force $G'=G$?
daniello
CC BY-SA 3.0
2014-11-14T00:16:54.073Z
Turns out that this has been recently proven for $s = (1-\epsilon)\cdot \frac{n}{d_{\max}}$, which is really cool. The result can be found under Theorem 1 here http://arxiv.org/pdf/1404.5731.pdf
Dimitris
CC BY-SA 3.0
2014-11-15T12:40:48.857Z
I don't understand why you say the $O(\log s)$ bound is true for stars. Average degree is $2$, set $c = 1/50$ so $s = n/100$. Then the random selection will pick the root with probability $1/100$, in which case the size of the component is $s$. So expected size of the largest component is at least $s/100$, no?
daniello
<graph-theory><randomness><random-graphs>
The largest connected component of a random subgraph
Dimitris
# The largest connected component of a random subgraph

(Asked by: username_0 on 2014-11-12)

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?

**Tags:** graph-theory, randomness, random-graphs
> **Comments:**
> **username_1**: By "without replacement" of the vertices, what happens to the edges that connect to non chosen vertices?  
> **username_0**: 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.  
> **username_1**: Ok, and what is the quantity $d_{av}$?  
> **username_0**: Sorry, forgot to mention, it's the average degree.  
> **username_2**: Why does not $c=d_{av}$ force $G'=G$?  
> **username_0**: Turns out that this has been recently proven for $s = (1-\epsilon)\cdot \frac{n}{d_{\max}}$, which is really cool. The result can be found under Theorem 1 here http://arxiv.org/pdf/1404.5731.pdf  
> **username_2**: I don't understand why you say the $O(\log s)$ bound is true for stars. Average degree is $2$, set $c = 1/50$ so $s = n/100$. Then the random selection will pick the root with probability $1/100$, in which case the size of the component is $s$. So expected size of the largest component is at least $s/100$, no?  

---

## 0 answers

