pith. sign in

arxiv: 2604.09449 · v1 · submitted 2026-04-10 · 🧮 math.CO

Colour-balanced subgraphs

Emma Hogan , Alex Scott , Dmitry Tsarev This is my paper

Pith reviewed 2026-05-10 17:26 UTC · model grok-4.3

classification 🧮 math.CO
keywords colour-balanced graphsedge-coloured graphsperfect matchingsrecolouringcomplete graphsspanning subgraphshypergraph matchingsnecklace splitting
0
0 comments X

The pith

Any colour-balanced k-edge-coloured complete graph on 2kt vertices contains a perfect matching that becomes colour-balanced after recolouring only O(k^2) edges.

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

The paper establishes that when a complete graph has its edges painted with k colours in exact balance, one can always locate a perfect matching whose own colour counts sit close enough to equal that only a quadratic number of edge recolourings are needed to reach exact balance. A sympathetic reader would care because the result guarantees that dense, fair colourings always admit nearly fair spanning substructures without large-scale fixes, improving earlier estimates for many families of subgraphs. The same style of bound holds for any bounded-degree spanning subgraph and for perfect matchings inside edge-coloured uniform hypergraphs under a vector labelling. The argument works by reducing each case to an auxiliary problem on bipartite graphs.

Core claim

Resolving a conjecture of Pardey and Rautenbach, we show that any colour-balanced k-edge-coloured complete graph K_{2kt} contains a perfect matching that can be made colour-balanced by recolouring O(k^2) edges. More generally, we obtain analogous bounds for arbitrary bounded-degree spanning subgraphs of edge-coloured complete graphs and for perfect matchings in edge-coloured r-uniform complete hypergraphs in a more general vector-label setting. The former result answers a question recently posed by Banerjee and Hollom, and significantly improves earlier bounds for all previously studied classes of subgraph. Our proofs reduce each of these problems to a setting in which we can apply a bound.

What carries the argument

The reduction of each problem to the task of finding a perfect matching in an auxiliary edge-coloured complete bipartite graph, where a linear relaxation combined with a necklace-splitting argument controls the number of recolourings needed.

If this is right

  • Any bounded-degree spanning subgraph of a colour-balanced edge-coloured complete graph admits a copy that becomes colour-balanced after O(k^2) recolourings.
  • In r-uniform complete hypergraphs with vector labels, perfect matchings can be made balanced with a number of label changes bounded by a function of k and r.
  • The same reduction technique yields improved recolouring bounds for all previously studied classes of balanced subgraphs.
  • The necklace-splitting step supplies an explicit way to bound the discrepancy between the matching and the global colour counts.

Where Pith is reading between the lines

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

  • If the bipartite reduction can be made algorithmic, the same technique would give a polynomial-time method to produce the near-balanced matching.
  • The vector-label extension may connect the problem to multi-objective fair division tasks where several resources must be balanced simultaneously.
  • Similar reductions could apply to other spanning structures such as Hamilton cycles or decompositions once their bipartite relaxations are understood.

Load-bearing premise

The reduction from the original coloured graph to the bipartite perfect-matching instance via linear relaxation and necklace-splitting preserves the O(k^2) recolouring bound without extra losses or further restrictions on the colouring.

What would settle it

A single colour-balanced k-edge-colouring of K_{2kt} in which every perfect matching requires more than a quadratic number of recolourings to reach exact colour balance would falsify the claim.

Figures

Figures reproduced from arXiv: 2604.09449 by Alex Scott, Dmitry Tsarev, Emma Hogan.

Figure 1
Figure 1. Figure 1: Adjacency matrix representations of the constructions used in [PITH_FULL_IMAGE:figures/full_fig_p024_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Counterexamples for k = 3 with t = 1 (left) and t = 2 (right). When k = 3 and t = 1 the construction gives a graph isomorphic to the counterexample of Pardey and Rautenbach [19]. V1 V2 V4 V3 V1 V2 V4 V3 [PITH_FULL_IMAGE:figures/full_fig_p026_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Counterexamples for k = 4 with t = 1 (left) and t = 2 (right). 6 Open Problems There are several interesting directions for further research. There is a gap between the O(k 2 ) bound obtained for representative matchings in bipartite graphs in Theorem 1.9, and the worst-case lower bound of p k/2 constructed in Theorem 5.1. Our use of Theorem 1.9 to prove each of our other results for representative subgrap… view at source ↗
read the original abstract

A $k$-edge-coloured graph is colour-balanced if each colour appears equally often. Resolving a conjecture of Pardey and Rautenbach, we show that any colour-balanced $k$-edge-coloured complete graph $K_{2kt}$ contains a perfect matching that can be made colour-balanced by recolouring $O(k^2)$ edges. More generally, we obtain analogous bounds for arbitrary bounded-degree spanning subgraphs of edge-coloured complete graphs and for perfect matchings in edge-coloured $r$-uniform complete hypergraphs in a more general vector-label setting. The former result answers a question recently posed by Banerjee and Hollom, and significantly improves earlier bounds for all previously studied classes of subgraph. Our proofs reduce each of these problems to a setting in which we can apply a bound for perfect matchings in the complete bipartite graph, established via a linear relaxation and a necklace-splitting argument.

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.

Referee Report

2 major / 2 minor

Summary. The manuscript resolves a conjecture of Pardey and Rautenbach by proving that any colour-balanced k-edge-coloured complete graph K_{2kt} contains a perfect matching that becomes colour-balanced after recolouring O(k^2) edges. It further establishes analogous O(k^2) bounds for perfect matchings in arbitrary bounded-degree spanning subgraphs of edge-coloured complete graphs and for perfect matchings in edge-coloured r-uniform complete hypergraphs under a vector-label generalization. All results are obtained by reducing to a bound on perfect matchings in the complete bipartite graph, derived via linear relaxation followed by a necklace-splitting argument.

Significance. If the claimed O(k^2) bound is verified, the result is significant: it improves all previously known bounds for these problems (which typically depended on the number of vertices or had worse dependence on k) and answers a recent question of Banerjee and Hollom. The reduction technique via linear programming relaxation plus necklace splitting is a clean combinatorial tool that may extend to other recolouring or balancing problems in edge-coloured graphs. The independence of the bound from the graph order is particularly useful for large instances.

major comments (2)
  1. [§3] §3 (necklace-splitting for bipartite matchings): the argument asserts that the integral solution differs from the fractional matching in O(k^2) edges total. With vector labels of dimension k and up to Θ(kt) fractional variables, it is unclear whether the number of cuts or the support difference remains O(k^2) rather than acquiring an extra factor linear in t or logarithmic in kt. An explicit calculation bounding the total variation (not merely per colour class) is needed to confirm the claimed bound survives.
  2. [§5] §5 (lifting the bipartite bound to K_{2kt} and bounded-degree subgraphs): the linear-relaxation reduction from the original coloured graph to the bipartite instance must transfer the O(k^2) recolouring count without hidden multiplicative losses depending on maximum degree or t. The manuscript should include a precise lemma quantifying the additional recolourings introduced when mapping solutions back.
minor comments (2)
  1. [Abstract] The abstract and introduction use 'O(k^2)' without indicating whether the hidden constant is explicit or depends on r in the hypergraph case; a short remark on the dependence would aid readability.
  2. [Hypergraph section] Notation for vector labels in the hypergraph section should be cross-referenced to the earlier graph sections to avoid ambiguity in the dimension-k setting.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading, positive assessment of the significance of our results, and constructive suggestions for improving the exposition. The two major comments correctly identify places where additional explicit calculations and a transfer lemma would strengthen the paper. We have revised the manuscript to address both points fully by adding the requested details in §§3 and 5. We respond to each comment below.

read point-by-point responses

  1. Referee: [§3] §3 (necklace-splitting for bipartite matchings): the argument asserts that the integral solution differs from the fractional matching in O(k^2) edges total. With vector labels of dimension k and up to Θ(kt) fractional variables, it is unclear whether the number of cuts or the support difference remains O(k^2) rather than acquiring an extra factor linear in t or logarithmic in kt. An explicit calculation bounding the total variation (not merely per colour class) is needed to confirm the claimed bound survives.

    Authors: We thank the referee for highlighting the need for an explicit total-variation bound. In the revised §3 we have inserted a new paragraph containing the full calculation. The LP relaxation produces a fractional matching x with ||x||_1 = kt and each colour class summing to exactly t. We encode the support of x as a necklace whose beads are the fractional edges, each carrying a k-dimensional vector label (one coordinate per colour). The multidimensional necklace-splitting theorem then yields a partition into k integral matchings with at most k(k-1) cuts in total. Selecting the part whose vector sum is closest to the target (t,…,t) produces an integral matching y whose L1 distance to x is supported only on the O(k) cut edges. Because each cut edge has fractional value at most 1 and there are k colours, the total number of edges where x_e ≠ y_e is at most 2k^2. This bound is independent of t and of the number of fractional variables; the extra logarithmic or linear factors the referee feared do not appear. We have also added a short appendix verifying the vector-label version of the necklace theorem used here. revision: yes

  2. Referee: [§5] §5 (lifting the bipartite bound to K_{2kt} and bounded-degree subgraphs): the linear-relaxation reduction from the original coloured graph to the bipartite instance must transfer the O(k^2) recolouring count without hidden multiplicative losses depending on maximum degree or t. The manuscript should include a precise lemma quantifying the additional recolourings introduced when mapping solutions back.

    Authors: We agree that a precise transfer statement is required. In the revised §5 we have added Lemma 5.1, which states: if the bipartite auxiliary graph admits a perfect matching differing from its fractional solution in at most C recolourings, then the corresponding recolouring set in the original (bounded-degree) spanning subgraph differs from the target colour-balanced matching by at most C + 2k^2 edges. The proof proceeds by lifting each bipartite discrepancy back through the original edges; because the reduction identifies each bipartite vertex with a colour class of size t and uses only O(k) auxiliary complete-graph edges per colour class to resolve imbalances, the extra recolourings remain additive O(k^2) and carry no multiplicative factor in Δ or t. The lemma is proved in full and immediately implies that the O(k^2) bound for the original problems follows from the bipartite case without degradation. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation reduces general cases to independently proved bipartite bound

full rationale

The paper's proofs explicitly reduce the colour-balanced subgraph problems (including the main K_{2kt} perfect matching result) to a bound on perfect matchings in edge-coloured complete bipartite graphs, which is then established separately via linear relaxation followed by a necklace-splitting argument. No equations or steps are self-definitional, no parameters are fitted to data and then relabelled as predictions, and no load-bearing claims rest on self-citations or prior uniqueness theorems by the same authors. The O(k^2) recolouring bound is derived from the reduction plus the bipartite analysis rather than being presupposed by construction. This structure is self-contained against external benchmarks and does not reduce any claimed result to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the colour-balance hypothesis and the validity of the reduction technique; no free parameters or invented entities appear in the abstract.

axioms (2)
  • domain assumption The input graph is complete and the edge colouring is colour-balanced (each colour appears equally often).
    This is the explicit hypothesis of the main theorem stated in the abstract.
  • standard math Standard results on perfect matchings in complete bipartite graphs and the necklace-splitting theorem apply after the linear relaxation step.
    Invoked in the described proof reduction.

pith-pipeline@v0.9.0 · 5438 in / 1406 out tokens · 89016 ms · 2026-05-10T17:26:19.590037+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    Cutting the Same Fraction of Several Measures

    A. Akopyan and R. Karasev. “Cutting the Same Fraction of Several Measures”. In:Discrete & Computational Geometry49.2 (Aug. 2012), pp. 402–410.issn: 1432-0444.doi:10.1007/ s00454-012-9450-4

    work page 2012

  2. [2]

    Splitting necklaces

    N. Alon. “Splitting necklaces”. In:Advances in Mathematics63.3 (1987), pp. 247–253.doi: 10.1016/0001-8708(87)90055-7

    work page doi:10.1016/0001-8708(87)90055-7 1987

  3. [3]

    Uniformly balancedH-factors in multicoloured complete graphs

    A. Banerjee and L. Hollom. “Uniformly balancedH-factors in multicoloured complete graphs”. In:arXiv preprint arXiv:2601.18789(2026). 27

    work page arXiv 2026

  4. [4]

    On the Erdős-Ginzburg-Ziv theorem and the Ramsey numbers for stars and matchings

    A. Bialostocki and P. Dierker. “On the Erdős-Ginzburg-Ziv theorem and the Ramsey numbers for stars and matchings”. In:Discrete Mathematics110.1 (1992), pp. 1–8.doi:10.1016/0012- 365X(92)90695-C

    work page doi:10.1016/0012- 1992

  5. [5]

    Discrete Mathematics , volume =

    Y. Caro. “Zero-sum problems—a survey”. In:Discrete Mathematics152.1-3 (1996), pp. 93– 113.doi:10.1016/0012-365X(94)00308-6

    work page doi:10.1016/0012-365x(94)00308-6 1996

  6. [6]

    On Zero-Sum Spanning Trees and Zero-Sum Connectivity

    Y. Caro, A. Hansberg, J. Lauri, and C. Zarb. “On Zero-Sum Spanning Trees and Zero-Sum Connectivity”. In:The Electronic Journal of Combinatorics(2022), P1–9.doi:10.37236/ 10289

    work page 2022

  7. [7]

    Almost-full transversals in equi-n-squares

    D. Chakraborti, M. Christoph, Z. Hunter, R. Montgomery, and T. Petrov. “Almost-full transversals in equi-n-squares”. In:arXiv preprint arXiv:2412.07733(2024)

    work page arXiv 2024

  8. [8]

    Concentration inequalities with exchangeable pairs

    S. Chatterjee. “Concentration inequalities with exchangeable pairs”. PhD thesis. Stanford University, 2005

    work page 2005

  9. [9]

    Submodular functions, matroids, and certain polyhedra

    J. Edmonds. “Submodular functions, matroids, and certain polyhedra”. In:Proc. Calgary Int. Conference on Combinatorial Structures and Their Applications, 1970. Gordon and Breach. 1970.doi:10.1007/3-540-36478-1_2

    work page doi:10.1007/3-540-36478-1_2 1970

  10. [10]

    Low Weight Perfect Matchings

    S. Ehard, E. Mohr, and D. Rautenbach. “Low Weight Perfect Matchings”. In:The Electronic Journal of Combinatorics27.4 (Dec. 2020).issn: 1077-8926.doi:10.37236/9994

    work page doi:10.37236/9994 2020

  11. [11]

    On zero-trees

    Z. Füredi and D. J. Kleitman. “On zero-trees”. In:Journal of Graph Theory16.2 (1992), pp. 107–120.doi:10.1002/jgt.3190160202

    work page doi:10.1002/jgt.3190160202 1992

  12. [12]

    A Uniform Bound on Almost Colour-Balanced Perfect Matchings in Colour- Balanced Complete Graphs

    L. Hollom. “A Uniform Bound on Almost Colour-Balanced Perfect Matchings in Colour- Balanced Complete Graphs”. In:The Electronic Journal of Combinatorics(2025), P4–50. doi:10.37236/13491

    work page doi:10.37236/13491 2025

  13. [13]

    Almost colour-balanced spanning forests in complete graphs

    L. Hollom, A. Mond, and J. Portier. “Almost colour-balanced spanning forests in complete graphs”. In:arXiv preprint arXiv:2410.06148(2024)

    work page arXiv 2024

  14. [14]

    On the existence of zero-sum perfect matchings of complete graphs

    T. Kittipassorn and P. Sinsap. “On the existence of zero-sum perfect matchings of complete graphs”. In:Ars Math. Contemp.23.3 (Jan. 2023), P3.07.doi:10.26493/1855-3974.2573. 90d

    work page doi:10.26493/1855-3974.2573 2023

  15. [15]

    J., 2022, in Bambi C., Santangelo A., eds, , Handbook of X-ray and Gamma-ray Astrophysics

    J. Matoušek.Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combina- torics and Geometry.Universitext. Written incooperationwith Anders BjörnerandGünterM. Ziegler. Berlin, Heidelberg: Springer, Apr. 2003.isbn: 978-3-540-00362-5.doi:10.1007/978- 3-540-76649-0

    work page doi:10.1007/978- 2003

  16. [16]

    Zero-sum copies of spanning forests in zero-sum complete graphs

    E. Mohr, J. Pardey, and D. Rautenbach. “Zero-sum copies of spanning forests in zero-sum complete graphs”. In:Graphs and Combinatorics38.5 (2022), p. 132.doi:10.1007/s00373- 022-02539-2

    work page doi:10.1007/s00373- 2022

  17. [17]

    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 evenn”. In:arXiv preprint arXiv:2310.19779(2023)

    work page arXiv 2023

  18. [18]

    Oxley.Matroid Theory

    J. Oxley.Matroid Theory. 2nd ed. Vol. 21. Oxford University Press, 2011

    work page 2011

  19. [19]

    Matching signatures and pfaffian graphs.Discrete Mathematics, 311(4):289–294, 2011.doi:10.1016/j.disc

    J. Pardey and D. Rautenbach. “Almost color-balanced perfect matchings in color-balanced complete graphs”. In:Discrete Mathematics345.2 (2022), p. 112701.doi:10.1016/j.disc. 2021.112701

    work page doi:10.1016/j.disc 2022

  20. [20]

    Efficiently finding low-sum copies of spanning forests in zero- sum complete graphs via conditional expectation

    J. Pardey and D. Rautenbach. “Efficiently finding low-sum copies of spanning forests in zero- sum complete graphs via conditional expectation”. In:Discrete Applied Mathematics328 (2023), pp. 108–116.doi:10.1016/j.dam.2022.12.014

    work page doi:10.1016/j.dam.2022.12.014 2023

  21. [21]

    Sets on which several measures agree

    W. Stromquist and D. R. Woodall. “Sets on which several measures agree”. In:Journal of Mathematical Analysis and Applications108.1 (1985), pp. 241–248.doi:10 . 1016 / 0022 - 247X(85)90021-6. 28

    work page 1985