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
| CREATOR | Kristóf Bérczi, Viktor Csaplár, Yutaro Yamaguchi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51226 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.20009