Katona's circle method places a finite ground set in a uniformly counted cyclic order, proves a bound for the members of a set family that appear as cyclic intervals, and double-counts pairs of a member and a compatible cyclic order.
In any cyclic ordering on points, an antichain contains at most nonempty proper cyclic intervals. The intervals with one prescribed final position are nested, so at most one belongs to the antichain. Summing over final positions proves the bound. Averaging it over cyclic orderings proves the LYM inequality; the empty set and full set must be handled separately.
An intersecting family of cyclic intervals of length in a cyclic order of positions has at most members when . Rotate one selected interval to end at position . Intervals ending at miss it. Pair the remaining endpoints, other than , as for ; each pair represents two disjoint intervals, hence contributes at most one member. This gives . Counting such intervals over all permutations proves the Erdős-Ko-Rado theorem.
Articles by others on the same topic
There are currently no matching articles.