2023/06/20 by Juan Camilo Torres, Torres, Juan Camilo
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2306.11910
openalex publication_date 2023/06/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.