# Combinatorial optimization for a sequential random process on graphs

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

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