= Measurable Hall theorem
= Hall theorem for Lebesgue measurable sets
{c}
{synonym}
For finitely many <Lebesgue measurable sets> $A_i\subseteq[0,1]$ and nonnegative demands $b_i$, pairwise disjoint measurable <subsets> $B_i\subseteq A_i$ with $\lambda(B_i)=b_i$ exist exactly when $\lambda(\bigcup_{i\in I}A_i)\geq\sum_{i\in I}b_i$ for every index <subset> $I$. Necessity is additivity and monotonicity of <Lebesgue measure>. For sufficiency, partition the <set union> into membership cells $E_J$, send flow from a source through demand vertices $i$ to cells with $i\in J$, then to a sink. Source capacities are $b_i$, cell capacities are $\lambda(E_J)$, and intermediate capacities are $D=\sum_i b_i$. Every <cut of a flow network> has capacity at least $D$ by the assumed inequalities. The <max-flow min-cut theorem> provides the allocations, and <divisibility of Lebesgue measure> turns each cell allocation into disjoint pieces. If $D=0$, all $B_i$ can simply be empty.
Back to article page
