Prof. dr. Gyula O.H. Katona: Bounds on the largest families of subsets with forbidden subposets
Gyula O.H. Katona
Matematični inštitut Alfréd Rényi, Budimpešta
25. marec 2010
Let [n] = {1, 2, …, n} be a finite set, families F of its subsets will be investigated. An old theorem of Sperner (1928) says that if there is no inclusion (F ∈ F, G ∈ F, F ≠ G then F ⊄ G) then the largest family under this conditionis the one contaning all ⌊n/2⌋-element subsets of [n]. This theorem has many consequences. It helps to find (among others) the maximum numberof 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 Σ ±ai for the vectors ai(1 ≤ i ≤ 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 certainconfiguration is excluded. The configuration here is always described byinclusions. More formally, let P be a poset. The maximum size of a family F ⊂ 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 ⌊n/2⌋. 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 ⌊n/2⌋) 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 ⊂ B, C ⊂ B, C ⊂ D. In a relatively new paper the author jointly with J.R. Griggs determined La(n, N).
