Around the Complete Intersection Theorem

Katona, Gyula (2017) Around the Complete Intersection Theorem. DISCRETE APPLIED MATHEMATICS, 216. pp. 618-621. ISSN 0166-218X

Preview

Text 1602.02634v1.pdf Download (90kB) | Preview

Abstract

In their celebrated paper, Erdos et al. (1961) posed the following question. Let F be a family of k-element subsets of an n-element set satisfying the condition that |F∩G|≥ℓ holds for any two members of F where ℓ≤k are fixed positive integers. What is the maximum size |F| of such a family? They gave a complete solution for the case ℓ=1: the largest family is the one consisting of all k-element subsets containing a fixed element of the underlying set. (One has to suppose 2k≤n, otherwise the problem is trivial.) They also proved that the best construction for arbitrary ℓ is the family consisting of all k- element subsets containing a fixed ℓ-element subset, but only for large n's. They also gave an example showing that this statement is not true for small n'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. © 2016 Elsevier B.V.

Actions (login required)

Edit Item