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

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Межкафедральный семинар МФТИ по дискретной математике
25 октября 2017 г. 18:30, г. Долгопрудный, Актовый зал Лабораторного корпуса МФТИ
 


Possible profiles of Sperner families

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

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

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

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017