Gyula O.H. KATONA

( Rényi Institute, Budapest, Pf. 127, 1364, Węgry)

Forbidden inclusion patterns in families of subsets

Let [n]={1,2,...,n} be a finite set, families $\cal{F}$ of its subsets will be investigated. An old theorem of Sperner (1928) says that if there is no inclusion ( $F\in \cal{F}, G\in \cal{F}, F\ne G$ then $F\not\subset G$) then the largest family under this condition is the one contaning all $\lfloor {n\over 2}\rfloor$-element subsets of $[n]$. This theorem has many consequences. It helps to find (among others) the maximum number of mimimal keys in a database, the maximum number of subsums of secret numerical data what can be released without telling any one of the data, bounds of the distribution of the sums $\sum \pm a_i$ for the vectors $a_i (1\leq i\leq n)$.

We will consider its certain generalisations in the present lecture. They are useful in proving theorems in number theory. geometry, etc. Again, the maximum size of $\cal{F}$ is to be found under the condition that a certain configuration is excluded. The configuration here is always described by inclusions. More formally, let $P$ be a poset. The maximum size of a family ${\cal F}\subset 2^{[n]}$ which does not contain $P$ as a (non-necessarily induced) subposet is denoted by La$(n,P)$.

If $P$ consist of two comparable elements, then Sperner's theorem gives the answer, the maximum is ${n\choose \lfloor {n\over 2}\rfloor }$.

In most cases, however La$(n,P)$ is only asymptotically determined in the sense that the main term is the size of the largest level (sets of size $\lfloor {n\over 2}\rfloor$) while the second term is ${c\over n}$ times the second largest level where the lower and upper estimates contain different constants $c$.

Let the poset $N$ consist of 4 elements illustrated here with 4 distinct sets satisfying $A\subset B, C\subset B, C\subset D$. We were not able to determine La$(n,N)$ for a long time. Recently, a new method jointly developed by J.R. Griggs, helped us to prove the following theorem.

Theorem

$${n\choose \lfloor {n\over 2}\rfloor }\left( 1+{1\over n}+ o({1\... ...\choose \lfloor {n\over 2}\rfloor }\left( 1+{2\over n}+ o({1\over n})\right).$$

Serdecznie zapraszamy wszystkich chętnych !