# 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
Full Text: