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

(Razlika med različicami)
 Različica od 15:38, 18 marec 2010MarkoBoben (Pogovor | prispevki)← Prejšnja različica Trenutna različicaMarkoBoben (Pogovor | prispevki) Vrstica 3: Vrstica 3: '''Gyula O. H. Katona''' '''Gyula O. H. Katona''' - Matematični inštitut Alfréd Rényi + Matematični inštitut Alfréd Rényi, Budimpešta, Madžarska 25. marec 2010 25. marec 2010 Vrstica 22: Vrstica 22: We will consider its certain generalisations in the present lecture. They We will consider its certain generalisations in the present lecture. They are useful in proving theorems in number theory, geometry, etc. Again, 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 + 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 configuration is excluded. The configuration here is always described by inclusions. More formally, let $P$ be a poset. The maximum size of a family inclusions. More formally, let $P$ be a poset. The maximum size of a family Vrstica 33: Vrstica 33: In most cases, however $\mathrm{La}(n, P)$ is only asymptotically In most cases, however $\mathrm{La}(n, P)$ is only asymptotically determined in the sense that the main term is the size of the largest level 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$. + (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 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$. sets satisfying $A \subset B, C \subset B, C \subset D$. In a relatively new paper the author jointly with J.R. Griggs determined In a relatively new paper the author jointly with J.R. Griggs determined - $\mathrm{La}(n, P)$. + $\mathrm{La}(n, N)$. - Theorem + '''Theorem''' $[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, N) \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] Similar results will be surveyed, also introducing a method. Similar results will be surveyed, also introducing a method. + ==Glej tudi== ==Glej tudi==

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