Graph game minimum vertex degree

Question

Consider the following graph game, given a graph $G=(V,E)$ on $n$ vertices with minimum degree $ \gg \log(n)$. Players are BR and MA (BR moves first):

1. BR claims an unclaimed edge from $E$, adds it to $B$
2. MA claims an unclaimed edge from $E$, adds to $M$
3. Repeat

MA wins if for all edges (with corresponding vertices $v$ from $V$) in $M$ fulfills $\deg_M(v) \geq (1-\epsilon)\cdot 1/3 \cdot \deg_G(v)$, for some $\epsilon > 0$.

I would like to show that there exists a winning strategy for MA.

In order to do that I would have to assume BR is playing optimally. I'm guessing I need to figure out what that strategy is before I can start proving $Pr[\exists \text{winning strategy}]>0$. Any ideas?

Answer 1

I would try the following. Every time breaker plays an edge, maker chooses an endpoint of that edge at random and plays any available edge at that vertex. Since the vertex degrees are much bigger than $\log n$, each vertex should be chosen by maker about half the number of times it gets used by breaker, so maker should achieve about $1/3$ of the available degree at each vertex. The times maker is forced to deviate from this strategy because there are no edges available will be swallowed by the $\epsilon$.

Two clarifications following the comments:

Maker's extra degree at other vertices. Treat this like you would the bonus move you get in a strategy stealing argument. We don't count the bonus degree towards our total at any vertex, and if our strategy ever tells us to play at a vertex where we've built up some bonus degree then we spend that and move arbitrarily (building up bonus degree at some two vertices). This handles the problem that arises if our strategy tells us to play at a vertex but we can't because we've already amassed too much bonus degree there.

Why do we need the vertex degrees to be large? In expectation we get to play at each vertex half as often as breaker. To say that this is in fact the typical behaviour we use a Chernoff inequality to say that the probability of differing from the expectation by a factor of more than $\epsilon$ at a vertex $v$ is bounded by an expression like $e^{-\epsilon^2d(v)}$, which tends to zero faster than $1/n$ (which is what we need to take a union bound over all $n$ vertices) provided that $d(v)$ is large enough compared to $\log n$.

Answer 2

This is proved by using a variant of the 'box game' of Chvatal and Erdos. The idea is the following.

As Maker, what you do is pick a 'most dangerous' vertex, meaning one where the ratio of your edges to Breaker's is worst, and you take an arbitrary edge there.

To prove this is a winning strategy is a bit harder. You would like to use a potential function argument, but if you do the naive approach you will get stuck because you are only trying to help yourself in one place whereas Breaker might be hurting you at two different vertices simultaneously. So what you do is take the abstract game where you have a box for each vertex and you claim elements, with Maker's bias one (because the 'other' endpoint cannot hurt Maker) and Breaker's is two (for the two endpoints of Breaker's edge). You prove the above strategy gives a Maker win in this game, which now is a fairly standard potential function argument. See Beck's book, or more recently Gebauer-Szabo or Ferber-Krivelevich-Naves.

This translation to the abstract game is where you lose something and can only guarantee $(1-\varepsilon)/3$ fraction of the vertex degree; the potential function argument is sharp (and it is where the log degree restriction comes in).