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

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




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


Possible profiles of Sperner families

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

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

Аннотация: 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.
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024