Strongly maximal matchings

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


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?


Remarks

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

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]. A previous version of this page contained an analogous conjecture for vertex covers; however the following example by Eli Berger shows that there are graphs with no strongly minimal vertex cover. For every [math]n \in \mathbb{N}[/math], let [math]V_n[/math] be a node set of size [math]n[/math]. Two nodes [math]u \in V_i[/math] and [math]v \in V_j[/math] are connected if and only if [math]i \neq j[/math]. It is easy to check that the inclusionwise minimal vertex covers are complements of [math]V_n[/math] ([math]n \in \mathbb{N}[/math]), so there is no strongly minimal one.

References

  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.