Around the Complete Intersection Theorem

详细信息    查看全文

• 作者：Gyula O.H. Katona ^{ohkatona@renyi.hu}
• 关键词：Extremal combinatorics ; Families of subsets ; Intersecting families
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：216
• 期：part_P3
• 页码：618-621
• 全文大小：359 K
• 卷排序：216

文摘

In their celebrated paper, Erdos et al. (1961) posed the following question. Let FF be a family of kk-element subsets of an nn-element set satisfying the condition that |F∩G|≥ℓ|F∩G|≥ℓ holds for any two members of FF where ℓ≤kℓ≤k are fixed positive integers. What is the maximum size |F||F| of such a family? They gave a complete solution for the case ℓ=1ℓ=1: the largest family is the one consisting of all kk-element subsets containing a fixed element of the underlying set. (One has to suppose 2k≤n2k≤n, otherwise the problem is trivial.) They also proved that the best construction for arbitrary ℓℓ is the family consisting of all kk- element subsets containing a fixed ℓℓ-element subset, but only for large nn’s. They also gave an example showing that this statement is not true for small nn’s.Later Frankl gave a construction for the general case that he believed to be the best. Frankl, Wilson and Füredi made serious progress towards the proof of this conjecture, but the complete solution was not achieved until 1996 when the surprising news came: Rudolf Ahlswede and Levon Khachatrian have found the proof. They invented the expressive name: Complete Intersection Theorem.We will show some of the consequences of this deep and important theorem.