THE STRUCTURE OF LARGE INTERSECTING FAMILIES

被引:20
作者
Kostochka, Alexandr [1 ,2 ]
Mubayi, Dhruv [3 ]
机构
[1] Univ Illinois, Urbana, IL 61801 USA
[2] Sobolev Inst Math, Novosibirsk 630090, Russia
[3] Univ Illinois, Dept Math Stat & Comp Sci, Chicago, IL 60607 USA
基金
俄罗斯基础研究基金会; 美国国家科学基金会;
关键词
FINITE SETS; HYPERGRAPH; THEOREMS; SYSTEMS;
D O I
10.1090/proc/13390
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A collection of sets is intersecting if every two members have nonempty intersection. We describe the structure of intersecting families of r-sets of an n-set whose size is quite a bit smaller than the maximum (n-1 r-1) given by the Erd. os-Ko-Rado Theorem. In particular, this extends the Hilton-Milner theorem on nontrivial intersecting families and answers a recent question of Han and Kohayakawa for large n. In the case r = 3 we describe the structure of all intersecting families with more than 10 edges. We also prove a stability result for the Erd. os matching problem. Our short proofs are simple applications of the Delta-system method introduced and extensively used by Frankl since 1977.
引用
收藏
页码:2311 / 2321
页数:11
相关论文
共 17 条
[1]   SETS OF INDEPENDENT EDGES OF A HYPERGRAPH [J].
BOLLOBAS, B ;
DAYKIN, DE ;
ERDOS, P .
QUARTERLY JOURNAL OF MATHEMATICS, 1976, 27 (105) :25-32
[2]   INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS [J].
ERDOS, P ;
RADO, R ;
KO, C .
QUARTERLY JOURNAL OF MATHEMATICS, 1961, 12 (48) :313-&
[3]  
Erdos P., 1965, Ann. Univ. Sci. Budapest. Eotvos Sect. Math, V8, P93
[4]  
Erdos P., 1975, INFINITE FINITE SETS, V10, P609
[5]  
Erdos P., 1950, J LOND MATH SOC, V25, P249
[6]   ERDOS-KO-RADO THEOREM WITH CONDITIONS ON THE MAXIMAL DEGREE [J].
FRANKL, P .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1987, 46 (02) :252-263
[7]   INTERSECTING FAMILIES OF FINITE SETS [J].
FRANKL, P .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1978, 24 (02) :146-161
[8]  
Frankl P., 1977, Bull. Austral. Math. Soc., V17, P125
[9]  
Frankl P., 1980, Bull. Austral. Math. Soc, V21, P363
[10]  
Frankl P., ARXIV12056847