On symmetric intersecting families of vectors

Sean Eberhard, Jeff Kahn, Bhargav Narayanan*, Sophie Spirkl

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

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(kn), 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.

Original languageEnglish
Pages (from-to)899 - 904
JournalCombinatorics Probability and Computing
Volume30
Issue number6
Early online date18 Mar 2021
DOIs
Publication statusPublished - Nov 2021
Externally publishedYes

Bibliographical note

Publisher Copyright:
© The Author(s), 2021. Published by Cambridge University Press.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'On symmetric intersecting families of vectors'. Together they form a unique fingerprint.

Cite this