2017/06/21 by Girão, António, Snyder, Richard
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1706.06994
The problem of bounding the size of a set system under various intersection restrictions has a central place in extremal combinatorics. We investigate the maximum number of disjoint pairs a set system can have in this setting. In particular, we show that for any pair of set systems (A, B) which avoid a cross-intersection of size t, the number of disjoint pairs (A, B) with A ∈ A and B ∈ B is at most ∑k=0t-1\binomnk2n-k. This implies an asymptotically best possible upper bound on the number of disjoint pairs in a single t-avoiding family F ⊂ P[n]. We also study this problem when A, B ⊂ [n](r) are both r-uniform, and show that it is closely related to the problem of determining the maximum of the product |A||B| when A and B avoid a cross-intersection of size t, and n ≥ n0(r, t).