Edge-covering number of 2-polymatroids

From Egres Open
Jump to: navigation, search

Let f be a 2-polymatroid function on S that has a matroid representation [math]M=(S \times \{1,2\},r)[/math] with the following property: [math]|C\cap \{(e,1),(e,2)\}| \leq 1[/math] for every [math]e \in S[/math] and every circuit C of M. Is it true that [math]\beta(f) \leq \beta^*(f)+1[/math], i.e. the minimum cover by matchings is at most one more than the minimum fractional cover by matchings?


The conjecture was proposed by Aharoni, Berger, and Ziv [1]; they show that the statement does not hold for general 2-polymatroids. Using the techniques in [2], one can prove that [math]\beta(f) \leq 2\beta^*(f)[/math] for any 2-polymatroid function f (see Theorem 3.6 in [1]).

The conjecture is a common generalization of the conjecture on Upper bound on common independent set cover and a version of the Goldberg-Seymour conjecture (Open Problem Garden) that states that the edge-colouring number of a multigraph is at most its fractional edge-colouring number plus one.


  1. 1.0 1.1 R. Aharoni, E. Berger, R. Ziv, The edge covering number of the intersection of two matroids, DOI link
  2. R. Aharoni, E. Berger, The intersection of a matroid and a simplicial complex, Trans. Amer. Math. Soc. 358 (2006), 4895-4917. Journal link. Citeseer link.