pith. sign in

arxiv: 2511.16021 · v2 · submitted 2025-11-20 · 🧮 math.CO

Generalizing the Multiple Exchange Property for Matroid Bases

Taihei Oki , Tam\'as Schwarcz This is my paper

Pith reviewed 2026-05-17 21:18 UTC · model grok-4.3

classification 🧮 math.CO MSC 05B35
keywords matroid basesbasis exchange propertymultiple exchangeGrassmann-Plücker identityrepresentable matroidsequitability theorem
0
0 comments X

The pith

In any matroid, for bases A and B and any subsets X of A outside B and Y of B outside A, one can always find larger exchange sets U containing X and V containing Y such that both A minus U plus V and B plus U minus V remain bases and the交換d

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

The paper proves a common generalization of the classical multiple exchange property and other known basis exchange results for matroids. For any two bases A and B together with prescribed subsets X inside A but not B and Y inside B but not A, there exist supersets U of X and V of Y inside the respective symmetric differences so that A minus U plus V and B plus U minus V are both bases while the common size of U and V is at most the rank of the union X union Y. A second direction develops a systematic way to obtain further exchange properties for matroids that are representable over a field of characteristic zero by extending the Grassmann-Plücker identity; this recovers the first result plus the recent Equitability Theorem as special cases. A reader who works with combinatorial algorithms or optimization would care because these exchange rules are basic building blocks for proving correctness and designing procedures that move between bases.

Core claim

The central claim is that every matroid satisfies the following exchange property: given bases A and B and arbitrary X ⊆ A∖B, Y ⊆ B∖A, there exist U ⊇ X inside A∖B and V ⊇ Y inside B∖A such that A−U+V and B+U−V are bases and |U|=|V| ≤ rank(X+Y). For matroids representable over characteristic zero the authors supply an algebraic framework that produces additional exchange statements by manipulating suitable Grassmann-Plücker identities; one such statement simultaneously generalizes the rank-bounded property above and the Equitability Theorem.

What carries the argument

The rank-bounded common generalization of basis exchange properties, realized by enlarging prescribed subsets X and Y to exchangeable U and V whose size is controlled by the rank of X+Y.

If this is right

  • The new property immediately strengthens any algorithmic argument that previously invoked the classical multiple exchange property.
  • Several previously separate exchange lemmas become special cases of a single statement controlled by the rank function.
  • The Grassmann-Plücker framework yields further exchange rules that apply exactly to linear matroids over characteristic zero.
  • The Equitability Theorem is recovered as one instance inside the same algebraic derivation chain.

Where Pith is reading between the lines

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

  • The rank bound suggests that exchange steps can be chosen to be as small as the linear dependence structure permits, which may simplify analysis of greedy or augmentation algorithms.
  • Because the size is controlled by rank rather than cardinality alone, the result may extend naturally to weighted or parametric versions of basis exchange.
  • The algebraic framework could be used to derive analogous identities for other matroid classes that admit some form of linear representation or valuation.

Load-bearing premise

The structure obeys the usual matroid independence axioms, and for the algebraic extensions the matroid must be representable over a field of characteristic zero.

What would settle it

A concrete matroid together with bases A, B and subsets X, Y for which every candidate pair U ⊇ X, V ⊇ Y that makes both modified sets bases has |U| strictly larger than rank(X+Y).

Figures

Figures reproduced from arXiv: 2511.16021 by Taihei Oki, Tam\'as Schwarcz.

Figure 1
Figure 1. Figure 1: Relation of exchange properties Theorem 1.5 specializes to Theorem 1.1 if Y = ∅. Our proof idea of Theorem 1.5 extends Woodall’s proof [53] of the multiple exchange property, which is based on Edmonds’ matroid inter￾section theorem [9]. We formulate the problem of finding the sets U and V as weighted matroid intersection, and bound the optimal value via Frank’s weight splitting theorem [12]. As our proof i… view at source ↗
read the original abstract

The multiple exchange property for matroid bases states that for any bases $A$ and $B$ of a matroid and any subset $X\subseteq A\setminus B$, there exists a subset $Y\subseteq B\setminus A$ such that both $A-X+Y$ and $B+X-Y$ are bases. This classical result has found applications not only in matroid theory, but also in the analysis and design of various algorithms. This paper generalizes the multiple exchange property in two directions. First, we prove a common generalization of this and other known basis exchange properties by showing that for any subsets $X \subseteq A \setminus B$ and $Y \subseteq B \setminus A$, there exist subsets $U \subseteq A \setminus B$ and $V \subseteq B \setminus A$ such that $X\subseteq U$, $Y\subseteq V$, $A-U+V$ and $B+U-V$ are bases, and $|U|=|V|$ is at most the rank of $X+Y$. Second, we develop a general framework for deriving extensions of the Grassmann-Pl\"ucker identity, showing further exchange properties for matroids representable over a field of characteristic zero. Using our framework, we prove an exchange property for this matroid class that simultaneously generalizes our first result and the very recent Equitability Theorem (SODA 2026).

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

0 major / 3 minor

Summary. The paper generalizes the classical multiple exchange property for matroid bases. It first proves that given bases A and B of a matroid, and arbitrary subsets X ⊆ A ∖ B and Y ⊆ B ∖ A, there exist subsets U ⊆ A ∖ B and V ⊆ B ∖ A with X ⊆ U, Y ⊆ V, |U| = |V| ≤ r(X ∪ Y), such that A − U + V and B + U − V are also bases. Second, it introduces a framework for deriving extensions of the Grassmann-Plücker identity, which is used to prove a stronger exchange property for matroids representable over a field of characteristic zero; this property generalizes both the first result and the recent Equitability Theorem.

Significance. This generalization unifies several known basis exchange properties under a single statement with an explicit rank bound on the size of the exchanged sets. The bound |U| = |V| ≤ r(X ∪ Y) is a natural and potentially tight strengthening derived from submodularity. The development of a general framework for Grassmann-Plücker extensions in the representable case over characteristic zero is a valuable contribution that may facilitate further results in algebraic combinatorics. The proofs rely on iterated applications of the standard basis exchange axiom and submodularity of the rank function, which are standard tools in the field.

minor comments (3)
  1. The notation 'X+Y' in the abstract and theorem statements should be explicitly defined as the union X ∪ Y (or clarified via context) to prevent potential confusion with other algebraic operations.
  2. In the introduction, a brief remark on how the new rank-bounded exchange property might improve existing algorithms (e.g., in matroid intersection or optimization) would strengthen the motivation.
  3. The citation to the Equitability Theorem should include complete bibliographic details for the SODA 2026 paper.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending minor revision. The provided summary accurately reflects the two main contributions: the generalized multiple exchange property with the explicit rank bound |U|=|V| ≤ r(X ∪ Y), and the framework for Grassmann-Plücker extensions yielding stronger results for characteristic-zero representable matroids.

Circularity Check

0 steps flagged

No significant circularity; derivation relies on standard matroid axioms

full rationale

The paper proves the generalized multiple exchange property by iterated application of the classical basis exchange axiom together with submodularity of the rank function on X ∪ Y, directly constructing U and V while bounding |U|=|V| ≤ r(X ∪ Y). The second direction invokes the Grassmann-Plücker identity only for representable matroids over characteristic zero, an external algebraic fact. No step reduces a claimed prediction to a fitted parameter by construction, nor does any load-bearing premise rest solely on a self-citation whose content is itself unverified within the paper. Classical matroid results are cited as background, not as the source of the new generalization.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests entirely on the standard axioms of matroid theory from prior literature; no free parameters are introduced or fitted, and no new entities are postulated.

axioms (1)
  • standard math A matroid is defined by its independent sets satisfying the hereditary property and the augmentation axiom, or equivalently by its bases satisfying the basis exchange axiom.
    This is the ambient structure in which bases A and B and the exchange properties are defined throughout the abstract.

pith-pipeline@v0.9.0 · 5542 in / 1454 out tokens · 41709 ms · 2026-05-17T21:18:52.744393+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

54 extracted references · 54 canonical work pages

  1. [1]

    Akrami, R

    H. Akrami, R. Raj, and L. A. Végh. Matroids are equitable, 2025. arXiv:2507.12100. To appear in Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

    work page arXiv 2025

  2. [2]

    InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 1653–1664, New York, NY, USA

    K.Bérczi,B.Mátravölgyi,andT.Schwarcz.Reconfigurationofbasispairsinregularmatroids. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 1653–1664, New York, NY, USA. Association for Computing Machinery, 2024.doi: 10.1145/3618260.3649660

    work page doi:10.1145/3618260.3649660 2024

  3. [3]

    R. A. Brualdi. Comments on bases in dependence structures.Bulletin of the Australian Math- ematical Society, 1(2):161–167, 1969.doi:10.1017/s000497270004140x

    work page doi:10.1017/s000497270004140x 1969

  4. [4]

    T. H. Brylawski. Some properties of basic families of subsets.Discrete Mathematics, 6(4):333– 341, 1973.doi:10.1016/0012-365x(73)90064-2

    work page doi:10.1016/0012-365x(73)90064-2 1973

  5. [5]

    Buchbinder, M

    N. Buchbinder, M. Feldman, and M. Garg. Deterministic(1/2 +ε)-approximation for sub- modular maximization over a matroid.SIAM Journal on Computing, 52(4), 2023.doi:10. 1137/19M125515X

    work page 2023

  6. [6]

    Călinescu and X

    G. Călinescu and X. Wang. A(1/2 + 1/60)-approximation algorithm for Maximum Weight Series-Parallel Subgraph.Discrete Applied Mathematics, 354:241–261, 2024.doi:10.1016/ j.dam.2023.09.019

    work page 2024

  7. [7]

    P. M. Camerini, G. Galbiati, and F. Maffioli. Random pseudo-polynomial algorithms for exact matroid problems.Journal of Algorithms, 13(2):258–273, 1992.doi:10.1016/0196- 6774(92)90018-8

    work page doi:10.1016/0196- 1992

  8. [8]

    A. W. M. Dress and W. Wenzel. Valuated matroids: a new look at the greedy algorithm. Applied Mathematics Letters, 3(2):33–35, 1990.doi:10.1016/0893-9659(90)90009-Z. 29

    work page doi:10.1016/0893-9659(90)90009-z 1990

  9. [9]

    J. Edmonds. Submodular functions, matroids, and certain polyhedra. InCombinatorial Struc- tures and Their Applications, pages 69–87. Gordon and Breach, New York, 1970.doi:10. 1007/3-540-36478-1_2

    work page 1970

  10. [10]

    J. Edmonds. Matroids and the greedy algorithm.Mathematical Programming, 1:127–136, 1971.doi:10.1007/BF01584082

    work page doi:10.1007/bf01584082 1971

  11. [11]

    Fekete and J

    Z. Fekete and J. Szabó. Equitable partitions to spanning trees in a graph.The Electronic Journal of Combinatorics, 18(1):P221, 2011.doi:10.37236/708

    work page doi:10.37236/708 2011

  12. [12]

    A. Frank. A weighted matroid intersection algorithm.Journal of Algorithms, 2(4):328–336, 1981.doi:10.1016/0196-6774(81)90032-8

    work page doi:10.1016/0196-6774(81)90032-8 1981

  13. [13]

    Fujishige and Z

    S. Fujishige and Z. Yang. A note on Kelso and Crawford’s gross substitutes condition.Math- ematics of Operations Research, 28(3):463–469, 2003.doi:10.1287/moor.28.3.463.16393

    work page doi:10.1287/moor.28.3.463.16393 2003

  14. [14]

    H. Gabow. Decomposing symmetric exchanges in matroid bases.Mathematical Programming, 10(1):271–276, 1976.doi:10.1007/bf01580672

    work page doi:10.1007/bf01580672 1976

  15. [15]

    I. M. Gelfand, M. Kapranov, and A. Zelevinsky.Discriminants, Resultants, and Multidimen- sional Determinants. Modern Birkhäuser Classics. Birkhauser Boston, Secaucus, NJ, 2008. doi:10.1007/978-0-8176-4771-1

    work page doi:10.1007/978-0-8176-4771-1 2008

  16. [16]

    C. Greene. A multiple exchange property for bases.Proceedings of the American Mathematical Society, 39(1):45–50, 1973.doi:10.2307/2038987

    work page doi:10.2307/2038987 1973

  17. [17]

    C. Greene. Another exchange property for bases.Proceedings of the American Mathematical Society, 46(1):155–156, 1974.doi:10.2307/2040500

    work page doi:10.2307/2040500 1974

  18. [18]

    Greene and T

    C. Greene and T. L. Magnanti. Some abstract pivot algorithms.SIAM Journal on Applied Mathematics, 29(3):530–539, 1975.doi:10.1137/0129045

    work page doi:10.1137/0129045 1975

  19. [19]

    Gul and E

    F. Gul and E. Stacchetti. Walrasian equilibrium with gross substitutes.Journal of Economic Theory, 87(1):95–124, 1999.doi:10.1006/jeth.1999.2531

    work page doi:10.1006/jeth.1999.2531 1999

  20. [20]

    Hörsch, A

    F. Hörsch, A. Imolay, R. Mizutani, T. Oki, and T. Schwarcz. Problems on group-labeled ma- troid bases. InProceedings of the 51st International Colloquium on Automata, Languages and Programming (ICALP ’24), volume 297 ofLIPIcs, 86:1–86:20. Schloss Dagstuhl — Leibniz- Zentrum für Informatik, 2024.doi:10.4230/LIPICS.ICALP.2024.86

    work page doi:10.4230/lipics.icalp.2024.86 2024

  21. [21]

    Huang, Y

    L. Huang, Y. Wang, C. Yang, and H. Zhou. Efficient submodular optimization under noise: local search is robust. InAdvances in Neural Information Processing Systems, volume 35, pages 26122–26134. Curran Associates, Inc., 2022

    work page 2022

  22. [22]

    D. Kotlar. On circuits and serial symmetric basis-exchange in matroids.SIAM Journal on Discrete Mathematics, 27(3):1274–1286, 2013.doi:10.1137/120867603

    work page doi:10.1137/120867603 2013

  23. [23]

    Kotlar and R

    D. Kotlar and R. Ziv. On serial symmetric exchanges of matroid bases.Journal of Graph Theory, 73(3):296–304, 2013.doi:10.1002/jgt.21675

    work page doi:10.1002/jgt.21675 2013

  24. [24]

    Krogdahl

    S. Krogdahl. A combinatorial base for some optimal matroid intersection algorithms. Techni- cal report STAN-CS-74-468, Computer Science Department, Stanford University, Stanford, 1974

    work page 1974

  25. [25]

    Krogdahl

    S. Krogdahl. A combinatorial proof for a weighted matroid intersection algorithm. Techni- cal report Computer Science Report 17, Institute of Mathematical and Physical Sciences, University of Tromso, Tromso, 1976. 30

    work page 1976

  26. [26]

    Krogdahl

    S. Krogdahl. The dependence graph for bases in matroids.Discrete Mathematics, 19(1):47– 59, 1977.doi:10.1016/0012-365X(77)90118-2

    work page doi:10.1016/0012-365x(77)90118-2 1977

  27. [27]

    J. P. S. Kung. Alternating basis exchanges in matroids.Proceedings of the American Mathe- matical Society, 71(2):355–358, 1978.doi:10.2307/2042864

    work page doi:10.2307/2042864 1978

  28. [28]

    J. Lee, M. Sviridenko, and J. Vondrák. Submodular maximization over multiple matroids via generalized exchange properties.Mathematics of Operations Research, 35(4):795–806, 2010. doi:10.1287/moor.1100.0463

    work page doi:10.1287/moor.1100.0463 2010

  29. [29]

    S. Li, Y. Jin, and D. I. Shuman. ScalableM-channel critically sampled filter banks for graph signals.IEEE Transactions on Signal Processing, 67(15):3954–3969, 2019.doi:10 . 1109 / TSP.2019.2923142

    work page arXiv 2019

  30. [30]

    Maclagan and B

    D. Maclagan and B. Sturmfels.Introduction to Tropical Geometry, volume 161 ofGraduate Studies in Mathematics. American Mathematical Society, Providence, 2015.doi:10.1090/ gsm/161

    work page 2015

  31. [31]

    J. H. Mason. On a class of matroids arising from paths in graphs.Proceedings of the London Mathematical Society. Third Series, s3-25(1):55–74, 1972.doi:10.1112/plms/s3-25.1.55

    work page doi:10.1112/plms/s3-25.1.55 1972

  32. [32]

    Murota.Matrices and Matroids for Systems Analysis, volume 20 ofAlgorithms and Com- binatorics

    K. Murota.Matrices and Matroids for Systems Analysis, volume 20 ofAlgorithms and Com- binatorics. Springer, Berlin, 2000.doi:10.1007/978-3-642-03994-2

    work page doi:10.1007/978-3-642-03994-2 2000

  33. [33]

    Murota.Discrete Convex Analysis, volume 10 ofMonographs on Discrete Mathematics and Applications

    K. Murota.Discrete Convex Analysis, volume 10 ofMonographs on Discrete Mathematics and Applications. SIAM, Philadelphia, 2003.doi:10.1137/1.9780898718508

    work page doi:10.1137/1.9780898718508 2003

  34. [34]

    K. Murota. A stronger multiple exchange property for M♮-concave functions.Japan Journal of Industrial and Applied Mathematics, 35(1):411–421, 2018.doi:10 . 1007 /s13160 - 017 - 0278-4

    work page 2018

  35. [35]

    K. Murota. Multiple exchange property for M ♮-concave functions and valuated matroids. Mathematics of Operations Research, 43(3):781–788, 2018.doi:10.1287/moor.2017.0882

    work page doi:10.1287/moor.2017.0882 2018

  36. [36]

    Nakasawa

    T. Nakasawa. Zur Axiomatik der linearen Abhängigkeit. I.Science Reports of the Tokyo Bunrika Daigaku, Section A, 2(43):235–255, 1935

    work page 1935

  37. [37]

    Nematollahi, A

    S. Nematollahi, A. Vladu, and J. Zhao. Fixed-parameter tractable submodular maximization over a matroid, 2025. arXiv:2509.01591

    work page arXiv 2025

  38. [38]

    R.Niazadeh,N.Golrezaei,J.Wang,F.Susan,andA.Badanidiyuru.Onlinelearningviaoffline greedy algorithms: applications in market design and optimization.Management Science, 69(7):3797–3817, 2023.doi:10.1287/mnsc.2022.4558

    work page doi:10.1287/mnsc.2022.4558 2023

  39. [39]

    G. Nie, M. Agarwal, A. Umrawal, V. Aggarwal, and C. J. Quinn. An explore-then-commit algorithm for submodular maximization under full-bandit feedback. InProceedings of the 38th Conference on Uncertainty in Artificial Intelligence, volume 180 ofPMLR, pages 1541–1551, 2022

    work page 2022

  40. [40]

    Oki and S

    T. Oki and S. Sakaue. Faster discrete convex function minimization with predictions: the M-convex case. InAdvances in Neural Information Processing Systems (NeurIPS ’23), vol- ume 36, pages 68576–68588. Curran Associates, Inc., 2023. 31

    work page 2023

  41. [41]

    Oki and S

    T. Oki and S. Sakaue. No-regret M♮-concave function maximization: stochastic bandit algo- rithms and NP-hardness of adversarial full-information setting. InAdvances in Neural Infor- mation Processing Systems (NeurIPS ’24), volume 37, pages 57418–57438. Curran Associates, Inc., 2024

    work page 2024

  42. [42]

    S. Onn. A colorful determinantal identity, a conjecture of Rota, and Latin squares.The American Mathematical Monthly, 104(2):156–159, 1997.doi:10 . 1080 / 00029890 . 1997 . 11990616

    work page 1997

  43. [43]

    J. G. Oxley.Matroid Theory. Oxford Graduate Texts in Mathematics. Oxford University Press, New York, second edition, 2011.doi:10.1093/acprof:oso/9780198566946.001. 0001

    work page doi:10.1093/acprof:oso/9780198566946.001 2011

  44. [44]

    Paes Leme

    R. Paes Leme. Gross substitutability: an algorithmic survey.Games and Economic Behavior, 106:294–316, 2017.doi:10.1016/j.geb.2017.10.016

    work page doi:10.1016/j.geb.2017.10.016 2017

  45. [45]

    A.Schrijver.Combinatorial Optimization,volume24ofAlgorithms and Combinatorics.Springer, Berlin, 2003

    work page 2003

  46. [46]

    A. Shioura. M-convex function minimization under L1-distance constraint and its application to dock reallocation in bike-sharing system.Mathematics of Operations Research, 47(2):1566– 1611, 2022.doi:10.1287/moor.2021.1180

    work page doi:10.1287/moor.2021.1180 2022

  47. [47]

    M. Z. Spivey.The Art of Proving Binomial Identities. Discrete Mathematics and Its Appli- cations. CRC Press, New York, 2019.doi:10.1201/9781351215824

    work page doi:10.1201/9781351215824 2019

  48. [48]

    M. J. Streeter and D. Golovin. An online algorithm for maximizing submodular functions. In Advances in Neural Information Processing Systems 21 (NIPS ’08), volume 21, pages 1577–

    work page

  49. [49]

    Curran Associates, Inc., 2008

    work page 2008

  50. [50]

    Traub and J

    V. Traub and J. Vygen. Beating the integrality ratio fors-t-tours in graphs.SIAM Journal on Computing, 52(6):FOCS18-37–FOCS18-84, 2023.doi:10.1137/18M1227135

    work page doi:10.1137/18m1227135 2023

  51. [51]

    Traub and R

    V. Traub and R. Zenklusen. Better-than-2 approximations for weighted tree augmentation and applications to Steiner tree.Journal of the ACM, 72(2):Article 16, 2025.doi:10.1145/ 3722101

    work page 2025

  52. [52]

    N. L. White. A unique exchange property for bases.Linear Algebra and its Applications, 31:81–91, 1980.doi:10.1016/0024-3795(80)90209-8

    work page doi:10.1016/0024-3795(80)90209-8 1980

  53. [53]

    H. Whitney. On the abstract properties of linear dependence.American Journal of Mathe- matics, 57(3):509–533, 1935.doi:10.2307/2371182

    work page doi:10.2307/2371182 1935

  54. [54]

    D. R. Woodall. An exchange theorem for bases of matroids.Journal of Combinatorial Theory, Series B, 16(3):227–228, 1974.doi:10.1016/0095-8956(74)90067-7. 32

    work page doi:10.1016/0095-8956(74)90067-7 1974