Normality of k-Matching Polytopes of Bipartite Graphs

• Autores: Juan Camilo Torres
• Localización: Revista Colombiana de Matemáticas, ISSN-e 0034-7426, Vol. 57, Nº. 2, 2023, págs. 193-206
• Idioma: varios idiomas
• Títulos paralelos:
  • Normalidad del politopo de k-emparejamientos de grafos bipartitos
• Enlaces
  • Texto completo
• Resumen
  • español

    El politopo de k-emparejamientos de un grafo es la envolvente convexa de todos sus emparejamientos de un tamaño dado k cuando estos son considerados como vectores indicadores. En este artículo, demostramos que el politopo de k-emparejamientos de un grafo bipartito es normal, es decir, todo punto entero en su t-dilatación es la suma de t puntos enteros del politopo original. Esto generaliza el resultado conocido de que los politopos de Birkhoff son normales. Como resultado preliminar, demostramos que para grafos bipartitos el politopo de k-emparejamientos es igual al politopo de k-emparejamientos fraccional, teniendo así la H-representación del politopo. Esto generaliza el Teorema de Birkhoff-Von Neumann que establece que toda matriz doblemente estocástica puede ser escrita como una combinación convexa de matrices de permutación.

  • Multiple

    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.

• Referencias bibliográficas
  • R. E. Behrend, Fractional perfect b-matching polytopes i: General theory, Linear Algebra and its Applications 439 (2013), no. 12, 3822-3858.
  • W. Bruns and J. Gubeladze, Polytopes, rings, and k-theory, Springer, 2009.
  • D. A. Cox, C. Haase, T. Hibi, and A. Higashitani, Integer decomposition property of dilated polytopes, The Electronic Journal of Combinatorics...
  • D. A. Cox, J. B. Little, and H. K. Schenck, Toric varieties, vol. 124, American Mathematical Soc., 2011.
  • D-Z. Du and K-I. Ko, Theory of computational complexity, vol. 58, John Wiley & Sons, 2011.
  • J. Gill and S. Linusson, The k-assignment polytope, Discrete Optimization 6 (2009), no. 2, 148-161.
  • J. Gubeladze, Normal polytopes: Between discrete, continuous, and random, Journal of Pure and Applied Algebra 227 (2023), no. 2, 107187.
  • J. De Loera, J. Rambau, and F. Santos, Triangulations: structures for algorithms and applications, vol. 25, Springer Science & Business...
  • L. Lovasz and M. D. Plummer, Matching theory, vol. 367, American Mathematical Soc., 2009.
  • J. C. Torres, The slack model in the study of polytopes, Ph.D. thesis, Universidad de los Andes, 2020.