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

(Razlika med različicami)
 Različica od 15:36, 18 marec 2010MarkoBoben (Pogovor | prispevki)← Prejšnja različica Različica od 15:38, 18 marec 2010MarkoBoben (Pogovor | prispevki) Naslednja različica → Vrstica 43: Vrstica 43: $[itex] - n \choose {\lfloor n/2 \rfloor})\left(1 + 1/n + \Omega(1/n^2)\right) + {n \choose \lfloor n/2 \rfloor}\left(1 + 1/n + \Omega(1/n^2)\right) \leq \mathrm{La}(n, P) \leq \leq \mathrm{La}(n, P) \leq - n \choose {\lfloor n/2 \rfloor})\left(1 + 2/n + O(1/n^2)\right) + {n \choose \lfloor n/2 \rfloor}\left(1 + 2/n + O(1/n^2)\right)$ [/itex]

## Bounds on the largest families of subsets with forbidden subposets

Gyula O. H. Katona

Matematični inštitut Alfréd Rényi

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 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 $\langle n/2\rangle$) 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,P).

Theorem

${n \choose \lfloor n/2 \rfloor}\left(1 + 1/n + \Omega(1/n^2)\right) \leq \mathrm{La}(n, P) \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.