The Erdős-Ko-Rado theorem states that for , an intersecting family of -subsets of satisfiesThe bound is sharp: take all -sets containing one fixed element.
Use the Katona circle method. In any cyclic ordering of , the cyclic interval intersection bound permits at most members of to appear as length- intervals. To see the bound directly, rotate a chosen interval so that it ends at . Intervals ending at miss it. Pair the remaining endpoints except as , ; the two intervals in each pair are disjoint, so at most one is chosen. Including the fixed interval gives at most .
There are oriented cyclic orders. A fixed -set appears consecutively in of them: collapse it to a block, cyclically order that block with the other elements, and order its members internally. Double counting the compatible family-member/order pairs gives , proving the theorem.
Form the family . The nonnegative weights make it an up-set. It is an intersecting family, since two disjoint members would have combined weight exceeding one. The no-tie hypothesis makes it a self-dual set family: exactly one of belongs.
Let . Self-duality gives . The Erdős-Ko-Rado theorem gives for ; at this is immediate. If is even, .
The biased measure of a set family is . By independence of the Bernoulli random variables, it equals , since equality is excluded. Subtract and pair complementary levels. The complementary-layer bound for biased measure givesBoth factors are nonnegative for . The endpoints also follow directly, or by continuity. Thus the weighted Bernoulli majority bound is
Articles by others on the same topic
There are currently no matching articles.