Abstract
LetP be the convex hull of perfect matchings of a graphG=(V, E). The dominant ofP is {y∈R E∶y≥x for somex∈P}. A theorem of Fulkerson implies that, ifG is bipartite, then the dominant ofP 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 integern, there exists a graph for which the dominant has an essential valid inequality whose coefficient-set includes the firstn positive integers. A similar result holds for the submissive ofP, {y∈R E∶0≤y≤x for somex∈P}.
Similar content being viewed by others
References
G. Birkhoff, “Tres observaciones sobre el algebra lineal,”Universidad Nacionale Tucuman Revista 5 (1946) 147–151.
W.H. Cunningham, letter to D.R. Fulkerson, Dec. 19, 1974.
W.H. Cunningham, “An unbounded matroid intersection polyhedron,”Linear Algebra and its Applications 16 (1977) 209–215.
J. Edmonds, “Maximum matching and a polyhedron with 0–1 vertices,”Journal of Research of the National Bureau of Standards 69B (1965) 125–130.
J. Edmonds and R. Giles, “A min-max relation for submodular functions on graphs,”Annals of Discrete Methematics 1 (1977) 185–204.
D.R. Fulkerson, “Blocking polyhedra,” in: B. Harris, ed.,Graph Theory and its Applications (Academic Press, New York, 1970) pp. 93–112.
D.R. Fulkerson, “Blocking and anti-blocking pairs of polyhedra,”Mathematical Programming 1 (1971) 168–194.
D.R. Fulkerson and D.B. Weinberger, “Blocking pairs of polyhedra arising from network flows”Journal of Combinatorial Theory 18 (1975) 265–283.
C.J.H. McDiarmid, “Blocking, anti-blocking, and pairs of matroids and polymatroids,”Journal of Combinatorial Theory B25 (1978) 313–325.
J. Von Neumann, “A certain zero-sum two person game equivalent to the optimum assignment problem,” in: A. Tucker and H. Kuhn, eds.,Contributions to the Theory of Games II, Annals of Mathematics Study 38 (Princeton University Press, 1953) pp. 5–12.
D.B. Weinberger, “Network flows, minimum coverings, and the four-color conjecture,”Operations Research 24 (1976) 272–290.
Author information
Authors and Affiliations
Additional information
Research partially supported by a grant from NSERC of Canada.
Rights and permissions
About this article
Cite this article
Cunningham, W.H., Green-Krotki, J. Dominants and submissives of matching polyhedra. Mathematical Programming 36, 228–237 (1986). https://doi.org/10.1007/BF02592027
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02592027