Pith. sign in

REVIEW 5 minor 15 references

Almost-perfect colorful matchings in three-edge-colored bipartite graphs

T0 review · 0 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read In any bipartite graph that is the union of three perfect matchings, every prescribed color-multiplicity triple summing to n-1 is realized by a matching of size n-1.

desk verdict Solid proof of the three-color multiplicity RBS case in bipartite graphs; intricate but sound, with only a harmless sign typo and a sketched multigraph extension. read the letter →

arxiv 2504.15167 v2 pith:76WDPIRV submitted 2025-04-21 math.CO

Simona Boyadzhiyska , Micha Christoph , Tibor Szabó This is my paper · ORCID
classification math.CO MSC 05C7005C1505D15
keywords colorfulmatchingsrainbowmatchingRyser–Brualdi–Steinconjectureedge-coloredbipartitegraphsperfectalternatingpathsprescribedcolormultiplicitiesthree-edge-colored
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proves that, in a bipartite graph on 2n vertices whose edges split into three disjoint perfect matchings M1, M2, M3, one can always find a matching of size n-1 that uses exactly ai edges from Mi, for any prescribed nonnegative integers a1, a2, a3 summing to n-1. This settles the three-color case of the multiplicity extension of the Ryser-Brualdi-Stein conjecture, which asks for matchings with prescribed numbers of edges from each color class of a properly edge-colored complete bipartite graph. The size n-1 is best possible: for triples summing to n the statement can fail. The proof is elementary, built from augmenting paths, and extends to bipartite multigraphs where the three perfect matchings need not be edge-disjoint.

What carries the argument

The proof rests on two structural lemmas. The Reduction Lemma (Lemma 2.1) shows that in any bipartite union of three disjoint perfect matchings on 2m vertices, if three bounds b1, b2, b3 sum to at least 2m-1, then there is a perfect matching using at most bi edges from Mi; this lets a matching in a disconnected graph be assembled component by component. The Switching Lemma (Lemma 2.2) shows that, in a connected such graph, whenever an (a1, a2, a3)-matching of size n-1 exists with a3 >= 1, one can also find matchings with one M3 edge traded for an M1 or M2 edge. The Switching Lemma is proved by tracking two unsaturated vertices along nearly-M-alternating paths that are c-good, shifting the unsaturated vertices in steps of two, and using an Intermediate Value Lemma to interpolate the number of M3-edges along the resulting sequence of matchings. Parity of the vertices' positions, supplied by bipartiteness, drives every case split.

What would settle it

Exhibit a bipartite graph on 2n vertices that is the union of three disjoint perfect matchings and, for some nonnegative a1, a2, a3 with a1 + a2 + a3 = n - 1, has no matching using exactly ai edges from Mi. For small n this can be settled by exhaustive search over all such graphs; the theorem predicts no such example exists.

Watch

Extended reading notes

Core claim

On its own terms, the central claim is Theorem 1.2: if G is a bipartite graph on 2n vertices that is the union of three disjoint perfect matchings M1, M2, M3, then for every triple of nonnegative integers a1, a2, a3 with sum n-1 there is a matching M with |M ∩ Mi| = ai for each i. The theorem is sharp, since the paper cites bipartite examples with no such matching when the prescribed counts sum to n. A direct corollary, via König's theorem, is that the multiplicity Ryser-Brualdi-Stein conjecture holds in every properly edge-colored complete bipartite graph K_{n,n} when only three color classes have nonzero prescribed multiplicities. The paper also records that the same conclusion holds for bipartite multigraphs, i.e., when the three perfect matchings are not necessarily edge-disjoint.

Load-bearing premise

The load-bearing premise is that the graph is bipartite with equal part sizes: this forces the two unmatched vertices on any near-perfect alternating path to sit at odd and even positions, and every case split in the switching argument depends on that parity.

Editorial extensions

If this is right

  • For the complete bipartite graph K_{n,n} with its edges partitioned into n perfect matchings, any three color classes with prescribed counts a_i summing to n-1 can be realized in a single matching of size n-1; this is the three-color case of the multiplicity Ryser-Brualdi-Stein conjecture.
  • The bound n-1 cannot be improved: there are bipartite unions of three perfect matchings for which no prescribed triple summing to n is realizable.
  • The result extends to bipartite multigraphs in which the three perfect matchings need not be edge-disjoint, so the disjointness assumption in the theorem is not the essential bottleneck.
  • For k >= 4 colors the analogous statement is open; the paper notes that k = 4 already seems to require genuinely new ideas.
  • If the three-color case generalizes, then replacing the constant 1 in the multiplicity conjecture by a function f(k) depending only on k is the natural next target.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the proof is parity-driven only at the level of alternating paths, a plausible test of the conjecture that drops bipartiteness outside K4 obstructions is whether the Switching Lemma can be reworked on odd cycles; the K4 counterexample suggests parity is the only obstruction.
  • The color-switching scheme resembles a discrete intermediate value argument on a grid of matchings; if it scales, the k-color version might be approached by proving a multivariate interpolation lemma rather than by new extremal arguments.
  • A computational sanity check would be to exhaustively verify all bipartite unions of three perfect matchings for small n, say n up to 6, against every triple summing to n-1; the theorem predicts no counterexample exists.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper proves Theorem 1.2: every bipartite graph on 2n vertices that is the union of three disjoint perfect matchings M1, M2, M3 contains, for every triple (a1, a2, a3) of nonnegative integers with a1 + a2 + a3 = n - 1, a matching M with exactly ai edges from Mi. The proof is elementary and self-contained. It is organized around two auxiliary results: the Reduction Lemma (Lemma 2.1, proved in Section 3), which finds a perfect matching with bounded color counts in a component of a disconnected graph, and the Switching Lemma (Lemma 2.2, proved in Section 4), which changes the color statistics of a near-perfect matching by one unit. The paper also proves a multigraph version (Theorem 5.1) and discusses possible extensions to more colors and to non-bipartite graphs.

Significance. If correct, the result resolves the three-color case of the Multiplicity Ryser-Brualdi-Stein Conjecture of Anastos, Fabian, Müyesser, and Szabó, and the bound n - 1 is best possible by the known construction from [2]. The main contribution is the Switching Lemma, a delicate combinatorial interpolation argument that is of independent interest. The proofs are fully written, self-contained, and do not rely on Montgomery's theorem or other external results; the only external input is the cited example showing optimality. The paper is likely to be of interest to researchers in matching theory and edge-colored graphs.

minor comments (5)
  1. [Section 4.2, proof of Lemma 2.2, near inequality (3)] In the discussion of the second inequality in (3) for the case c = 2, the displayed value f2(P', M^Delta(P'; h-1, h)) is stated as 1, but it should be -1, because w_{h-1}w_h is an M2 edge in a 2-good path. The absolute-value argument is unaffected, but the sign should be corrected.
  2. [Definition 4.3] The definition says that a nearly-M-alternating path P has a "unique perfect matching M_P", but a path with an even number of vertices has two perfect matchings. The notation only becomes unambiguous through Observation 4.4, where M_P is implicitly the perfect matching consisting of edges in odd positions; this should be stated explicitly.
  3. [Section 4.2, proof of Lemma 2.2, paragraph beginning "If a3(M_{i,k}) < a3"] The sentence "applying Lemma 4.10 to M = M(P; 1, h), P, and M_{i,k}" does not match the hypotheses as written, because Lemma 4.10 assumes a3 of the first matching is at most a3 of the second. The inference is valid if the two matchings are swapped in the application; the wording should be adjusted.
  4. [Abstract and Theorem 1.2] The abstract states the result for "positive integers n, a1, a2, a3", but Theorem 1.2 and the proof allow zeros in the multiplicity triple; the wording should be aligned with the theorem statement.
  5. [Definition 4.7 and Lemma 4.17] The phrase "M_c-alternating" is used before it is formally defined; since a path that is c-good allows M3 edges, while "M_c-alternating" appears to mean alternating between M_c edges and non-M_c edges, a short definition or clarification would prevent misreading of the construction in Lemma 4.17.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: self-contained alternating-path proof; citations to [2] are contextual or for sharpness only.

full rationale

The paper's derivation chain is self-contained. Theorem 1.2 is deduced from Lemma 2.1 (Reduction Lemma) and Lemma 2.2 (Switching Lemma) by induction on the number of connected components, and both lemmas are proved in Sections 3 and 4 from elementary matching, alternating-path, and parity arguments (Definitions 4.1, 4.3, 4.5, and 4.7; Observations 4.2, 4.4, 4.6, 4.8, and 4.14; Lemmas 4.9, 4.10, 4.12, 4.13, 4.16, and 4.17; and the case analysis in Section 4.2). The target color-multiplicity triple (a1,a2,a3) is never used as an input to a fitted parameter, never appears as a defining condition of the constructions, and is not assumed anywhere in the proof; matchings are constructed explicitly and then shown to have the required color counts. The citations to [2] are used for the conjecture statement, for the context of the earlier n-2-range result, and for an external counterexample ([2, Proposition 1]) showing that the sum n-1 is best possible. None of these citations is load-bearing for the existence proof: the proof does not invoke the Multiplicity Ryser-Brualdi-Stein Conjecture as an assumption, and the cited Proposition 1 only establishes optimality of the bound, not the theorem itself. Although the present paper shares one author with [2], that shared authorship does not create circularity here, because the cited results are published, independent statements and the central derivation does not reduce to them. The paper also explicitly identifies the genuinely load-bearing bipartiteness assumption in Section 5 and gives a counterexample without it, which is consistent with a self-contained proof rather than a circular one. The typo noted by a careful reader in the c=2 case of Lemma 2.2, where the displayed value of f2(P', M^Delta(P'; h-1,h)) should be -1 rather than 1, is a harmless sign error inside an absolute-value inequality and does not affect the argument or indicate circularity. Overall, no step in the derivation chain is equivalent to its own input, no fitted quantity is renamed as a prediction, and no uniqueness theorem from the authors' prior work is imported to force the conclusion.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The proof is self-contained modulo standard matching theory; no free parameters or invented entities. The theorem's bipartiteness hypothesis is the key domain assumption.

assumptions (3)
  • domain assumption The graph G is bipartite with equal part sizes and is the union of three pairwise edge-disjoint perfect matchings M1, M2, M3.
    This is the hypothesis of Theorem 1.2; the proof relies on bipartiteness for parity arguments in alternating paths (Section 4, Observation 4.2 and Lemma 4.13). Without it the statement is false, as noted in Section 5 (K4 obstruction).
  • standard math Standard matching theory facts: the union of two disjoint perfect matchings is a disjoint union of even cycles, and Koenig's theorem on decomposition of regular bipartite graphs.
    Used in the Reduction Lemma (Section 3) and in the reduction of Conjecture 1.1 to Theorem 1.2 (Section 1). These are textbook results, not original to the paper.
  • standard math The perfect matching MP of a nearly-M-alternating path P is uniquely defined (a path with an even number of vertices has a unique perfect matching).
    Foundation for the notation M(P;i,j) in Definition 4.3 and throughout Section 4.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Almost-perfect colorful matchings in three-edge-colored bipartite graphs." pith.science (2026). https://pith.science/paper/76WDPIRV

@misc{pith2026250415167,
  author       = {Pith},
  title        = {Pith review of: Almost-perfect colorful matchings in three-edge-colored bipartite graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/76WDPIRV}},
  note         = {Machine review of arXiv:2504.15167}
}
abstract

We prove that, for positive integers $n,a_1, a_2, a_3$ satisfying $a_1+a_2+a_3 = n-1$, it holds that any bipartite graph $G$ which is the union of three perfect matchings $M_1$, $M_2$, and $M_3$ on $2n$ vertices contains a matching $M$ such that $|M\cap M_i| =a_i$ for $i= 1,2,$ and $3$. The bound $n-1$ on the sum is best possible in general. Our result verifies the multiplicity extension of the Ryser-Brualdi-Stein Conjecture, proposed recently by Anastos, Fabian, M\"uyesser, and Szab\'o, for three colors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 13 canonical work pages

  1. [2]

    Anastos, D

    M. Anastos, D. Fabian, A. M¨ uyesser, and T. Szab´ o,Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets , Electron. J. Combin. 30 (2023), no. 3, Paper No. 3.10, 6

    work page 2023

  2. [1]

    Alon, private communication

    N. Alon, private communication

    work page

  3. [3]

    Arman, V

    A. Arman, V. R¨ odl, and M. T. Sales, Colorful matchings , SIAM J. Discrete Math. 37 (2023), no. 2, 925–950

    work page 2023

  4. [4]

    What did Ryser Conjecture?

    D. Best and I. M. Wanless, What did Ryser conjecture? , arXiv:1801.02893 (2018)

    work page Pith review arXiv 2018

  5. [5]

    A. E. Brouwer, A. J. de Vries, and R. M. A. Wieringa, A lower bound for the length of partial transversals in a Latin square, Nieuw Arch. Wisk. (3) 26 (1978), no. 2, 330–332

    work page 1978

  6. [6]

    R. A. Brualdi and H. J. Ryser, Combinatorial matrix theory , Cambridge University Press, 1991

    1991

  7. [7]

    D. A. Drake, Maximal sets of Latin squares and partial transversals , J. Statist. Plann. Inference 1 (1977), no. 2, 143–149

    work page 1977

  8. [8]

    Hatami and P

    P. Hatami and P. W. Shor, A lower bound for the length of a partial transversal in a Latin square , J. Combin. Theory Ser. A 115 (2008), no. 7, 1103–1113

    work page 2008

Show all 15 references
  1. [9]

    Keevash, A

    P. Keevash, A. Pokrovskiy, B. Sudakov, and L. Yepremyan, New bounds for Ryser’s conjecture and related prob- lems, Trans. Amer. Math. Soc. Ser. B 9 (2022), 288–321

    2022

  2. [10]

    K. K. Koksma, A lower bound for the order of a partial transversal in a Latin square , J. Combinatorial Theory 7 (1969), 94–95

    1969

  3. [11]

    Montgomery, A proof of the Ryser-Brualdi-Stein conjecture for large even n, arXiv:2310.19779 (2023)

    R. Montgomery, A proof of the Ryser-Brualdi-Stein conjecture for large even n, arXiv:2310.19779 (2023)

    2023 arXiv

  4. [12]

    H. J. Ryser, Neuere Probleme der Kombinatorik , Vortr¨ age ¨ uber Kombinatorik, Oberwolfach69 (1967), no. 91, 35

    1967

  5. [13]

    P. W. Shor, A lower bound for the length of a partial transversal in a Latin square , J. Combin. Theory Ser. A 33 (1982), no. 1, 1–8

    1982

  6. [14]

    S. K. Stein, Transversals of Latin squares and their generalizations , Pacific J. Math. 59 (1975), no. 2, 567–575

    1975

  7. [15]

    D. E. Woolbright, An n× n Latin square has a transversal with at least n−√n distinct symbols, J. Combinatorial Theory Ser. A 24 (1978), no. 2, 235–237. 16 S.BOYADZHIYSKA, M. CHRISTOPH, AND T. SZAB ´O (SB) HUN-REN Alfr´ed R´enyi Institute of Mathematics, Budapest, Hungary. Emai...

    1978

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.