15
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I'm not an expert, but perhaps this paper on Ramsey theory applied to bipartite graphs can help you: math.mit.edu/~fox/paper-density-theorems-final.pdf $\endgroup$ – Marzio De Biasi Feb 16 '12 at 11:14
  • 3
    $\begingroup$ 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.) $\endgroup$ – Tsuyoshi Ito Feb 17 '12 at 22:50
  • $\begingroup$ If $(X,Y)$ is a product of iid trials $(X_i,Y_i)$ then I am inclined to say yes. $\endgroup$ – enthdegree Jun 12 '17 at 13:01

Your Answer

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

Browse other questions tagged or ask your own question.