Intersecting families of sets are typically trivial

József Balogh, Ramon I. Garcia, Lina Li, Adam Zsolt Wagner

Research output: Contribution to journalArticlepeer-review

Abstract

A family of subsets of [n] is intersecting if every pair of its sets intersects. Determining the structure of large intersecting families is a central problem in extremal combinatorics. Frankl–Kupavskii and Balogh–Das–Liu–Sharifzadeh–Tran showed that for n≥2k+ckln⁡k, almost all k-uniform intersecting families are stars. Improving their result, we show that the same conclusion holds for n≥2k+100ln⁡k. Our proof uses, among others, the graph container method and the Das–Tran removal lemma.

Original languageEnglish (US)
Pages (from-to)44-67
Number of pages24
JournalJournal of Combinatorial Theory. Series B
Volume164
DOIs
StatePublished - Jan 2024

Keywords

  • Extremal combinatorics
  • Graph container method
  • Intersecting family

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Intersecting families of sets are typically trivial'. Together they form a unique fingerprint.

Cite this