Erdos-Ko-Rado: the largest intersecting family of k-subsets

For \(n \ge 2k\) the maximum is \(\binom{n-1}{k-1}\), attained by the star of all \(k\)-sets through a fixed element.

Usage

morie_erdos_ko_rado(n, k)

Arguments

n, k

Ground set and subset sizes.

Value

A list with count, star_size, ekr_regime, warnings.

Details

The condition \(n \ge 2k\) is not decoration. BELOW it no two \(k\)-subsets can be disjoint at all, so every family is intersecting and the answer is the trivial \(\binom{n}{k}\); quoting the star bound there gives an answer that is too small and looks reasonable. ekr_regime reports which case applies.

References

Erdos P, Ko C, Rado R (1961) Quart J Math 12:313-320.

Examples

morie_erdos_ko_rado(n = 5L, k = 5L)
#> $count
#> [1] 1
#> 
#> $star_size
#> [1] 1
#> 
#> $all_k_sets
#> [1] 1
#> 
#> $ekr_regime
#> [1] FALSE
#> 
#> $n
#> [1] 5
#> 
#> $k
#> [1] 5
#> 
#> $warnings
#> [1] "n = 5 is below 2k = 10, outside the Erdos-Ko-Rado regime. The star bound C(n-1, k-1) = 1 is NOT the answer here; it is smaller than the truth because every family is intersecting when no two k-sets can be disjoint."
#> 
#> $method
#> [1] "Erdos-Ko-Rado theorem (1961)"
#>