Katona, Gyula O. H.; Matematični kolokvij marec 2010

Bounds on the largest families of subsets with forbidden subposets

Gyula O. H. Katona

Matematični inštitut Alfréd Rényi, Budimpešta, Madžarska

25. marec 2010

Let $[n] = \{1,2,\dots,n\}$ be a finite set, families $\mathcal{F}$ of its subsets will be investigated. An old theorem of Sperner (1928) says that if there is no inclusion ($F \in \mathcal{F}, G \in \mathcal{F}, F \neq G$ then $F \not\subset G$) then the largest family under this condition is the one contaning all $\lfloor n/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 ai $(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 $\mathcal{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 $\mathcal{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/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/2\rfloor$) while the second term is c / n times the second largest level where the lower and upper estimates contain different constants c.

Let e.g. the poset N consist of 4 elements illustrated here with 4 distinct sets satisfying $A \subset B, C \subset B, C \subset D$. In a relatively new paper the author jointly with J.R. Griggs determined La(n,N).

Theorem

${n \choose \lfloor n/2 \rfloor}\left(1 + 1/n + \Omega(1/n^2)\right) \leq \mathrm{La}(n, N) \leq {n \choose \lfloor n/2 \rfloor}\left(1 + 2/n + O(1/n^2)\right)$

Similar results will be surveyed, also introducing a method.