|
|
Межкафедральный семинар МФТИ по дискретной математике
25 октября 2017 г. 18:30, г. Долгопрудный, МФТИ, Корпус Прикладной Математики, 115
|
|
|
|
|
|
Possible profiles of Sperner families
Г. О. X. Катона |
Количество просмотров: |
Эта страница: | 355 |
|
Аннотация:
Let $[n]=\{ 1,2, \ldots , n\}$ be our underlying set. We will consider families $\cal F\subset 2^{[n]}$ of subsets of $[n]$. Sperner's theorem claims that the maximum of $|\cal F|$ is ${n\choose \lfloor n/2 \rfloor}$ under the condition that $\cal F$ contains no pair of distinct members $F, G$ such that $F\subset G$. (Such families will be called Sperner families in what follows.)
The so-called YBLM-inequality
$$\sum_{F\in \cal F}{1\over {n\choose |F|}}\leq 1$$
also holds for Sperner families. This is an obvious strengthening of Sperner's theorem.
Let $\cal F_i$ be the subfamily of $\cal F$ consisting of its $i$-element members. Introducing the notation
$f_i=f_i(\cal F)=|\cal F_i|$ the YBLM-inequality can be rewritten in the following form.
$$\sum_{i=0}^n{f_i\over {n\choose i}}\leq 1.$$
Call the vector $(f_0(\cal F), f_1(\cal F),\ldots ,f_n(\cal F))$ the profile vector of
$\cal F$. The inequality expresses that the profile vectors of Sperner families are below
the corresponding hyperplane. Bey gave a strengthening: a stronger quadratic inequality having the same property. Griggs and the author improved Bey's inequality by a system of pieces of hyperplanes.
|
|