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

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 15:36, 18 marec 2010
MarkoBoben (Pogovor | prispevki)

← Prejšnja različica
Trenutna različica
MarkoBoben (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 [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.


Glej tudi

Matematični kolokviji

Osebna orodja