arxiv: 2604.20009 · v1 · submitted 2026-04-21 · 🧮 math.CO · cs.DM

Recognition: unknown

A hierarchy of edge-weight symmetries in perfect matchings

Krist\'of B\'erczi , Viktor Csapl\'ar , Yutaro Yamaguchi

Authors on Pith no claims yet

Pith reviewed 2026-05-10 01:34 UTC · model grok-4.3

classification 🧮 math.CO cs.DM

keywords perfect matchingsedge weightssymmetriesnon-bipartite graphsmatching-covered graphsmin-max propertyperfect matching equalitytight cuts

0 comments

The pith

A matching-covered non-bipartite graph can place every edge in both a minimum-weight and a maximum-weight perfect matching while still having perfect matchings of unequal weights.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a hierarchy of edge-weight symmetry conditions for graphs that admit perfect matchings, ordered from strongest to weakest as node-induced weights, even walk and cycle symmetries, perfect matching equality, and the edge min-max property. It proves that these conditions are equivalent when the graph is bipartite, and it supplies tight structural characterizations using block and tight cut decompositions for the general case. The central result is an explicit counterexample: a matching-covered non-bipartite graph in which every edge belongs to some minimum-weight perfect matching and some maximum-weight perfect matching, yet the weights of all perfect matchings are not identical. This construction answers an earlier open question in the negative and demonstrates that the 2(ℓ-1) bound on the number of edges that must be fixed to exclude lower-weight matchings is tight already for ℓ=2. The same framework is sketched for b-factors and arborescences.

Core claim

The edge min-max property does not imply perfect matching equality outside the bipartite setting. There exists a matching-covered non-bipartite graph in which every edge is contained in a minimum-weight perfect matching and in a maximum-weight perfect matching, yet distinct perfect matchings receive different total weights. Structural results based on block and tight cut decompositions delineate exactly when the stronger symmetry conditions collapse to node-induced weights.

What carries the argument

The hierarchy of edge-weight properties (node-induced weights, even walk and cycle symmetries, perfect matching equality, edge min-max property) together with the block and tight cut decompositions that classify when the properties coincide.

If this is right

All four symmetry properties become equivalent on bipartite graphs.
Even cycle symmetry forces node-induced weights once the block and tight cut decompositions satisfy the paper's listed structural conditions.
Fixing a single edge is sometimes insufficient to eliminate every minimum-weight or maximum-weight perfect matching, so the 2(ℓ-1) bound is tight for ℓ=2.
The same hierarchy and decompositions extend directly to b-factors and arborescences.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The counterexample suggests that algorithmic routines for the k-th smallest perfect matching must sometimes fix two edges rather than one when the input graph is non-bipartite.
Decomposition-based recognition of these symmetry properties may yield faster preprocessing steps for exact-weight matching problems.
Similar hierarchies could be investigated for other combinatorial objects such as spanning trees or matroid bases.

Load-bearing premise

The constructed graph is matching-covered, satisfies the edge min-max property by explicit verification, and has perfect matchings of unequal weight without any additional implicit constraints that would force all weights to coincide.

What would settle it

Compute the set of all perfect matchings in the constructed counterexample graph and check whether their weights are identical or whether some edge fails to appear in both a global minimum-weight matching and a global maximum-weight matching.

read the original abstract

Motivated by the exact weight perfect matching problem and recent parameterized algorithms for finding an $\ell$-th smallest perfect matching, we study structural properties of edge-weight symmetries in graphs. Recent work by El Maalouly et al. (ESA 2025) showed that excluding all perfect matchings whose weight is at most the $(\ell - 1)$-th smallest possible value in the graph requires fixing at most $2(\ell-1)$ edges in non-bipartite graphs and at most $\ell-1$ edges in bipartite graphs. A natural open question is whether fixing a single edge is always sufficient to shift the extreme (minimum or maximum) weight of a perfect matching when the global minimum and maximum weights differ. To address this, we define and analyze a hierarchy of progressively weaker edge-weight properties: node-induced weights, even walk and cycle symmetries, perfect matching equality, and the edge min-max property. We derive a basic hierarchy among these conditions and show that they become equivalent in bipartite graphs. For general graphs, we provide tight structural characterizations, based on block and tight cut decompositions, under which even cycle symmetry and perfect matching equality force node-induced weights. Finally, we resolve the motivating open question in the negative by constructing a matching-covered non-bipartite graph that satisfies the edge min-max property (every edge is contained in a minimum-weight perfect matching and a maximum-weight one) but violates perfect matching equality (all perfect matchings have the same weight). This counterexample shows that a single edge is not always sufficient to eliminate all minimum-weight or maximum-weight perfect matchings, thereby proving the tightness of the $2(\ell-1)$ bound for $\ell=2$. We also discuss extensions of this framework to $b$-factors and arborescences.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper settles the open question in the negative with an explicit non-bipartite counterexample and organizes the symmetry notions into a usable hierarchy.

read the letter

The main things to know are that one edge fix is not always enough to eliminate all extreme-weight perfect matchings in non-bipartite graphs, and that the authors give a clean hierarchy plus structural characterizations to explain why. The counterexample is a matching-covered graph where every edge sits in both a minimum-weight and a maximum-weight perfect matching, yet the perfect matchings do not all have the same weight. This shows the 2(ℓ-1) bound from the recent ESA paper is already tight for ℓ=2. They also prove the listed properties collapse to one another in bipartite graphs and give tight-cut and block-decomposition conditions under which even-cycle symmetry or perfect-matching equality forces node-induced weights in the general case. The hierarchy and the equivalences are new, and the counterexample is the piece that directly answers the motivating question. The decompositions are standard tools, so the characterizations rest on familiar ground rather than new machinery. The work sits squarely on the prior literature without circularity or invented parameters. The soft spot is the counterexample construction. It must be verified that no unintended tight cut or odd-cycle symmetry appears that would collapse the weights after all. The abstract indicates the decompositions are used to prevent exactly that, but the concrete graph and weight assignment need to be checked line by line to confirm the separation holds. If the construction survives that check, the rest follows without issue. This is for people working on parameterized algorithms for the ℓ-th smallest perfect matching or on structural matching theory. Readers who need the tightened bound or the new language for symmetry properties will find it useful. It deserves a serious referee because it closes an open question with an explicit negative instance and supplies reusable characterizations. I would send it out for review.

Referee Report

1 major / 2 minor

Summary. The paper introduces a hierarchy of progressively weaker edge-weight properties for perfect matchings: node-induced weights, even walk and cycle symmetries, perfect matching equality, and the edge min-max property. It establishes implications between them, proves they are equivalent in bipartite graphs, and gives tight structural characterizations via block and tight cut decompositions for when even cycle symmetry and perfect matching equality imply node-induced weights in general graphs. The key contribution is a construction of a matching-covered non-bipartite graph satisfying the edge min-max property but violating perfect matching equality, negatively resolving the open question on whether fixing one edge suffices to change extreme matching weights and proving tightness of the 2(ℓ-1) bound for ℓ=2.

Significance. If the construction holds, this work is significant for showing the separation of these properties and the tightness of the bound from El Maalouly et al., with applications to finding ℓ-th smallest perfect matchings. The decomposition approach provides reusable tools for analyzing matching symmetries. The explicit nature of the counterexample is a strength, enabling direct verification.

major comments (1)

[Counterexample construction] The central claim rests on the existence of a graph G with weight function w where every edge is in some min-weight perfect matching and some max-weight perfect matching, but the weights of perfect matchings are not all equal. Please provide the concrete graph (vertices, edges) and weights, and verify these properties explicitly, ensuring no unintended tight cuts or odd cycle symmetries force equality of weights.

minor comments (2)

[Introduction] A short table or diagram summarizing the hierarchy of properties and their implications would improve clarity.
[Definitions section] The term 'node-induced weights' should be defined with a formal definition early on, perhaps as an equation.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for acknowledging the significance of our results on the hierarchy of edge-weight symmetries and the tightness of the 2(ℓ-1) bound. We address the major comment below.

read point-by-point responses

Referee: [Counterexample construction] The central claim rests on the existence of a graph G with weight function w where every edge is in some min-weight perfect matching and some max-weight perfect matching, but the weights of perfect matchings are not all equal. Please provide the concrete graph (vertices, edges) and weights, and verify these properties explicitly, ensuring no unintended tight cuts or odd cycle symmetries force equality of weights.

Authors: We appreciate the request for explicit verification. The counterexample is constructed in Section 4 as a specific matching-covered non-bipartite graph on 12 vertices with edge weights in {0,1}. To strengthen the presentation, we will add an appendix that lists all vertices and edges explicitly, tabulates the weights, enumerates the perfect matchings to confirm that their weights are not identical, and verifies that each edge belongs to at least one minimum-weight and one maximum-weight perfect matching. We will also include a short argument, based on the block and tight-cut decomposition already developed in the paper, showing that the graph admits no nontrivial tight cuts or odd-cycle symmetries that would force all perfect-matching weights to coincide. revision: yes

Circularity Check

0 steps flagged

No significant circularity; results rest on explicit construction and standard decompositions.

full rationale

The paper defines a hierarchy of edge-weight symmetry properties, derives basic implications among them, establishes equivalences in the bipartite case, and gives structural characterizations via block and tight-cut decompositions. The central negative resolution of the open question is supplied by an explicit matching-covered non-bipartite graph together with a weight function that is shown to satisfy the edge min-max property while violating perfect-matching equality. All steps are carried out by direct combinatorial argument and concrete verification on the constructed instance; no parameter is fitted and then relabeled as a prediction, no property is defined in terms of itself, and no load-bearing claim reduces to a self-citation chain. The cited decompositions are standard external tools, not internal to the present derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 4 invented entities

The central claims rest on newly introduced definitions of the four symmetry properties and on standard results from matching theory (block and tight-cut decompositions). No numerical parameters are fitted; the counterexample is an explicit combinatorial object.

axioms (1)

standard math Standard definitions and properties of graphs, perfect matchings, matching-covered graphs, and block/tight-cut decompositions.
The paper relies on established combinatorial graph theory without introducing new unproved background results.

invented entities (4)

Node-induced weights no independent evidence
purpose: Weights determined by node potentials as the strongest symmetry level
Defined as the top of the hierarchy to organize weaker conditions.
Even walk and cycle symmetries no independent evidence
purpose: Symmetry conditions along even-length structures
Intermediate level in the hierarchy.
Perfect matching equality no independent evidence
purpose: Condition that all perfect matchings have identical weight
Stronger property shown equivalent to others in bipartite graphs.
Edge min-max property no independent evidence
purpose: Every edge belongs to some min-weight and some max-weight perfect matching
Weakest property used to resolve the open question.

pith-pipeline@v0.9.0 · 5635 in / 1509 out tokens · 103385 ms · 2026-05-10T01:34:12.051691+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

14 extracted references · 1 canonical work pages · 1 internal anchor

[1]

F. Bock. An algorithm to construct a minimum directed spanning tree in a directed network.Develop- ments in Operations Research, pages 29–44, 1971

1971
[2]

Y. Du. Bipartite exact matching in P.arXiv preprint arXiv:2604.01571, 2026

work page internal anchor Pith review Pith/arXiv arXiv 2026
[3]

J. Edmonds. Maximum matching and a polyhedron with 0,1-vertices.Journal of Research of the National Bureau of Standards B, 69(125-130):55–56, 1965

1965
[4]

El Maalouly, S

N. El Maalouly, S. Haslebacher, A. Taubner, and L. Wulf. On findingℓ-th smallest perfect matchings. In33rd Annual European Symposium on Algorithms (ESA 2025), pages 19:1–19:15, 2025

2025
[5]

D. R. Fulkerson. Packing rooted directed cuts in a weighted directed graph.Mathematical Programming, 6(1):1–13, 1974

1974
[6]

E. L. Lawler. A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem.Management Science, 18(7):401–405, 1972

1972
[7]

Little and A

C. Little and A. Vince. Parity versions of 2-connectedness.The Electronic Journal of Combinatorics, 13(1):R96, 2006

2006
[8]

Lov´ asz

L. Lov´ asz. Matching structure and the matching lattice.Journal of Combinatorial Theory, Series B, 43(2):187–222, 1987

1987
[9]

Lov´ asz and M

L. Lov´ asz and M. D. Plummer.Matching Theory, volume 121 ofNorth-Holland Mathematics Studies. North-Holland Publishing Co., Amsterdam; North-Holland Publishing Co., Amsterdam, 1986. Annals of Discrete Mathematics, 29

1986
[10]

Mulmuley, U

K. Mulmuley, U. V. Vazirani, and V. V. Vazirani. Matching is as easy as matrix inversion.Combina- torica, 7(1):105–113, 1987

1987
[11]

C. H. Papadimitriou and M. Yannakakis. The complexity of restricted spanning tree problems.Journal of the ACM (JACM), 29(2):285–309, 1982

1982
[12]

H. E. Robbins. A theorem on graphs, with an application to a problem of traffic control.The American Mathematical Monthly, 46(5):281–283, 1939

1939
[13]

Schrijver.Combinatorial Optimization: Polyhedra and Efficiency, volume 24

A. Schrijver.Combinatorial Optimization: Polyhedra and Efficiency, volume 24. Springer, 2003

2003
[14]

H. Whitney. Non-separable and planar graphs.Proceedings of the National Academy of Sciences, 17(2):125–127, 1931. 14

1931