Disjoint pairs in set systems with restricted intersection. (January 2020)

• Record Type: Journal Article
• Authors: Girão, António; Snyder, Richard
• Is Part Of: European journal of combinatorics. Volume 83(2020)
• Publication Date: 2020-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2019.102998
• Languages: English
• ISSNs: 0195-6698

Abstract

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 ) .