Improved bounds for Erdos' Matching Conjecture

被引：102

作者：

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 [J].