On symmetric intersecting families. (May 2020)

• Record Type: Journal Article
• Authors: Ellis, David; Kalai, Gil; Narayanan, Bhargav
• Is Part Of: European journal of combinatorics. Volume 86(2020)
• Publication Date: 2020-05
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2020.103094
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: We make some progress on a question of Babai from the 1970s, namely: for n, k ∈ N with k ≤ n ∕ 2, what is the largest possible cardinality s ( n, k ) of an intersecting family of k -element subsets of { 1, 2, …, n } admitting a transitive group of automorphisms? We give upper and lower bounds for s ( n, k ), and show in particular that s ( n, k ) = o ( n − 1 k − 1 ) as n → ∞ if and only if k = n ∕ 2 − ω ( n ) ( n ∕ log n ) for some function ω ( ⋅ ) that increases without bound, thereby determining the threshold at which 'symmetric' intersecting families are negligibly small compared to the maximum-sized intersecting families. We also exhibit connections to some basic questions in group theory and additive number theory, and pose a number of problems.