Toric ideal of matching polytopes and edge colorings

Kenta Mori, Ryo Motomura, Hidefumi Ohsugi and Akiyoshi Tsuchiya · 2025

Read Toric ideal of matching polytopes and edge colorings by Kenta Mori, Ryo Motomura, Hidefumi Ohsugi and Akiyoshi Tsuchiya (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-19209.txt.

Description

Matching points in a network, pairing them off by edges, can be packed into a geometric shape called the matching polytope. Kenta Mori and co-authors study the algebra of that shape in a 2025 paper, through its toric ideal, a set of binomial equations that describe it. The question is how complicated the simplest equations in that set can be.

For networks split into two camps, bipartite graphs, the ideal is known to need binomials of degree at most three. The authors show this fact is exactly a classic result about coloring the edges of bipartite multigraphs in disguise. They also characterize which bipartite graphs manage with degree two alone. The general graph case is explored, with a conjecture offered for the maximal degree needed.

Catalog record

CREATORKenta Mori, Ryo Motomura, Hidefumi Ohsugi and Akiyoshi Tsuchiya
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-19209

Browse the full library · About the Tower of Babel