Cyclic interval intersection bound

ID: cyclic-interval-intersection-bound

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.

New to topics? Read the docs here!