Combinatorial optimization for a sequential random process on graphs

Question

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)$).

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$.