<p>Let $X_m=[m]=\{0,1,\dots,m-1\}$ and let $Y_m=[2m]\setminus [m]$.
Given is a complete bipartite graph $G_m$, with parts $X_m$ and $Y_m$ and edges $\{x,y\}$ for every $x\in X_m$ and $y\in Y_m$.
Alice and Bob are given subsets $A$ and $B$ of $[2m]$, with $|A|=a$ and $|B|=b$, and further these subsets are small relative to $m$, in the sense that $a &lt; b \le m$.
For convenience, let $C = A\cup B$.
The parties must agree on a common pair of vertices $u\in X_m$ and $v\in Y_m$, that represent some edge of $G_m$ that is <em>not</em> in the subgraph induced by $C$, in other words so that either $u \not\in C$ or $v\not\in C$.</p>

<p>Is this game known, and is there a good lower bound on the amount of communication required?</p>

<hr>

<p>The size condition guarantees that the decision version is trivial (Alice sends "YES" to Bob): since $|C|&lt;2m$ there is always some vertex that is not held by either party, so it together with any vertex in the other part forms a non-edge of $G_m[C]$.
Since $a$ is small relative to $m$, Alice can send a description of $A$ to Bob using $\lceil\lg\binom{2m}{a}\rceil = O(a\lg m)$ bits.
Furthermore, Alice sending a random element from $X\setminus A$ and one from $Y\setminus A$ gives a randomized one-way protocol with vanishing error (at least in some parameter regimes) and cost $O(\lg m)$.
In contrast, a set disjointness lower bound applied to the complements of $A$ and $B$ would predict $\Omega(m)$ bits being required, contradicting the trivial upper bound, so a straightforward reduction from set disjointness does not work (of course, a less direct reduction might work).
The implicit description of edges seems to be introducing an ingredient that I do not recognise from the usual communication games.</p>

CC BY-SA 3.0
2016-12-20T14:14:04.823Z
I don't completely understand your question. Is the goal to agree on a common pair $(u,v)$? Isn't this equivalent to playing the game of agreeing on some $u\in X\setminus (A\cup B)$ twice (in parallel) with the only thing connecting the two copies of the game being the size restrictions? I also don't understand your remarks that follow the question.
domotorp
CC BY-SA 3.0
2016-12-20T15:27:17.903Z
I do not really understand why you need a graph in this ... I still do not understand why Alice can say yes. Indeed, you allow $b = m$. Thus, you can have $B = Y_m$. In this case, you cannot find the desired $(u,v)$ as you want $v \in Y \setminus (A \cup B) = \emptyset$... Even if you have $b < m$, you still may have $A \cup B \supset Y$. Please clarify.
holf
CC BY-SA 3.0
2016-12-20T16:22:52.477Z
@domotorp, thanks for your helpful comments.  I have updated the question.  It seems the hard part here was formulating the question precisely enough; once it is set out clearly then the answer seems straightforward.  Perhaps you would like to turn your second sentence into an answer, so that I could accept it?
András Salamon
CC BY-SA 3.0
2016-12-20T16:23:00.757Z
@holf: you are right, this doesn't seem to rely on a graph when formulated correctly.
András Salamon
CC BY-SA 3.0
2016-12-20T19:43:31.563Z
Now the question seems to have changed, at least I thought earlier that both $u$ and $v$ had to be outside $C$, but now only one of them has to be. I'm still not entirely sure what kind of answer you're looking for, but this might be of your interest: https://arxiv.org/abs/1304.1217
domotorp
CC BY-SA 3.0
2016-12-22T14:02:07.387Z
@domotorp, thanks for the pointer, looks highly relevant.
András Salamon
<cc.complexity-theory><communication-complexity>
Is this graph communication game known?
András Salamon
# Is this graph communication game known?

(Asked by: username_0 on 2016-12-19)

Let $X\_m=[m]=\{0,1,\dots,m-1\}$ and let $Y\_m=[2m]\setminus [m]$.
Given is a complete bipartite graph $G\_m$, with parts $X\_m$ and $Y\_m$ and edges $\{x,y\}$ for every $x\in X\_m$ and $y\in Y\_m$.
Alice and Bob are given subsets $A$ and $B$ of $[2m]$, with $|A|=a$ and $|B|=b$, and further these subsets are small relative to $m$, in the sense that $a < b \le m$.
For convenience, let $C = A\cup B$.
The parties must agree on a common pair of vertices $u\in X\_m$ and $v\in Y\_m$, that represent some edge of $G\_m$ that is *not* in the subgraph induced by $C$, in other words so that either $u \not\in C$ or $v\not\in C$.

Is this game known, and is there a good lower bound on the amount of communication required?

---

The size condition guarantees that the decision version is trivial (Alice sends "YES" to Bob): since $|C|<2m$ there is always some vertex that is not held by either party, so it together with any vertex in the other part forms a non-edge of $G\_m[C]$.
Since $a$ is small relative to $m$, Alice can send a description of $A$ to Bob using $\lceil\lg\binom{2m}{a}\rceil = O(a\lg m)$ bits.
Furthermore, Alice sending a random element from $X\setminus A$ and one from $Y\setminus A$ gives a randomized one-way protocol with vanishing error (at least in some parameter regimes) and cost $O(\lg m)$.
In contrast, a set disjointness lower bound applied to the complements of $A$ and $B$ would predict $\Omega(m)$ bits being required, contradicting the trivial upper bound, so a straightforward reduction from set disjointness does not work (of course, a less direct reduction might work).
The implicit description of edges seems to be introducing an ingredient that I do not recognise from the usual communication games.

**Tags:** cc.complexity-theory, communication-complexity

> **Comments:**
> **username_1**: I don't completely understand your question. Is the goal to agree on a common pair $(u,v)$? Isn't this equivalent to playing the game of agreeing on some $u\in X\setminus (A\cup B)$ twice (in parallel) with the only thing connecting the two copies of the game being the size restrictions? I also don't understand your remarks that follow the question.  
> **username_2**: I do not really understand why you need a graph in this ... I still do not understand why Alice can say yes. Indeed, you allow $b = m$. Thus, you can have $B = Y_m$. In this case, you cannot find the desired $(u,v)$ as you want $v \in Y \setminus (A \cup B) = \emptyset$... Even if you have $b < m$, you still may have $A \cup B \supset Y$. Please clarify.  
> **username_0**: @username_1, thanks for your helpful comments.  I have updated the question.  It seems the hard part here was formulating the question precisely enough; once it is set out clearly then the answer seems straightforward.  Perhaps you would like to turn your second sentence into an answer, so that I could accept it?  
> **username_0**: @username_2: you are right, this doesn't seem to rely on a graph when formulated correctly.  
> **username_1**: Now the question seems to have changed, at least I thought earlier that both $u$ and $v$ had to be outside $C$, but now only one of them has to be. I'm still not entirely sure what kind of answer you're looking for, but this might be of your interest: https://arxiv.org/abs/1304.1217  
> **username_0**: @username_1, thanks for the pointer, looks highly relevant.  

---

## 0 answers

