Generalized Laminar Families and Certain Forbidden Matrices
Generalized Laminar Families and Certain Forbidden Matrices
复制标题
广义层状族和某些禁止矩阵
作者：
P. Dukes
回想一下，在层流族中，任何两个集合要么不相交，要么包含在另一个集合中。在这里，这个条件的参数化弱化。假设一个集合系统F <$2X $\mathcal {F} \subseteq 2^{X}$是t-层的，如果A，B∈F$A，B \in \mathcal {F}$，|A、B、B| ≥t$|A \cap B|\ge t$意味着A将B$A \subseteq B$或B将A$B \subseteq A$。我们得到了关于2-层流族F <$2 [n]$\mathcal {F} \subseteq 2^{[n]}$的最大尺寸的关于n的非常接近的渐近界。文中还给出了3-层族的构造和一般t的初步分析。
Recall that in a laminar family, any two sets are either disjoint or contained one in the other. Here, a parametrized weakening of this condition is introduced. Let us say that a set system F⊆2X$\mathcal {F} \subseteq 2^{X}$ is t-laminar if A,B∈F$A,B \in \mathcal {F}$ with |A∩B|≥t$|A \cap B| \ge t$ implies A⊆B$A \subseteq B$ or B⊆A$B \subseteq A$. We obtain very close asymptotic bounds in terms of n on the maximum size of a 2-laminar family F⊆2[n]$\mathcal {F} \subseteq 2^{[n]}$. A construction for 3-laminar families and a crude analysis for general t are also given.