<p>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 <a href="http://www.math.u-szeged.hu/~csaba/cikkek/fesz-reg.pdf">paper</a> relevant.</p>

CC BY-SA 3.0
2012-06-05T01:22:13.067Z
2012-06-05T01:22:13.067Z
hbm
<p>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:</p>

<p>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.</p>

<p>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.</p>

<p><em>Background</em>: 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.</p>

CC BY-SA 3.0
2012-06-05T02:53:58.730Z
We don't generally like simultaneous cross posting. It tends to fragment and duplicate the discussion.
Suresh Venkat
CC BY-SA 3.0
2012-06-05T04:03:53.823Z
Thanks, I saw this policy a bit later and removed the question from math overflow.
Or Meir
<cc.complexity-theory><co.combinatorics><communication-complexity>
A balanced generalization of Hall’s theorem
Or Meir
# A balanced generalization of Hall’s theorem

(Asked by: username_0 on 2012-06-05)

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.

**Tags:** cc.complexity-theory, co.combinatorics, communication-complexity

> **Comments:**
> **username_1**: We don't generally like simultaneous cross posting. It tends to fragment and duplicate the discussion.  
> **username_0**: Thanks, I saw this policy a bit later and removed the question from math overflow.  

---

## 1 answers

### Answer by username_2 on 2012-06-05. Score: 5 | Accepted answer

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](http://www.math.u-szeged.hu/~csaba/cikkek/fesz-reg.pdf) relevant.


---

