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!