Maximal 3-Wise Intersecting Families

József Balogh, Ce Chen, Kevin Hendrey, Ben Lund, Haoran Luo, Casey Tompkins, Tuan Tran

Research output: Contribution to journalArticlepeer-review

Abstract

A family F on ground set [n] : = { 1 , 2 , … , n} is maximal k-wise intersecting if every collection of at most k sets in F has non-empty intersection, and no other set can be added to F while maintaining this property. In 1974, Erdős and Kleitman asked for the minimum size of a maximal k-wise intersecting family. We answer their question for k= 3 and sufficiently large n. We show that the unique minimum family is obtained by partitioning the ground set [n] into two sets A and B with almost equal sizes and taking the family consisting of all the proper supersets of A and of B.

Original languageEnglish (US)
Pages (from-to)1045-1066
Number of pages22
JournalCombinatorica
Volume43
Issue number6
DOIs
StatePublished - Dec 2023

Keywords

  • Intersecting
  • Maximal
  • Saturation
  • Set-system

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Maximal 3-Wise Intersecting Families'. Together they form a unique fingerprint.

Cite this