Let $G(V, E)$ be a simple graph with $|V|=n$, and let $h$ be an integer in $[n]$.

We repeat $h$-many times the following operation in a sequential fashion, where the graph may change at each round. We denote by $G_t(V_t, E_t)$ the graph obtained just after round $t\in [h]$ (we have thereofore $G(V,E)=G_0(V_0,E_0)$):

At each round $t=1, 2, \ldots, h$, we select uniformly at random (with replacement) $h$-many vertices from $V_t$. Let $v$ be the first vertex selected. If at least one of the other selected vertices is adjacent to $v$ in $G_t$, then we remove from $G_t$ vertex $v$ and all vertices adjacent to $v$ (together with their incident edges) -- otherwise $G_t(V_t,E_t)=G_{t-1}(V_{t-1},E_{t-1})$.

Question: In expectation over the above random process, what is the maximum number of edges in $E_h$ over all possible $2^{n \choose 2}$-many input graphs $G(V, E)$ (when $n\to\infty$)?

(I am especially interested in finding a tight upper bound for $\max_{G(V,E)}\mathbb{E}\left[|E_h|\right]$).

Conjecture: The maximum value for $\mathbb{E}\left[|E_h|\right]$ is equal to $\Theta\left(\frac{n^2}{h}\right)$.

(In particular, I cannot find any graph $G(V,E)$ for which $\mathbb{E}\left[|E_h|\right]=\omega\left(\frac{n^2}{h}\right)$).


1 Answer 1


The conjectured upper bound is true and rather simple. Note that if we have a vertex $v$ of degree $d(v)=d>\frac nh$ in $G(t)$, then if we choose it first, the conditional probability that we remove it and its neighbors is $1-(1-\frac dn)^{h-1}\ge 1-(1-\frac 1h)^{h-1}\ge \frac 12$ (assuming $h\ge 2$; otherwise there is nothing to prove). Thus, if we denote by $\sigma(t)$ the sum $\sum_{v\in V(t):d(v)>\frac nh} d(v)$ and by $D(t)$ the number of deleted vertices when moving from $G(t)$ to $G(t+1)$, we get $$ ED(t)\ge \frac 1n\frac12 E\sigma(t)\,. $$ Since $\sum_{t=0}^{h-1}D(t)\le n$ and $\sigma(t)$ is non-increasing with $t$, we immediately obtain $$ n\ge\sum_{t=0}^{h-1}ED(t)\ge \frac 1n\sum_{t=0}^{h-1}\frac 12E\sigma(t)\ge \frac hn\frac 12E\sigma(h)\,, $$ i.e. $E\sigma(h)\le 2\frac{n^2}h$. But $$ E|E(h)|=\frac 12 E\sum_{v\in V(h)}d(v)=\frac 12 E\left[\sum_{v:d(v)\le \frac nh}d(v)+\sigma(h)\right]\le \frac 32\frac {n^2}h\,. $$ The constant $\frac 32$ is not the best, of course, but the order of magnitude is sharp at least as long as $h$ doesn't come too close to $n$. Just consider any regular graph with degree of each vertex $\frac n{20h}$ and notice that the survival probability for each edge is at least $\frac 12$.

  • $\begingroup$ Thank you fedja! $\endgroup$ Apr 30, 2019 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.