A Hierarchy of Edge-Weight Symmetries in Perfect Matchings

Kristóf Bérczi, Viktor Csaplár, Yutaro Yamaguchi · 2026

Read A Hierarchy of Edge-Weight Symmetries in Perfect Matchings by Kristóf Bérczi, Viktor Csaplár, Yutaro Yamaguchi (2026) 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-2604-20009.txt.

Description

Bérczi, Csaplár, and Yamaguchi study edge-weight symmetries in perfect matchings, motivated by finding perfect matchings of given rank. They define a hierarchy of weakening properties, from node-induced weights through even walk and cycle symmetries to matching equality and the min-max condition. The conditions coincide in bipartite graphs, with tight characterizations for general graphs via block and tight cut decompositions. A matching-covered non-bipartite counterexample settles the motivating question negatively: one fixed edge need not eliminate all minimum- or maximum-weight matchings.

Catalog record

CREATORKristóf Bérczi, Viktor Csaplár, Yutaro Yamaguchi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51226
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.20009

Browse the full library · About the Tower of Babel