Nearly perfect matchings in regular simple hypergraphs

被引:59
作者
Alon, N
Kim, JH
Spencer, J
机构
[1] TEL AVIV UNIV,RAYMOND & BEVERLY SACKLER FAC EXACT SCI,DEPT MATH,IL-69978 TEL AVIV,ISRAEL
[2] NYU,COURANT INST,DEPT MATH & COMP SCI,NEW YORK,NY
关键词
Perfect MATCHINGS; Dependency Graph; Partial System; Steiner Triple System; Steiner System;
D O I
10.1007/BF02773639
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For every fixed k greater than or equal to 3 there exists a constant c(k) with the following property. Let H be a k-uniform, D-regular hypergraph on N vertices, in which no two edges contain more than one common vertex. If k > 3 then H contains a matching covering all vertices but at most c(k)ND(-1/(k-1)). If k = 3, then H contains a matching covering all vertices but at most c(3)ND(-1/2) ln(3/2) D. This improves previous estimates and implies, for example, that any Steiner Triple System on N vertices contains a matching covering all vertices but at most O(N-1/2 ln3/2 N)) improving results by various authors.
引用
收藏
页码:171 / 187
页数:17
相关论文
共 16 条
[1]  
Ajtai M., 1981, EUR J COMBIN, V2, P1
[2]  
Alon N., 1992, PROBABILISTIC METHOD
[3]   ON THE SIZE OF A MAXIMUM TRANSVERSAL IN A STEINER TRIPLE SYSTEM [J].
BROUWER, AE .
CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 1981, 33 (05) :1202-1204
[4]  
ERDOS P, 1963, PUBL MATH-DEBRECEN, V10, P10
[5]  
Frankl P., 1985, EUROPEAN J COMBIN, V6, P317
[6]  
GORDON DM, 1995, ASYMPTOTICALLY OPTIM
[7]  
GRABLE DA, 1995, MORE NEARLY PERFECT
[8]   Asymptotically good list-colorings [J].
Kahn, J .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1996, 73 (01) :1-59
[9]   THE RAMSEY NUMBER R(3,T) HAS ORDER OF MAGNITUDE T(2)/LOG-T [J].
KIM, JH .
RANDOM STRUCTURES & ALGORITHMS, 1995, 7 (03) :173-207
[10]   PARTIAL PARALLEL CLASSES IN STEINER SYSTEMS [J].
LINDNER, CC ;
PHELPS, KT .
DISCRETE MATHEMATICS, 1978, 24 (01) :109-112