Browsing by Autor "Juan Camilo Torres"

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • Thumbnail Image
    Item type: Item ,
    Normality of k-Matching Polytopes of Bipartite Graphs
    (National University of Colombia, 2024) Juan Camilo Torres
    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.