1. Normality of k-Matching Polytopes of Bipartite Graphs.
- Author
-
CAMILO TORRES, JUAN
- Subjects
- *
STOCHASTIC matrices , *POLYTOPES , *INTEGERS , *PERMUTATIONS , *BIPARTITE graphs , *MATRICES (Mathematics) - Abstract
The k-matching polytope of a graph is the convex hull of all its matchings of a given size k when they are considered as indicator vectors. In this paper, we prove that the k-matching polytope of a bipartite graph is normal, that is, every integer point in its t-dilate is the sum of t integers points of the original polytope. This generalizes the known fact that Birkhoff polytopes are normal. As a preliminary result, we prove that for bipartite graphs the k-matching polytope is equal to the fractional k -matching polytope, having thus the H -representation of the polytope. This generalizes the Birkhoff-Von Neumann Theorem which establish that every doubly stochastic matrix can be written as a convex combination of permutation matrices. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF