The clique complex and hypergraph matching

被引：61

作者：

Meshulam, R ^{[1
]}

机构：

[1] Technion Israel Inst Technol, Dept Math, IL-32000 Haifa, Israel

来源：

COMBINATORICA | 2001年 / 21卷 / 01期

基金：

以色列科学基金会;

关键词：

AMS Subject Classification (1991) Classes: 05D05, 05D15, 05E25;

D O I：

10.1007/s004930170006

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The width of a hypergraph F is the minimal t = w(F) for which there exist F-1,..., F-t is an element of F such that for any F is an element of F, F-i boolean AND F not equal circle divide for some 1 less than or equal to i less than or equal to t. The matching width of F is the minimal t = mw(F) such that for any matching M subset of F there exist F-1,..., F-t is an element of F such that for any F is an element of M, F(i)boolean ANDF not equal circle divide for some 1 less than or equal to i less than or equal to t. The following extension of the Aharoni-Haxell matching Theorem [3] is proved: Let {F-i}(i = 1)(m) be a family of hypergraphs such that for each circle divide not equal I subset of [m] either mw(Ui is an element ofIFi) greater than or equal to \I\ or w(Ui is an element ofIFi) greater than or equal to 2\I\ -1, then there exists a matching F-1,...,F-m such that F-i is an element of F-i for all 1 less than or equal to i less than or equal to m. This is a consequence of a more general result on colored cliques in graphs. The proofs are topological and use the Nerve Theorem.

引用

页码：89 / 94

页数：6