Disjoint pairs in set systems with restricted intersection. (January 2020) - Girão, António; Snyder, Richard
Abstract: 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 = 0 t − 1 n k 2 n − 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 ≥ n 0 ( r, t ) .