×

zbMATH — the first resource for mathematics

The clique complex and hypergraph matching. (English) Zbl 1107.05302
Summary: The width of a hypergraph \(\mathcal F\) is the minimal \(t=\text{w}(\mathcal F)\) for which there exist \(F_1,\dots ,F_t\in \mathcal F\) such that for any \(F \in \mathcal F\), \(F_i \cap F \neq \emptyset\) for some \(1 \leq i \leq t\). The matching width of \(\mathcal F\) is the minimal \(t=\text{mw}(\mathcal F)\) such that for any matching \(\mathcal M \subset \mathcal F\) there exist \(F_1,\dots,F_t \in \mathcal F\) such that for any \(F \in \mathcal M\), \(F_i\cap F \neq \emptyset\) for some \(1 \leq i \leq t\). The following extension of the Aharoni-Haxell matching theorem [R. Aharoni, P. Haxell, J. Graph Theory, 35, 83–88 (2000; Zbl 0956.05075)] is proved:
Let \(\{\mathcal F_i \}_{i=1}^m\) be a family of hypergraphs such that for each \(\emptyset \neq I\subset [m]\) either \(\text{mw}(\cup_{i\in I} \mathcal F_i) \geq | I| \) or \(\text{w}(\cup_{i \in I}\mathcal F_i) \geq 2| I| -1\), then there exists a matching \(F_1,\dots,F_m\) such that \(F_i \in \mathcal F_i\) for all \(1 \leq i \leq m\).
This is a consequence of a more general result on colored cliques in graphs. The proofs are topological and use the nerve theorem.

MSC:
05C05 Trees
05D05 Extremal set theory
05D15 Transversal (matching) theory
05E25 Group actions on posets, etc. (MSC2000)
Keywords:
clique; hypergraph
PDF BibTeX XML Cite
Full Text: DOI