Premium
Partition‐free families of sets
Author(s) -
Frankl Peter,
Kupavskii Andrey
Publication year - 2019
Publication title -
proceedings of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.899
H-Index - 65
eISSN - 1460-244X
pISSN - 0024-6115
DOI - 10.1112/plms.12236
Subject(s) - mathematics , disjoint sets , conjecture , partition (number theory) , combinatorics , mathematical proof , family of sets , extremal combinatorics , discrete mathematics , set (abstract data type) , geometry , computer science , programming language
Let m ( n ) denote the maximum size of a family of subsets which does not contain two disjoint sets along with their union. In 1968, Kleitman proved that m ( n ) = n m + 1+ ⋯ + n 2 m + 1if n = 3 m + 1 . Confirming the conjecture of Kleitman, we establish the same equality for the cases n = 3 m and n = 3 m + 2 , and also determine all extremal families. Unlike the case n = 3 m + 1 , the extremal families are not unique. This is a plausible reason behind the relative difficulty of our proofs. We completely settle the case of several families as well.