Dominants and submissives of matching polyhedra (Q4726052)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3999666
Language Label Description Also known as
default for all languages
No label defined
    English
    Dominants and submissives of matching polyhedra
    scientific article; zbMATH DE number 3999666

      Statements

      Dominants and submissives of matching polyhedra (English)
      0 references
      0 references
      0 references
      1986
      0 references
      matching polyhedra
      0 references
      facet-inducing inequality
      0 references
      perfect matchings of a graph
      0 references
      dominant
      0 references
      essential valid inequality
      0 references
      Let P be the convex hull of perfect matchings of a graph \(G=(V,E)\). The dominant of P is \(\{y\in R^ E:\) \(y\geq x\) for some \(x\in P\}\). A theorem of Fulkerson implies that, if G is bipartite, then the dominant of P can be described by linear inequalities having \(\{\) 0,1\(\}\)-valued coefficients. However, this is far from true in general. Here it is proved that, for every positive integer n, there exists a graph for which the dominant has an essential valid inequality whose coefficient-set includes the first n positive integers. A similar result holds for the submissive of P, \(\{y\in R^ E:\) \(0\leq y\leq x\) for some \(x\in P\}\).
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references