Improved bounds for Erdos' Matching Conjecture

被引：97

作者：

Frankl, Peter ^{[1
]}

机构：

[1] Renyi Inst Math, Budapest, Hungary

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES A | 2013年 / 120卷 / 05期

关键词：

Hypergraphs; Matching number; Erdos Conjecture; Katona's Theorem on shadows of intersecting hypergraphs; INTERSECTION-THEOREMS; SYSTEMS; EDGES;

D O I：

10.1016/j.jcta.2013.01.008

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The main result is the following. Let F be a family of k-subsets of an n-set, containing no s + 1 pairwise disjoint edges. Then for n >= (2s + 1)k - s one has vertical bar F vertical bar <= ((n)(k)) - ((n-s)(k)). This upper bound is the best possible and confirms a conjecture of Erdos dating back to 1965. The proof is surprisingly compact. It applies a generalization of Katona's Intersection Shadow Theorem. (C) 2013 Elsevier Inc. All rights reserved.

引用

页码：1068 / 1072

页数：5

共 15 条

[1] Large matchings in uniform hypergraphs and the conjectures of Erdos and Samuels
Alon, Noga
Frank, Peter
Huang, Hao
Roedl, Vojtech
Rucinski, Andrzej
Sudakov, Benny
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 2012, 119 (06) : 1200 - 1215
[2] Nonnegative k-sums, fractional covers, and probability of small deviations
Alon, Noga
Huang, Hao
Sudakov, Benny
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2012, 102 (03) : 784 - 796
[3] [Anonymous], ARXIV12024196
[4] SETS OF INDEPENDENT EDGES OF A HYPERGRAPH
BOLLOBAS, B
DAYKIN, DE
ERDOS, P
[J]. QUARTERLY JOURNAL OF MATHEMATICS, 1976, 27 (105) : 25 - 32
[5] INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
ERDOS, P
RADO, R
KO, C
[J]. QUARTERLY JOURNAL OF MATHEMATICS, 1961, 12 (48) : 313 - &
[6] Erdos Paul, 1965, Ann. Univ. Sci. Budapest. Eotvos Sect. Math, V8, P93
[7] Erdos Paul, 1959, Acta Math. Acad. Sci. Hungar, V10, P337, DOI [10.1007/bf02024498, DOI 10.1007/BF02024498]
[8] Frankl P., 2012, ARXIV12056847
[9] Frankl P., 1995, HDB COMBINATORICS, V2, P1293
[10] Frankl P, 2012, ELECTRON J COMB, V19

← 1 2 →