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

### Iz MaFiRaWiki

Različica od 15:36, 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 <math>\mathcal{F}</math> 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 <math>P</math> be a poset. The maximum size of a family | inclusions. More formally, let <math>P</math> be a poset. The maximum size of a family | ||

Vrstica 33: |
Vrstica 33: | ||

In most cases, however <math>\mathrm{La}(n, P)</math> is only asymptotically | In most cases, however <math>\mathrm{La}(n, P)</math> 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 <math>\langle n/2\rangle</math>) while the second term is <math>c/n</math> times the second largest level where the lower and upper estimates contain different constants <math>c</math>. | + | (sets of size <math>\lfloor n/2\rfloor</math>) while the second term is <math>c/n</math> times the second largest level where the lower and upper estimates contain different constants <math>c</math>. |

Let e.g. the poset <math>N</math> consist of 4 elements illustrated here with 4 distinct | Let e.g. the poset <math>N</math> consist of 4 elements illustrated here with 4 distinct | ||

sets satisfying <math>A \subset B, C \subset B, C \subset D</math>. | sets satisfying <math>A \subset B, C \subset B, C \subset D</math>. | ||

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

- | <math>\mathrm{La}(n, P)</math>. | + | <math>\mathrm{La}(n, N)</math>. |

- | Theorem | + | '''Theorem''' |

<math> | <math> | ||

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

</math> | </math> | ||

Similar results will be surveyed, also introducing a method. | Similar results will be surveyed, also introducing a method. | ||

+ | |||

==Glej tudi== | ==Glej tudi== |

## Trenutna različica

## 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 be a finite set,
families of its subsets will be investigated.
An old theorem of Sperner (1928) says that if there is no inclusion
( then )
then the largest family under this condition
is the one contaning all -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 for the vectors *a*_{i}
.

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

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 ) 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 .
In a relatively new paper the author jointly with J.R. Griggs determined
La(*n*,*N*).

**Theorem**

Similar results will be surveyed, also introducing a method.