The question asks whether small mutual information between two dependent uniform random variables ( X ) and ( Y ) over ( {0,1}^n ) implies the existence of large product sets ( \mathcal{X} \times \mathcal{Y} ) in their support. A related graph-theoretic variant inquires if a sufficiently dense bipartite graph must contain a large complete bipartite subgraph (biclique) with relatively den...

No.

Take N = 2^n and fix any constant edge density p in (0,1). Let G be a d-regular bipartite graph on (N,N) with d = pN (such regular graphs exist for all large N). Define (X,Y) to be uniformly distributed over the edges of G, i.e., each edge has probability 1/(Nd) and non-edges have probability 0.

• The marginals are uniform: since G is d-regular on both sides, each left (resp. right) vertex i...

This is a very interesting question about the relationship between mutual information and product structure in probability distributions. Let me analyze both the information-theoretic formulation and its graph-theoretic variant.

Information-Theoretic Analysis

For the main question, the answer is no in general. Low mutual information does not necessarily imply the existence of large produc...

No – a small amount of mutual information does not force the joint support to contain a large Cartesian product, and, in the equivalent graph‐theoretic language, a dense bipartite graph need not contain a large complete bipartite sub-graph (biclique).
A single probabilistic construction already shows this.

1. A conven...

This is an excellent question that connects information theory, combinatorics, and graph theory. The short answer is no, small mutual information does not imply the existence of a large product set in the support.

Let's break down why this is the case, following the insightful graph-theoretic rephrasing you provided.

1. Connecting Mutual Information to Graph Density

First, let's make th...

We can also think of this in graph theory terms: consider a bipartite graph G with bipartition (A, B) where A = B =...

Mutual Information vs. Product Sets

This question explores the relationship between mutual information in random variables and the existence of large product sets within the support of their joint distribution.

Understanding the Problem

We have two dependent random variables and , each uniformly distributed over , with mutual information . The questi...

First, let me restate the two formulations in one language:

1. Information‐theoretic form. We have X,Y∈{0,1}ⁿ marginally uniform, and I(X;Y)≪n (say I(X;Y)≤√n). We ask: must there be “large’’ subsets 𝒳⊆{0,1}ⁿ and 𝒴⊆{0,1}ⁿ, each of size 2^{n−o(n)}, such that every pair in 𝒳×𝒴 has positive probability under (X,Y)?

2. Graph‐theoretic form. Let G be a bipartite graph on N=2ⁿ vertice...

No – knowing that two uniform random variables share only a few bits of mutual information does not force the support of their joint distribution to contain a large Cartesian product, and in the language of graphs a dense bipartite graph need not contain a large complete bipartite sub-graph.
A single counter-example already disproves the implication, and in fact one can give a whole family o...