Normality of k-Matching Polytopes of Bipartite Graphs

arXiv2306.11910MaRDI QIDQ6440923FDOQ6440923

Authors: Juan Camilo Torres 

Publication date: 20 June 2023

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.

This page was built for publication: Normality of $k$-Matching Polytopes of Bipartite Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6440923)