Let $X$ and $Y$ be sets, and $\mathcal{B}$ be a partition of $X \times Y$. I would like to prove that there exists a distribution $\mathcal{D}$ over $X \times Y$ whose marginal is uniform over $X$, and such that the distribution over $\mathcal{B}$ induced by $\mathcal{D}$ has large entropy(the latter distribution is defined by assigning each $B∈\mathcal{B}$ the total probability mass of the elements of $B$ under $\mathcal{D}$). We can use the following condition:

Consider the bipartite graph $G$ whose sides are $X$ and $\mathcal{B}$, such that for each $(x,y) \in B$ there is an edge $(x,B)$ in $G$ (multiple edges possible). Then, every set of $x$'s of size at least $\frac{3}{4}|X|$ has at least $\frac{1}{100}|B|$ neighbors in G.

I would appreciate it if someone could refer me to a relevant theorem. This question can be viewed in a sense as a generalization of Hall's theorem, where the above condition is a relaxation Hall's condition, and where instead of getting a perfect matching, we get a set of edges whose corresponding subgraph is roughly regular.

Background: The motivation for this questions comes from communication complexity. In the setting of communication complexity, two players, Alice and Bob, get inputs $x$ and $y$ respectively, and interact in order to compute some function $f(x,y)$. Here, each set $B \in \mathcal{B}$ consists of pairs $(x,y)$ that yield the same transcript of communication between Alice and Bob, and I would like to prove that under some condition, one can find a distribution over $X \times Y$ such that Alice gets a uniformly distributed input, and such that the entropy of the transcript under the distribution is large.

  • 1
    $\begingroup$ We don't generally like simultaneous cross posting. It tends to fragment and duplicate the discussion. $\endgroup$ Commented Jun 5, 2012 at 2:53
  • $\begingroup$ Thanks, I saw this policy a bit later and removed the question from math overflow. $\endgroup$
    – Or Meir
    Commented Jun 5, 2012 at 4:03

1 Answer 1


You might look into the concept of $f$-factors and specially Tutte's theorem on the existence of $f$-factors. You might find Proposition 2 of this paper relevant.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.