  RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  Ближайшие семинары Календарь семинаров Список семинаров Архив по годам Регистрация семинара Поиск RSS Ближайшие семинары

Межкафедральный семинар МФТИ по дискретной математике
25 октября 2017 г. 18:30, г. Долгопрудный, МФТИ, Корпус Прикладной Математики, 115  Possible profiles of Sperner families

Г. О. X. Катона

 Количество просмотров: Эта страница: 142

Аннотация: 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.

 ОТПРАВИТЬ:       Обратная связь: math-net2020_05 [at] mi-ras ru Пользовательское соглашение Регистрация Логотипы © Математический институт им. В. А. Стеклова РАН, 2020