= Bollobas set-pairs inequality
{c}
{title2=$\sum_i\binom{|A_i|+|B_i|}{|A_i|}^{-1}\leq1$}
= Bollobas set-pairs theorem
{c}
{synonym}
For disjoint pairs $A_i,B_i$ such that $A_i\cap B_j\ne\varnothing$ whenever $i\ne j$, the displayed sum is at most one. In a uniformly random <permutation>, the events that all of $A_i$ precedes all of $B_i$ are <disjoint events>, and their probabilities are the summands. Taking $B_i$ to be the complement of the members $A_i$ of an <antichain> recovers the <LYM inequality>.
Back to article page
