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



Combinatorial optimization for a sequential random process on graphs
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$. 


