# A graph theoretical/combinatorial problem

I'll try to describe a problem that I am currently working on, hoping to get some direction out of anyone possibly interested in the problem.

Let $G_1=([n],E_1), G_2=([n],E_2)$, such that $E_1\bigcup E_2 = {[n]\choose 2}, E_1\bigcap E_2 = \emptyset$. I.e. $E_1$ and $E_2$ form a partition of the complete graph.

Observe the following process, consisting of two sides, god and the devil.
At each step the devil chooses a graph, for example - $G_1$, and constructs a partition of its edges into two subsets, say $A, B$, i.e. $A\bigcup B = E_1$ and $A\bigcap B = \emptyset$.
God, in his turn can choose either $A$ or $B$, say he chose $A$, now $G_1=([n],A)$. And they continue to another iteration.
God's objective is to maximize the set of vertices $V:=\{i\in[n]|d_1(i),d_2(i) > 0\}$. I.e., to maximize the set of vertices with positive degree on both graphs, while the devil's goal is adverserial, he wishes to form partitions that would minimize the size $|V|$.
I can prove that for all graphs $G_1,G_2$ such that all vertices have degree of $n/2(1\pm o(1))$, and for all adversarial strategies of the devil, there exists a strategy for god (a choice of partitions) such that after $k$ steps, $|V|\ge\dfrac{n}{2^k}$.
My goal is to show that there exist graphs $G_1, G_2$ such that for all adversarial strategies, there exist counter strategies that would guaranty $|V|\ge\dfrac{n}{2^{k/2}}$. It can be shown using chernoff that the degree requirement holds for $G_1$ chosen according to $G(n,0.5)$ and $G_2$ being its complement with high probability.

Some thoughts:
I am convinced that with high probability choosing $G_1=G_{n,0.5}$ and $G_2$ to be its complement would be good candidates for the conjecture.
Simply choosing the side with the larger cardinality at each step doesn't work.
I have constructed a simple strategy that dictates god's choice at each step according to the following rule, that I suspect to be optimal strategy but I am short of proving it: Given a partition of $G_1$'s edges into two subsets $A$ and $B$, choose the set that maximizes $\Sigma_{(u,v)\in C}d_2(u) + d_2(v)$ for $C\in \{A,B\}$.
The idea is defining a potential function $\Phi = \Sigma_{(u,v)\in E_1}d_2(u) + d_2(v)$ and taking notice that for a partition of $E_1$ into $A,B$ it holds that: $\Phi = \Sigma_{E_1} = \Sigma_A + \Sigma_B$, therefore there is a choice of either $A$ or $B$ that decreases $\Phi$ by a factor of at most $2$. $\Phi$ is also symmetric as it can be rewritten as $\Sigma_{i\in [n]}d_1(i)d_2(i)$. It can be (easily) shown that choosing according to this strategy guaranties $|V|\ge\dfrac{n}{2^k}$ for all graphs. I suspect that it is an optimal strategy that would also yield the conjectured lower bound for the random graph $G(n,0.5)$ and its complement.

This is the problem, and those are some of my main thoughts. A simpler problem that I also can't solve would be to show that for 2 steps I can guaranty $|V|\ge n/2$.

I hope I was clear, and will remain available to make any clarifications required.

Edit: I am interested in proving that there exists a strategy for the case where $k\le c\log n$ for some $c\in (0,1)$ and in particular would be happy in showing, as stated above, the existence of such strategy in case $k=2$.

Thanks! :)

• When $G_2=\emptyset$|V| is always 0. Thanks for the comment, I will edit my statement. Jan 31 '17 at 14:42
• @JorgeFernándezHidalgo Thanks for your helpful corrections! :) Jan 31 '17 at 15:19
• sure no probz${}{}$ Jan 31 '17 at 15:19
• What is $d_1(v)$ and $d_2(v)$? Feb 27 '17 at 14:30
• can i still become rich? Mar 5 '17 at 15:51

The devil can make sure that the number of edges in $G_1$ after $k$ steps is approximately $\frac{n(n-1)}{2^{k+1}}$. This limits the number of vertices with positive degree to $\frac{n(n-1)}{2^{k}}$.
Notice that this is smaller than $\frac{n}{2^{k/2}}$ whenever $n-1<2^{k/2}$. So I don't think such a graph can exist for large enough values of $n$.
• Approximately $\binom n2 /2^k$, surely, given the initial edge count? Jan 31 '17 at 15:03
• I'm not sure it's a contradiction - we know the devil is going to win in the end, except for two vertices possibly labelled $U$ and $I$. Jan 31 '17 at 15:08
• I should add one more edit, saying that I do not wish to continue this process for more than $\log(n)$ steps, and even showing that this statement holds for $c\log(n)$ steps for some $c\in (0,1)$ would be considered a success. Jan 31 '17 at 15:10