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

Iz MaFiRaWiki

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).


{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.

Glej tudi

Matematični kolokviji

Osebna orodja