Partition-free families of sets

被引:7
作者
Frankl, Peter [1 ]
Kupayski, Andrey [2 ,3 ]
机构
[1] Renyi Inst, Budapest, Hungary
[2] Moscow Inst Phys & Technol, Lab Adv Combinator & Networks Applicat, Moscow 141701, Moskovskaya Obl, Russia
[3] Univ Oxford, Math Inst, Oxford OX1 2JD, England
基金
俄罗斯科学基金会;
关键词
05D05; 05D15 (primary); SUBSETS;
D O I
10.1112/plms.12236
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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)=nm+1+MIDLINE HORIZONTAL ELLIPSIS+n2m+1 if n=3m+1. Confirming the conjecture of Kleitman, we establish the same equality for the cases n=3m and n=3m+2, and also determine all extremal families. Unlike the case n=3m+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.
引用
收藏
页码:440 / 468
页数:29
相关论文
共 21 条