7
$\begingroup$

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! :)

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

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

$\endgroup$
7
  • $\begingroup$ Approximately $\binom n2 /2^k$, surely, given the initial edge count? $\endgroup$
    – Joffan
    Jan 31 '17 at 15:03
  • $\begingroup$ oh yeah, although this allows us to reach a contradiction either way right? $\endgroup$
    – Asinomas
    Jan 31 '17 at 15:04
  • $\begingroup$ 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$. $\endgroup$
    – Joffan
    Jan 31 '17 at 15:08
  • $\begingroup$ ok, maybe some justification is needed, but I don't see how this strategy can be overcome. $\endgroup$
    – Asinomas
    Jan 31 '17 at 15:09
  • $\begingroup$ 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. $\endgroup$
    – kindasorta
    Jan 31 '17 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.