Strongly maximal matchings, strongly minimal vertex covers

From Egres Open
Jump to: navigation, search

For a hypergraph [math]H=(V,E) [/math], we call [math]M \subseteq E [/math] a matching if the elements of [math]M [/math] are pairwise disjoint, and we call [math]C\subseteq V [/math] a vertex cover if it meets every hyperedge. A matching [math]M [/math] is strongly maximal if [math]\left|M'\setminus M\right|\leq \left|M\setminus M'\right| [/math] holds for any matching [math]M' [/math]. A vertex cover [math]C [/math] is strongly minimal if [math]\left|C\setminus C'\right|\leq \left|C'\setminus C\right| [/math] holds for any cover [math]C' [/math].

Is it true that if all the hyperedges of a hypergraph [math]H [/math] have size at most [math]k [/math] for some [math]k\in \mathbb{N} [/math], then [math]H [/math] admits a strongly maximal matching and a strongly minimal cover?


In the case of graphs the existence of a strongly maximal matching is known to be true ([1] p. 16. Theorem 5.6). The existence of strongly maximal matching conjectured originally under the assumption that the hyperedges are finite but it turned out to be false [2].


  1. R. Diestel and C.St.J.A. Nash-Williams, Directions in infinite graph theory and combinatorics, North-Holland, 1992. author link
  2. Ahlswede, Rudolf, and Levon H. Khachatrian. "A counterexample to Aharoni's strongly maximal matching conjecture." Discrete Mathematics 149.1 (1996): 289.