Arithmetic of marked order polytopes, monotone triangle reciprocity, and\n partial colorings

2012/06/18 by Katharina Jochemko, Jochemko, Katharina, Raman Sanyal +1
Mathematics · #06A07 #06A11 #52B12 #52B20 #Advanced Combinatorial Mathematics #Census and Population Estimation #Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG)

paper · pdf · doi:10.48550/arxiv.1206.4066

openalex publication_date 2012/06/18 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28

Abstract

For a poset P, a subposet A, and an order preserving map F from A into the\nreal numbers, the marked order polytope parametrizes the order preserving\nextensions of F to P. We show that the function counting integral-valued\nextensions is a piecewise polynomial in F and we prove a reciprocity statement\nin terms of order-reversing maps. We apply our results to give a geometric\nproof of a combinatorial reciprocity for monotone triangles due to Fischer and\nRiegler (2011) and we consider the enumerative problem of counting extensions\nof partial graph colorings of Herzberg and Murty (2007).\n

Related

• Order polynomials and Pólya's enumeration theorem
• Generalized Monotone Triangles: an extended Combinatorial Reciprocity Theorem
• Combinatorial Reciprocity for Monotone Triangles
• What is -Q for a poset Q?
• On piecewise-linear homeomorphisms between distributive and\n anti-blocking polyhedra