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$)
Mutual information vs. Product sets
co.combinatorics;it.information theory