Comparable pairs in families of sets
Comparable pairs in families of sets
复制标题
集合族中的可比对
DOI：
10.1016/j.jctb.2015.05.009
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
B. Sudakov
中科院分区：
文献类型：
--
作者：
N. Alon;S. Das;R. Glebov;B. Sudakov
给定[n]的子集族F，若A ∈ B或B ∈ A，则称两个集合A，B是可比较的. Sperner的著名定理给出了没有任何可比对的最大家庭的规模。这个结果后来被Kleitman推广，他给出了在给定规模的家庭中出现的可比较对的最小数量。本文研究了Erdens，戴金和Frankl在80年代初提出的一个互补问题。他们要求在[n]的m个子集的族中可以出现的可比较对的最大数量，我们用c（n，m）表示这个量。首先解决了Alon和Frankl的一个猜想，证明了当m= n ω（1）2 n/2时，c（n，m）= o（m2）.我们还得到了c（n，m）在稀疏族和稠密族中的更精确的界，给出了m的某些值的极值结构，并改进了其它一些已知结果.
Given a family F of subsets of [n], we say two sets A, B∈ F are comparable if A⊂ B or B⊂ A. Sperner's celebrated theorem gives the size of the largest family without any comparable pairs. This result was later generalised by Kleitman, who gave the minimum number of comparable pairs appearing in families of a given size. In this paper we study a complementary problem posed by Erdős, Daykin and Frankl in the early'80s. They asked for the maximum number of comparable pairs that can appear in a family of m subsets of [n], a quantity we denote by c (n, m). We first resolve an old conjecture of Alon and Frankl, showing that c (n, m)= o (m 2) when m= n ω (1) 2 n/2. We also obtain more accurate bounds for c (n, m) for sparse and dense families, characterise the extremal constructions for certain values of m, and sharpen some other known results.
登录
查看更多内容
布尔晶格中的过饱和
影响因子：
--
作者：
A. P. Dove;Jerrold R. Griggs;Ross J. Kang;Jean
通讯作者：
Jean
关于生成具有不相交并的有限集的所有子集的注意事项
影响因子：
0.7
作者：
David Ellis
通讯作者：
David Ellis
弗兰克尔超图图兰问题
DOI：
--
发表时间：
2002
期刊：
Comb.
影响因子：
--
作者：
Peter Keevash;B. Sudakov
通讯作者：
B. Sudakov
DOI：
--
发表时间：
1985
期刊：
Graphs Comb.
影响因子：
--
作者：
N. Alon;P. Frankl
通讯作者：
P. Frankl