{"id":"10a50e9a-0912-47ed-bfed-4e24e298c12a","arxiv_id":"2504.15167","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For any bipartite graph that is the union of three disjoint perfect matchings, a matching of size n-1 with exactly a1, a2, a3 edges from each exists whenever a1+a2+a3=n-1.","lead":"This paper proves that any bipartite graph made from three perfect matchings always contains a matching of size n-1 with any chosen numbers of edges from each of the three matchings, provided those numbers add up to n-1. It settles the three-color case of a 2023 multiplicity conjecture and shows the answer is optimal.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the Switching Lemma is intricate but internally coherent, and the one sign typo found does not affect the absolute-value argument.","rationale":"The reader's weakest-assumption analysis correctly identifies bipartiteness as load-bearing: the proof uses parity of unsaturated-vertex positions, reachability by alternating paths, and parity-based case splits, and the non-bipartite K4 example shows the assumption cannot simply be dropped. However, identifying an assumption as load-bearing is not the same as identifying a flaw. My review focused on the proof of the Switching Lemma, especially Lemma 4.10 and the final interpolation in Lemma 2.2, since that is where a hidden sign or agreement error would most likely break the argument. I traced the construction of P' and M* and the derivation of inequality (3); the sign typo in the c=2 display is real but immaterial because the proof uses absolute values. The Reduction Lemma's base case and the induction step of Theorem 1.2 are sound. The multigraph extension Theorem 5.1 is only sketched, but it is not the central claim and the paper flags it. Overall, the central theorem appears correct, so the reader's ACCEPT verdict should stand. The only residual risk is the sheer complexity of the proof and the absence of machine-checked verification, hence my concrete test proposes an independent computational check for small n rather than a targeted re-derivation of a specific flawed equation.","tokens_in":21581,"tokens_out":49590,"duration_ms":402255,"concrete_test":"Run an independent brute-force verification of Theorem 1.2 for all bipartite graphs on 8 and 10 vertices that decompose into three disjoint perfect matchings, checking every triple (a1,a2,a3) with sum n-1. This directly tests the central claim for n=4,5; any counterexample would disprove the theorem, and a clean pass would increase confidence that no hidden structural flaw in the Switching Lemma exists.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After working through the Reduction Lemma, the Switching Lemma, and the induction in the proof of Theorem 1.2, I did not find a concrete gap that would threaten the central claim. The most delicate part is the final application of the Intermediate Value Lemma in the proof of Lemma 2.2: the construction of M*, P', M^Δ, and the inequality (3) in Section 4.2 rely on several sign and agreement claims that are easy to misread, and the reader correctly noted that in the c=2 case the displayed value f2(P', M^Δ(P'; h-1, h)) should be -1 rather than 1. This typo is harmless because the surrounding inequality is in absolute values, but it shows how fragile the case analysis is. I verified the main structural steps: Observation 4.2 follows from the matching-saturation property of nearly-M-alternating paths; Lemma 4.9 preserves a2 and changes a3 by at most one; Lemma 4.10 constructs the required interpolation; and Lemma 4.16 obtains the path P0 with the stated properties. The bipartiteness assumption is genuinely load-bearing, as the paper's Section 5 counterexample with disjoint K4 components demonstrates, but it is used legitimately through parity arguments and Lemma 4.13. No unsupported assertion in the central proof was identified.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":21718,"tokens_out":37195,"duration_ms":310669,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Section 4.2, proof of Lemma 2.2, near inequality (3)"},{"comment":"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.","section":"Definition 4.3"},{"comment":"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.","section":"Section 4.2, proof of Lemma 2.2, paragraph beginning \"If a3(M_{i,k}) < a3\""},{"comment":"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.","section":"Abstract and Theorem 1.2"},{"comment":"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.","section":"Definition 4.7 and Lemma 4.17"}],"recommendation":"minor_revision","confidential_remarks":"I read the theorem and both main lemmas in detail, including the delicate final part of the Switching Lemma after inequality (3), and I did not find a gap in the central argument. The manuscript is technically demanding but appropriate for the journal. The sign typo and the notational ambiguities listed in the minor comments should be corrected before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe headline: this paper settles the three-color case of the Multiplicity Ryser–Brualdi–Stein Conjecture for bipartite graphs, reaching the optimal sum n−1 where prior work only reached n−2. That is a genuine theorem, not an incremental observation.\n\nWhat is new is the machinery: the Reduction Lemma for disconnected components, the Switching Lemma that trades a color-3 edge for color-1 or color-2 while holding matching size, and the Intermediate Value Lemma that lets them interpolate a3 along a sequence of matchings. The proof is elementary in the sense of using only alternating paths, but it is delicate. I traced the main steps—Reduction Lemma base case, Lemma 4.9, Lemma 4.10, and the path lemmas 4.16–4.17—and did not find a gap that threatens Theorem 1.2. The reader's and stress-test's assessment matches mine: the one displayed sign error in the c=2 branch (f2 = −1 rather than 1) is genuinely harmless because the argument uses absolute values.\n\nSoft spots, in proportion: the bipartiteness assumption is load-bearing, and the authors say so. Without it, their own Section 5 example (disjoint K4 copies) shows the statement fails. That is not a flaw; it is an honest boundary. Theorem 5.1, extending to multigraphs where the matchings may overlap, is only sketched. Since the main theorem is the three-color simple-graph case, this is a caveat rather than a defect, but a serious referee should ask for either a full proof or a clearer statement of which modifications are needed. The citation pattern is fine: the close relation to [2] is natural, and the authors do not hide the dependency.\n\nWho benefits: anyone working on rainbow matchings, Ryser–Brualdi–Stein, or edge-colored matching problems. This paper deserves a serious referee: the result is important, the proof is self-contained, and the complexity is high enough to justify careful referee time. I would expect a minor-revision accept.","headline":"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.","tokens_in":22377,"tokens_out":2464,"would_cite":true,"duration_ms":21478,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C70","05C15","05D15"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["colorful matchings","rainbow matching","Ryser–Brualdi–Stein conjecture","edge-colored bipartite graphs","perfect matchings","alternating paths","prescribed color multiplicities","three-edge-colored graphs"],"falsifier":"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.","tokens_in":21286,"feed_emoji":"🎨","tokens_out":6469,"duration_ms":54465,"temperature":0.7,"pith_summary":"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.","feed_headline":"Every prescribed color mix is realized in unions of three perfect matchings","feed_subtitle":"Extends the rainbow-matching conjecture to prescribed color counts, with n-1 edges shown best possible.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Proposes the multiplicity Ryser-Brualdi-Stein conjecture, proves the three-color case for sums up to n-2, and supplies the extremal example showing the n-1 bound is best possible.","marker":"[2]"},{"why":"Announces the proof of the Ryser-Brualdi-Stein conjecture for large n, the rainbow case that the multiplicity conjecture generalizes.","marker":"[11]"},{"why":"Earlier work on colorful matchings that motivated the study of prescribed color multiplicities beyond rainbow matchings.","marker":"[3]"},{"why":"Ryser's original conjecture on rainbow matchings in Latin squares, the historical root of the problem.","marker":"[12]"}],"fun_headline_variants":["Sharp bound for prescribed color counts in 3-color bipartite matchings","Triple matchings yield every prescribed color split, up to n-1 edges","All color mixes achieved in unions of three perfect matchings","Prescribed intersections in 3-color unions: sharp n-1 theorem","Every prescribed color count is realizable up to n-1 in 3-matchings"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Sharp bound for prescribed color counts in 3-color bipartite matchings","Triple matchings yield every prescribed color split, up to n-1 edges","All color mixes achieved in unions of three perfect matchings","Prescribed intersections in 3-color unions: sharp n-1 theorem","Every prescribed color count is realizable up to n-1 in 3-matchings"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000463,"raw_usage":{"total_tokens":2277,"prompt_tokens":869,"completion_tokens":1408,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":485,"completion_tokens_details":{"reasoning_tokens":1310}},"tokens_in":485,"tokens_out":1408,"duration_ms":9595,"temperature":1.0,"reasoning_tokens":1310,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:35:46.333240+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Anastos, D","cited_arxiv_id":null,"evidence_quote":"Proposes the multiplicity Ryser-Brualdi-Stein conjecture, proves the three-color case for sums up to n-2, and supplies the extremal example showing the n-1 bound is best possible."},{"cited_title":"Arman, V","cited_arxiv_id":null,"evidence_quote":"Earlier work on colorful matchings that motivated the study of prescribed color multiplicities beyond rainbow matchings."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Ryser's original conjecture on rainbow matchings in Latin squares, the historical root of the problem."}],"review_version":1}