Pith. sign in

REVIEW 4 minor 17 references

Additive Latin transversals become randomized poly-time constructible once the multiset A has fixed support size, via a new color-counted matching algorithm.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.5

2026-07-14 06:03 UTC pith:TQN3CZ2E

load-bearing objection Clean base-(q+1) gadget turns Color-Counted Matching into Exact Red Matching and gives the first poly-time construction of additive Latin transversals for fixed support size.

arxiv 2607.11241 v1 pith:TQN3CZ2E submitted 2026-07-13 cs.DS math.CO

Bounded-Support Additive Latin Transversals via Color-Counted Matching

Antoine Deza , Yan Gerard , Yijun Ma , Sebastian Pokutta This is my paper
classification cs.DS math.CO MSC 05C7068Q2511B7590C27
keywords additive Latin transversalsColor-Counted MatchingExact Red Matchingbase-Q reductionsupport sizeMulmuley-Vazirani-Vaziranimatching ILPdiscrete tomography
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper attacks an open algorithmic gap left by Alon: when you are given a multiset A of k elements from the cyclic group Zm and a k-set B, order B so that the pairwise sums ai+bi are all distinct. Existence is known in many cases, but a polynomial-time construction was known only for the full or near-full regimes k=m and k=m-1. The authors show that the problem is governed by the support size s of A: there is a randomized algorithm that finds a solution (when one exists) in time (k+log m)^{O(s)}. For every fixed s the construction is therefore randomized polynomial-time. The engine is a more general primitive called Color-Counted Matching—find a matching that uses exactly ri edges of each color i. They reduce it, by a base-(q+1) path-gadget encoding, to ordinary Exact Red Matching and invoke the classical Mulmuley–Vazirani–Vazirani algorithm, obtaining a q^{O(h)} dependence that improves on the q^{O(h^{2})} bound coming from black-box matching-ILP methods. The same primitive immediately yields fixed-color algorithms for lozenge tilings, prescribed cycle covers, and diagonal-sum permutation matrices.

Core claim

There is a randomized algorithm that, given an additive-transversal instance over Zm whose multiset A has support size s, either reports failure or returns a correct ordering; if a solution exists it succeeds with probability at least 2/3 in time (k+log m)^{O(s)}. Equivalently, Color-Counted Matching with total size q and h colors is solvable in randomized time (|V|^{2}+|E|(q+1)^{h-1})^{O(1)}.

What carries the argument

The red-black Q-augmented graph (Q=q+1): each original edge of color i is replaced by an alternating path that contributes exactly Q^i red edges when selected; uniqueness of base-Q expansions then recovers the exact color-count vector from a single red-edge total, reducing Color-Counted Matching to Exact Red Matching.

Load-bearing premise

The reduction relies on every color count being strictly smaller than Q=q+1 so that the base-Q representation of the red-edge total is unique; if that digit bound failed, distinct count vectors could produce the same red total.

What would settle it

Construct a small Color-Counted Matching instance whose color counts are all less than q+1, run the base-Q gadget reduction, and check whether every perfect matching with exactly T red edges corresponds to a matching whose color vector is exactly the prescribed (r0,…,rh-1); any counter-example would break the uniqueness claim of Proposition 4.3.

Watch this falsifier — get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 4 minor

Summary. The paper studies the constructive version of additive Latin transversals over Zm: given a multiset A of size k and a k-set B, order B so that the pairwise sums ai+bi are distinct. Hall’s theorem already settles the cases k=m and k=m-1 in polynomial time; Alon proved existence for prime moduli and k<m, but no general poly-time construction was known. The authors introduce Color-Counted Matching (find a matching with prescribed numbers of edges of each of h colors) and give a direct base-(q+1) reduction to Exact Red Matching. Combined with the Mulmuley–Vazirani–Vazirani algorithm this yields a randomized algorithm running in (|V|^2+|E|(q+1)^{h-1})^{O(1)} time. Specializing to the diagonal graph of an additive-transversal instance with support size s produces a randomized (k+log m)^{O(s)}-time algorithm, hence randomized polynomial time for every fixed support size. An appendix compares the exponent favorably with the black-box matching-ILP bound of Lassota–Ligthart.

Significance. The result supplies the first nontrivial algorithmic handle on Alon’s existence theorem and, more broadly, a clean XP algorithm for a natural exact-composition matching problem that appears in discrete tomography, lozenge tilings, and prescribed-diagonal permutation matrices. The base-Q path-gadget reduction is elementary yet improves the dependence on the number of colors from quadratic to linear in the exponent relative to the general matching-ILP framework; the comparison is made explicit and correctly derived. The Monte-Carlo guarantee is inherited transparently from MVV and the success probability is stated accurately. These contributions are of clear interest to the algorithms and combinatorial-number-theory communities.

minor comments (4)
  1. In the size analysis of the Q-augmented graph (just after Definition 4.1) the bound |V'|<=2|V|+2|E|Q^{h-1} is correct, but a one-line remark that the dummy vertices contribute only when 2q<|V| would make the case distinction fully explicit for the reader.
  2. Figure 3 is helpful, yet the caption could briefly recall that the red target T equals the base-Q evaluation of the count vector; this would make the figure self-contained.
  3. The bit-complexity claim (k+log m)^{O(s)} is stated correctly in the proof of Theorem 3.2, but a short parenthetical in the abstract or Theorem 3.2 itself would clarify that the unit-cost model already gives k^{O(s)}.
  4. Reference [10] (Lassota–Ligthart) is cited for the black-box comparison; adding the precise ICALP 2025 page numbers once they are available would be useful for archival purposes.

Circularity Check

0 steps flagged

No circularity: self-contained combinatorial reduction to the external classical MVV exact-matching algorithm, with elementary base-Q uniqueness and no fitted parameters or load-bearing self-citations.

full rationale

The derivation chain is Additive Transversal o bipartite Color-Counted Matching (Lemma 4.5, by explicit diagonal-graph construction and bijection of solutions) o Exact Red Matching via red-black Q-path gadgets with Q=q+1 (Proposition 4.3, both directions proven by counting active paths and uniqueness of base-Q expansions with digits <Q) o Mulmuley–Vazirani–Vazirani (Theorem 4.4, 1987, external Monte-Carlo algorithm). All steps are constructive equivalences or direct appeals to a classical external result; the base Q is forced by the matching-size bound |M|=q rather than fitted; digit uniqueness is elementary arithmetic; dummy vertices force exactly q active paths by construction. No parameters are fitted to data and called predictions; no uniqueness theorem is imported from the present authors; references (Hall, Alon, MVV, Lassota–Ligthart) are external and non-overlapping; the improved q^{O(h)} exponent versus black-box matching-ILP is a genuine consequence of the direct encoding, not a renaming. The paper is therefore free of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 2 invented entities

The paper rests on three external pillars: the classical Mulmuley–Vazirani–Vazirani randomized exact-matching algorithm, the uniqueness of base-Q expansions with digits <Q, and the elementary matching constraints of the diagonal graph. No free parameters are fitted; the only invented objects are the Color-Counted Matching problem itself and the red-black Q-augmented graph, both of which are purely algorithmic constructions with no ontological claim.

axioms (3)
  • standard math Mulmuley–Vazirani–Vazirani: Exact Red Matching admits a randomized poly-time algorithm that succeeds with probability ≥2/3 on yes-instances (Theorem 4.4).
    Invoked as a black box in the proof of Theorem 3.4; the paper does not re-prove it.
  • standard math Uniqueness of base-Q representation: if 0≤yi,ri<Q for all i and ∑yi Qi = ∑ri Qi, then yi=ri for every i.
    Used in the converse direction of Proposition 4.3 to recover color counts from the red-edge total.
  • domain assumption A matching of size q in an n-vertex graph exists only if q≤⌊n/2⌋; dummy vertices can be added to force perfect matchings without altering the color-count semantics.
    Standard matching theory; appears in the construction of the Q-augmented graph (Section 4.1).
invented entities (2)
  • Color-Counted Matching no independent evidence
    purpose: Abstracts the exact-composition matching problem that arises from additive transversals and several other combinatorial reconstruction tasks.
    Defined in Definition 3.3; purely algorithmic, no physical or ontological claim.
  • Red-black Q-augmented graph no independent evidence
    purpose: Encodes h color-count constraints into a single Exact Red Matching instance via base-Q path gadgets.
    Constructed in Section 4.1; the gadget is a standard algorithmic device, not a new mathematical object requiring external validation.

pith-pipeline@v1.1.0-grok45 · 17277 in / 2659 out tokens · 21925 ms · 2026-07-14T06:03:11.537142+00:00 · methodology

0 comments
read the original abstract

We consider the following additive Latin transversal problem. Given a multiset $A=(a_1,\dots,a_k)$ of elements of $\mathbb Z_m$ and a set $B\subseteq\mathbb Z_m$ of cardinality $k$, the task is to order $B$ as $b_1,\dots,b_k$ so that the sums $a_i+b_i$ are pairwise distinct. When $k=m$, Hall proved that a solution exists if and only if $\sum_{i=1}^m a_i\equiv 0 \pmod m$; moreover, his theorem yields a polynomial-time construction. Alon proved that a solution always exists when $m$ is prime and $k<m$, but no polynomial-time construction is known in general. Our main algorithmic contribution is a direct randomized algorithm for Color-Counted Matching: given an edge-colored graph and prescribed target counts for the colors, find a matching using exactly the prescribed number of edges of each color. If $q$ is the sum of the target counts and $h$ is the number of colors, our base-$(q+1)$ reduction to Exact Red Matching, combined with the algorithm of Mulmuley-Vazirani-Vazirani, gives a randomized algorithm with running time $\left(|V|^2+|E|(q+1)^{h-1}\right)^{O(1)} $ for an input graph $(V,E)$. Thus the dependence on the target matching size is $q^{O(h)}$, up to polynomial factors in the graph size. In contrast, applying the general matching-ILP theorem of Lassota and Ligthart as a black box yields a $q^{O(h^2)}$ dependence for the corresponding fixed-size color-counted instances. Applying this primitive to additive Latin transversals with $s=|\operatorname{supp}(A)|$, we obtain an algorithm in randomized time $(k+\log m)^{O(s)}$. In particular, additive Latin transversals are randomized polynomial-time constructible for every fixed support size.

Figures

Figures reproduced from arXiv: 2607.11241 by Antoine Deza, Sebastian Pokutta, Yan Gerard, Yijun Ma.

Figure 1
Figure 1. Figure 1: An additive Latin transversal instance viewed as a three-direction discrete tomography instance. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Reduction of the problem of tiling a region of the triangular grid with prescribed numbers of [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Reduction of a 3-color Color-Counted Matching instance with target counts (1, 1, 1) to an Exact Red Matching instance with 21 red edges. The Color-Counted Matching instance appears on the left, and the red-black Q-augmented graph appears on the right. The target matching size is q = 1 + 1 + 1 = 3, so Q = q + 1 = 4, and the red target is T = Q0 + Q1 + Q2 = 1 + 4 + 16 = 21. Corresponding solutions are shown … view at source ↗

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

17 extracted references · 1 linked inside Pith

  1. [1]

    2022 , month = jan, note =

    David Eppstein , title =. 2022 , month = jan, note =

    2022

  2. [2]

    Theoretical Computer Science , volume =

    Del Lungo, Alberto , title =. Theoretical Computer Science , volume =. 2002 , doi =

    2002

  3. [3]

    and Gritzmann, Peter , title =

    Gardner, Richard J. and Gritzmann, Peter , title =. Transactions of the American Mathematical Society , volume =. 1997 , doi =

    1997

  4. [4]

    and Gritzmann, Peter and Prangenberg, Doris , title =

    Gardner, Richard J. and Gritzmann, Peter and Prangenberg, Doris , title =. Discrete Mathematics , volume =. 1999 , doi =

    1999

  5. [5]

    1999 , doi =

    Discrete Tomography: Foundations, Algorithms, and Applications , series =. 1999 , doi =

    1999

  6. [6]

    Proceedings of the American Mathematical Society , volume =

    Hall, Marshall , title =. Proceedings of the American Mathematical Society , volume =. 1952 , doi =

    1952

  7. [7]

    Israel Journal of Mathematics , volume =

    Noga Alon , title =. Israel Journal of Mathematics , volume =. 2000 , doi =

    2000

  8. [8]

    Transversals of additive

    Samit Dasgupta and Gyula K. Transversals of additive. Israel Journal of Mathematics , volume =. 2001 , doi =

    2001

  9. [9]

    Weidong Gao and D. J. Wang , title =. Israel Journal of Mathematics , volume =. 2004 , doi =

    2004

  10. [10]

    On determinants, matchings, and random algorithms , booktitle =

    L. On determinants, matchings, and random algorithms , booktitle =. 1979 , publisher =

    1979

  11. [11]

    DeMillo and Richard J

    Richard A. DeMillo and Richard J. Lipton , title =. Information Processing Letters , volume =. 1978 , doi =

    1978

  12. [12]

    Symbolic and Algebraic Computation , series =

    Richard Zippel , title =. Symbolic and Algebraic Computation , series =. 1979 , publisher =

    1979

  13. [13]

    Schwartz , title =

    Jacob T. Schwartz , title =. Journal of the ACM , volume =. 1980 , doi =

    1980

  14. [14]

    Vazirani and Vijay V

    Ketan Mulmuley and Umesh V. Vazirani and Vijay V. Vazirani , title =. Combinatorica , volume =. 1987 , doi =

    1987

  15. [15]

    Vazirani , title =

    Vijay V. Vazirani , title =. 2020 , eprint =

    2020

  16. [16]

    52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) , pages =

    Alexandra Lassota and Koen Ligthart , title =. 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) , pages =. 2025 , doi =

    2025

  17. [17]

    Fellows and Serge Gaspers and Frances A

    Michael R. Fellows and Serge Gaspers and Frances A. Rosamond , title =. Theory of Computing Systems , volume =. 2012 , doi =. 1007.2021 , archivePrefix =

    Pith/arXiv arXiv 2012