<p>Suppose we have two <em>dependent</em> random variables $X$ and $Y$, each of which is uniform over $\{0,1\}^n$, such that their mutual information $I(X;Y)$ is small, say, at most $\sqrt{n}$. Does this imply that there exist large sets $\mathcal{X}, \mathcal{Y} \subset \{0,1\}^n$ such that the product set $\mathcal{X} \times \mathcal{Y}$ is contained in the support of the distribution $(X,Y)$?</p>

<p>A variant of this question can be phrased in graph-theoretic terms: Suppose we have a sufficiently dense bipartite graph G. Does this imply that $G$ contains a large complete sub-graph $G&#39;$? (i.e., $G&#39;$ is required to be a complete bipartite graph with bi-partition $(A,B)$ such that $A$ and $B$ are relatively dense in the corresponding parts of $G$)</p>

CC BY-SA 3.0
2012-02-16T11:14:00.757Z
I'm not an expert, but perhaps this paper on Ramsey theory applied to bipartite graphs can help you: http://math.mit.edu/~fox/paper-density-theorems-final.pdf
Marzio De Biasi
CC BY-SA 3.0
2012-02-17T22:50:33.423Z
If my calculation is correct, a standard use of the probabilistic method shows that for sufficiently large N, there exists a bipartite graph on N+N vertices with at least (1/2)N^2 edges that does not contain K_{k,k} as a subgraph, where k = floor(2.001 lg N).  (“lg” denotes the logarithm to base two.)
Tsuyoshi Ito
CC BY-SA 3.0
2017-06-12T13:01:23.340Z
If $(X,Y)$ is a product of iid trials $(X_i,Y_i)$ then I am inclined to say yes.
Christian Chapman
<co.combinatorics><it.information-theory>
Mutual information vs. Product sets
Or Meir
# Mutual information vs. Product sets

(Asked by: username_0 on 2012-02-16)

Suppose we have two *dependent* random variables $X$ and $Y$, each of which is uniform over $\{0,1\}^n$, such that their mutual information $I(X;Y)$ is small, say, at most $\sqrt{n}$. Does this imply that there exist large sets $\mathcal{X}, \mathcal{Y} \subset \{0,1\}^n$ such that the product set $\mathcal{X} \times \mathcal{Y}$ is contained in the support of the distribution $(X,Y)$?

A variant of this question can be phrased in graph-theoretic terms: Suppose we have a sufficiently dense bipartite graph G. Does this imply that $G$ contains a large complete sub-graph $G'$? (i.e., $G'$ is required to be a complete bipartite graph with bi-partition $(A,B)$ such that $A$ and $B$ are relatively dense in the corresponding parts of $G$)

**Tags:** co.combinatorics, it.information-theory
> **Comments:**
> **username_1**: I'm not an expert, but perhaps this paper on Ramsey theory applied to bipartite graphs can help you: http://math.mit.edu/~fox/paper-density-theorems-final.pdf  
> **username_2**: If my calculation is correct, a standard use of the probabilistic method shows that for sufficiently large N, there exists a bipartite graph on N+N vertices with at least (1/2)N^2 edges that does not contain K_{k,k} as a subgraph, where k = floor(2.001 lg N).  (“lg” denotes the logarithm to base two.)  
> **username_3**: If $(X,Y)$ is a product of iid trials $(X_i,Y_i)$ then I am inclined to say yes.  

---

## 0 answers

