Name
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 2 k ź 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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.dam.2016.01.008 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Extremal combinatorics,Families of subsets,Intersecting families | Discrete mathematics,Combinatorics,Complete intersection,Mathematics | Journal |
Volume | Issue | ISSN |
216 | P3 | 0166-218X |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gyula O. H. Katona | 1 | 264 | 66.44 |