On symmetric intersecting families of vectors. (18th November 2021)

• Record Type: Journal Article
• Authors: Eberhard, Sean; Kahn, Jeff; Narayanan, Bhargav; Spirkl, Sophie
• Is Part Of: Combinatorics, probability and computing. Volume 30:Number 6(2021)
• Page Start: 899
• Page End: 904
• Publication Date: 2021-11-18
• Subjects: 05D05 -- 05E18; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548321000079
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract: A family of vectors in [ k ] n is said to be intersecting if any two of its elements agree on at least one coordinate. We prove, for fixed k ≥ 3, that the size of any intersecting subfamily of [ k ] n invariant under a transitive group of symmetries is o ( k n ), which is in stark contrast to the case of the Boolean hypercube (where k = 2). Our main contribution addresses limitations of existing technology: while there are now methods, first appearing in work of Ellis and the third author, for using spectral machinery to tackle problems in extremal set theory involving symmetry, this machinery relies crucially on the interplay between up-sets, biased product measures, and threshold behaviour in the Boolean hypercube, features that are notably absent in the problem considered here. To circumvent these barriers, introducing ideas that seem of independent interest, we develop a variant of the sharp threshold machinery that applies at the level of products of posets.