Matroid isomorphism games

Daniel Corey; Marcel Wack; Simon Schmidt

REVIEW 3 major objections 5 minor 20 references

Matroid isomorphism games

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read Nonisomorphic matroids can be quantum isomorphic, and this paper exhibits an explicit 18-element pair.

desk verdict A promising framework and a likely-true example, but the non-isomorphism proof has a genuine gap that needs to be fixed before the main theorem is solid. read the letter →

arxiv 2507.06225 v1 pith:OOEVVFLA submitted 2025-07-08 math.QA math-phmath.COmath.MP

Daniel Corey , Simon Schmidt , Marcel Wack This is my paper · ORCID

classification math.QAmath-phmath.COmath.MP MSC 05B3505E1616T3020B25

keywords matroidsnonlocalgamesquantumcommutingstrategiesisomorphismmatroidstructuresautomorphismgroupslinearbinaryconstraintsystemsmagic-squaregame

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

This paper translates matroid isomorphism into nonlocal games: for any standard axiomatic description of a matroid, such as bases, nonbases, circuits, flats, or hyperplanes, two matroids are isomorphic exactly when the corresponding game has a perfect classical winning strategy. It then allows quantum commuting strategies and defines a notion of quantum isomorphism of matroids. The central result is an explicit pair of rank-3 matroids on 18 elements, $P = M_{\mathrm{hom}}$ and $Q = M_S$, that are quantum isomorphic under the nonbasis game but are not isomorphic. The paper also gives an algebraic characterization: a certain $*$-algebra $G^\bullet(M,N,S)$ is nonzero exactly when the two matroids are $S$-quantum isomorphic, and this leads to new quantum automorphism groups of matroids.

What carries the argument

The machinery has three pieces. First, the matroid isomorphism game: for an isomorphism structure $S$, the referee sends pointed $S$-sets $(S,p)$ and the players must answer with pointed $S$-sets of the other matroid while preserving the four-valued relation rel (0 for same set and same point, 1 for different set and same point, 2 for same set and different point, 3 otherwise); this is the colored graph isomorphism game on the relation colored graph $G(M,S)$. Second, the conversion in Theorem 4.4 from a perfect quantum strategy for a linear binary constraint system game, here the magic-square system with the sign pattern $s_{789} = -1$, into a perfect quantum strategy for the nonbasis game between $M_{\mathrm{hom}}$ and $M_S$. Third, the isomorphism algebra $G^\bullet(M,N,S)$, a quotient of the quantum permutation algebra by relations enforcing preservation of rel; its nonvanishing characterizes quantum commuting winning strategies, and for $N = M$ it becomes the quantum automorphism group $\mathrm{Aut}^\bullet(M,S)$.

What would settle it

One could settle the quantum claim by computing the isomorphism algebra $G^\bullet(P,Q,\mathrm{NB})$; if it is the zero algebra, no perfect quantum commuting strategy exists for the nonbasis game. A more direct check would be to verify whether the magic-square linear binary constraint system with $s_{789} = -1$ has a perfect quantum commuting strategy, since a negative answer would invalidate the cited premise on which the main example depends.

Watch

Extended reading notes

Core claim

The central claim is Theorem 4.5: the matroids $P = M_{\mathrm{hom}}$ and $Q = M_S$, where $M$ is the rank-3 matroid on nine points whose nonbases are the three rows and three columns of a $3\times3$ grid, and where $S$ is the sign choice $s_{789} = -1$ with all other signs $+1$, are not isomorphic but are NB-quantum isomorphic. They have the same rank, ground-set size, numbers of bases, independent sets, circuits, flats, and hyperplanes, the same connectivity, the same Tutte polynomial, and isomorphic automorphism groups, yet no isomorphism exists. The non-isomorphism is certified by a minor argument: $Q$ has a restriction isomorphic to the matroid whose nonbases are $123$, $456$, and $789$, while no restriction of $P$ is. The quantum isomorphism comes from a perfect quantum commuting strategy for the magic-square linear binary constraint system, converted by Theorem 4.4 into a perfect strategy for the nonbasis matroid game.

Load-bearing premise

The construction rests on the known theorem that the magic-square linear binary constraint system with the sign pattern $s_{789} = -1$ and all other signs $+1$ has a perfect quantum commuting strategy; if that theorem were wrong, the proof that $P$ and $Q$ are NB-quantum isomorphic would collapse.

Editorial extensions

If this is right

If two matroids are $S$-quantum isomorphic for a covering structure $S$, then their ground sets have the same size, and for each $r$ the number of $S$-sets of size $r$ is the same.
Quantum isomorphism can occur without isomorphism: the nonbasis game cannot separate $P$ and $Q$ even though a matroid minor argument does.
Existence of a perfect quantum commuting strategy for the matroid game is equivalent to nonvanishing of the explicit $*$-algebra $G^\bullet(M,N,S)$, connecting matroid isomorphism to the algebraic toolkit of quantum graph isomorphism, including tracial states and bigalois extensions.
The construction produces matroids whose quantum automorphism group $\mathrm{Aut}^\bullet(M,\mathrm{NB})$ is noncommutative even when the earlier bases-based quantum automorphism group is commutative.
Under circuit-quantum isomorphism, the property of being paving is preserved when the ranks agree.

Reading between the lines

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

Any linear binary constraint system with a perfect quantum commuting strategy and no perfect classical strategy should similarly generate nonisomorphic but quantum isomorphic matroids by the same doubling construction; the magic-square system is the first example, not the only one.
Because the matroid game is a colored graph isomorphism game, the known wealth of quantum isomorphic but nonisomorphic graphs suggests many more matroid pairs exist, possibly on smaller ground sets than 18.
Flipping different subsets of signs in the magic-square system would produce companion matroids $M_S$; checking which of those are pairwise nonisomorphic but quantum isomorphic would test how robust the construction is.
The paper's automorphism-group criterion detects noncommutativity of the algebra, but a natural next step is to decide when $\mathrm{Aut}^\bullet(M,S)$ differs from the classical automorphism group as a quantum group, not merely as an algebra.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Bottom line: this is a genuinely interesting paper that likely points to something true, but the proof of the main non-isomorphism claim has a gap that needs to be closed. The stress-test note is correct on both counts, so the referee should ask for a complete proof.

What's actually new: the idea of defining matroid isomorphism games for each axiomatic structure S, and the quantum version, is a fresh bridge between matroid theory and quantum information. The classical characterization (Theorem A) is clean. The construction of non-isomorphic matroids that are quantum isomorphic from the Mermin-Peres magic square is a nice application of LBCS games. Theorem 4.4 is a genuinely useful transfer principle. If the example is fixed, it gives the first pair of nonisomorphic quantum isomorphic matroids. The algebraic characterization (Theorem 5.3) and the new quantum automorphism groups Aut•(M,S) are also valuable, and the disjoint automorphism criterion (Theorem 6.6) is a nice tool.

The soft spots: the non-isomorphism direction of Theorem 4.5. The proof exhibits a 9-element restriction of Q that looks like N, and then tries to show no such restriction exists in P. The first issue: in the subcase where H1 = {(1,+),(2,-),(3,-)} and π(H2)=147, the claimed fourth nonbasis {(1,-),(2,-),(3,+)} uses (3,+), which is not necessarily in X because the only label-3 element in X may be (3,-). There is an alternative witness {(1,-),(2,+),(3,-)}, so the subcase may be salvageable, but the written argument is wrong. More seriously, the step 'Without loss of generality, suppose 2 ∈ π(H3), so π(H3)=258' is not WLOG: π(H3) could also be 456, 369, or 789. The sign pattern with s789 = -1 breaks the symmetry of the 3x3 grid, so a generic permutation of labels is not available. The argument must handle these cases separately. This matters because the non-isomorphism claim is the only thing separating P and Q from being isomorphic. The paper lists many shared invariants, so this minor argument is load-bearing. Theorem 5.3 is only sketched and relies on [3] for the bigalois extension and the faithful tracial state; that is likely fine but needs verification.

Who this is for: matroid theorists and quantum information people. The framework is worth knowing even if the example needs repair. I would send it to peer review, but the referee should ask for a complete proof of Theorem 4.5 before acceptance.

Referee Report

3 major / 5 minor

Summary. The paper defines matroid isomorphism games associated with cryptomorphic axiom systems S, proves that perfect classical strategies detect ordinary matroid isomorphism (Theorem A), and introduces S-quantum isomorphism via perfect quantum commuting strategies. The main construction (Theorem B) builds rank-3 matroids P and Q on 18 elements from the Mermin-Peres magic square and claims they are NB-quantum isomorphic but not isomorphic. The paper also defines a *-algebra G•(M,N,S) whose nonvanishing is claimed to characterize quantum isomorphism (Theorem 5.3), derives preservation of ground-set size and other numerical invariants, and introduces a quantum automorphism group Aut•(M,S) with a disjoint automorphism criterion. The authors report that P and Q share many invariants, including Tutte polynomial and automorphism group, so the non-isomorphism claim rests on a minor argument involving a rank-3 restriction.

Significance. If the proof of Theorem 4.5 is repaired, the paper's central example would be an explicit, low-rank pair of nonisomorphic matroids that are quantum isomorphic, a genuinely new phenomenon for matroids and a natural analogue of quantum graph isomorphism. The algebraic characterization and the new quantum automorphism group Aut•(M,S) are potentially useful tools, and Theorem D gives a clean separation from the earlier quantum automorphism groups in [7]. The paper is constructive and several auxiliary results (Theorem A, Theorem 3.10, Proposition 5.5) are supported by detailed arguments. However, the non-isomorphism direction of Theorem 4.5 is not proved as written, and Theorem 5.3 is only sketched, so the advertised central claims are not yet fully established.

major comments (3)

[Section 4.3, proof of Theorem 4.4] The non-isomorphism argument is incomplete and contains false statements. In the case H1={(1,+),(2,-),(3,-)} with π(H2)=147 and π(H3)=258, the displayed fourth nonbasis {(1,-),(2,-),(3,+)} is not contained in X: X contains (3,-) from H1 and no (3,+), since neither H2 nor H3 involves label 3. The valid witness is {(1,-),(2,+),(3,-)}. The step "Without loss of generality, suppose 2∈π(H3), so π(H3)=258" skips the possibilities π(H3)∈{369,456,789} and requires a symmetry argument that is not supplied. In the following paragraph, the statement "{π(H1),π(H2),π(H3)} equals {123,345,789} or {147,258,369}" contains the invalid line 345, and the immediately following assignment π(H1)=123, π(H2)=258, π(H3)=789 is not a partition of {1,...,9}; the intended row partition is presumably {123,456,789} with π(H2)=456. As written, the proof does not establish that no restriction of P is isomorphic to N.
[Section 5.2, proof of Theorem 5.3] The strategy in Theorem 4.4 is only explained for the case where the input pointed nonbases come from Mhom. The sentence "since tA and tB are fulfilling assignments in the homogeneous system" is false when an input belongs to MS; in that case tA satisfies the S-system, not the homogeneous system. The proof should explicitly verify that tA*kA lies in the required output matroid for every combination of inputs from Mhom and MS and that the four relation cases remain valid in the mixed cases. The computation appears to be the same in the missing case, so this is a fixable gap, but as stated the proof of the quantum-isomorphism direction of Theorem 4.5 is incomplete.
[Section 5.2] The converse direction of Theorem 5.3 is only sketched. The bijectivity of the map kl is asserted without verification, and the existence of a faithful tracial state on G•(M,N,S) is delegated to Theorems 3.15 and 3.17 of [3] without checking that the hypotheses of those theorems are satisfied. Since Theorem 5.3 is advertised as a purely algebraic characterization of quantum isomorphism and is used in Section 5.3 and in the definition of Aut•(M,S), the proof should be completed or the theorem should be reformulated as a precise reduction to the cited results with all hypotheses verified.

minor comments (5)

[Proposition 2.3(3)] The statement "if and only if M is not a free extension of a paving matroid or M does not split as a direct sum..." should logically read "if and only if M is neither a free extension of a paving matroid nor a direct sum of the form U(1,1)⊕U(r−1,n−1)"; the current wording is ambiguous.
[Section 4.3] The notation is inconsistent: Theorem 4.4 speaks of the "(Mhom,MS,NB)-isomorphism game" and an NB-isomorphism, while Theorem 4.5 says "NB•-quantum isomorphic". The bullet is not defined for quantum isomorphism of matroids.
[Section 3.2] In the proof of Theorem 3.6, the sentence "A≠Sy_{k+1}" should instead compare A with S_{b_{k+1}}; as written the subscript refers to a pointed set in N rather than in M.
[Section 4.3] In the first paragraph of the proof, "the 3 nonbases of Q|Y" should be "the three nonbases of Q|Y" for grammar; more importantly, the sentence listing them is correct but could explicitly state why no other 3-subsets of Y are nonbases of Q.
[Section 4.3] The sentence "we get that tA ∗ kA and tB ∗ kB fulfilling assignments" is missing the verb "are".

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; central quantum-isomorphism construction rests on the external Mermin-Peres strategy and independently cited algebraic results.

full rationale

The derivation chain of the central claim (Theorem 4.5) is self-contained against external benchmarks. The quantum-isomorphism direction is built in Theorem 4.4 from a perfect quantum strategy for the Mermin-Peres linear binary constraint system, cited to [10]; this is an external, well-known result and is not derived from the matroids P and Q or from the game definitions. The non-isomorphism direction is attempted by a restriction argument comparing P and Q; whatever gaps it may have are correctness issues, not circular reductions. Theorem 5.3's algebraic criterion uses bigalois-extension results of [3], an external source, and the subsequent ground-set cardinality results are proved from the algebra. The references to overlapping-author prior work ([7], [16]) are not load-bearing for the main existence theorem: [7] supplies a published comparison statement for Theorem D, and Example 6.8 includes an explicit commutativity proof in the r=3 case. No parameter is fitted to a subset of data and then renamed a prediction, no quantity is defined in terms of the target quantity, and no equation used in the proof is equivalent to its input by construction.

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

No free parameters are fitted or chosen ad hoc. The paper's load rests on standard background in matroid theory and quantum information, the pre-existing magic square quantum strategy, and the stated covering condition. The new algebraic objects (G•, Aut•) are proven constructs rather than unexplained postulates.

assumptions (5)

standard math Matroid axiomatics and the cyclic flats lattice characterization of matroids
Used throughout; the construction of M_S from a rank-3 sparse paving matroid in Section 4.1 relies on this characterization.
standard math Synchronous game lemma: perfect quantum commuting strategies correspond to tracial states on a C*-algebra with PVM relations
This is Lemma 3.9, cited from [13]; it underlies Theorems 3.10 and 5.3.
standard math Nonvanishing of the graph isomorphism algebra implies existence of a quantum commuting isomorphism strategy for colored graphs, via bigalois extensions
The proof of Theorem 5.3 is a sketch that delegates the construction of a faithful tracial state to the bigalois extension theorems of [3].
domain assumption The Mermin-Peres magic square linear binary constraint system with the sign pattern used here has a perfect quantum commuting strategy
Used in Theorem 4.4 to produce the quantum strategy for the matroid game; cited as well-known from [10], not proved in this paper.
domain assumption The isomorphism structure S covers the matroids M and N, meaning every ground-set element lies in some member of S
A stated technical hypothesis in Theorems A, C, 5.3, and 6.3; Proposition 2.3 gives conditions for the standard structures.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Matroid isomorphism games." pith.science (2026). https://pith.science/paper/OOEVVFLA

@misc{pith2026250706225,
  author       = {Pith},
  title        = {Pith review of: Matroid isomorphism games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OOEVVFLA}},
  note         = {Machine review of arXiv:2507.06225}
}

read the original abstract

We define and study a collection of matroid isomorphism games corresponding to various axiomatic characterizations of matroids. These are nonlocal games played between two cooperative players. Each game is played on two matroids, and the matroids are isomorphic if and only if the game has a perfect classical winning strategy. We define notions of quantum isomorphism in terms of perfect quantum commuting strategies, and we find a pair of nonisomorphic matroids that are quantum isomorphic. We also give a purely algebraic characterization of quantum isomorphic matroids. Finally, we use this notion of quantum isomorphism to describe a new type of quantum automorphism group of a matroid and derive a sufficient condition for a matroid to have nonclassical quantum automorphism.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[3]

Brannan, A

M. Brannan, A. Chirvasitu, K. Eifler, S. Harris, V . Paulsen, X. Su, and M. Wasilewski. Bigalois extensions and the graph isomorphism game. Comm. Math. Phys., 375(3):1777–1809, 2020

work page 2020
[7]

Corey, M

D. Corey, M. Joswig, J. Schanz, M. Wack, and M. Weber. Quantum automorphisms of matroids. J. Algebra, 667:480–507, 2025

work page 2025
[1]

Atserias, L

A. Atserias, L. Manˇ cinska, D. E. Roberson, R. Šámal, S. Severini, and A. Varvitsiotis. Quantum and non- signalling graph isomorphisms. Journal of Combinatorial Theory, Series B, 136:289–328, 2019

work page 2019
[2]

J. E. Bonin and A. de Mier. The lattice of cyclic flats of a matroid. Ann. Comb., 12(2):155–170, 2008

work page 2008
[4]

Cleve, P

R. Cleve, P . Hoyer, B. Toner, and J. Watrous. Consequences and limits of nonlocal strategies. InProceedings. 19th IEEE Annual Conference on Computational Complexity, 2004., pages 236–249, 2004

work page 2004
[5]

Cleve, L

R. Cleve, L. Liu, and W. Slofstra. Perfect commuting-operator strategies for linear system games. Journal of Mathematical Physics, 58(1):012202, 01 2017

work page 2017
[6]

Cleve and R

R. Cleve and R. Mittal. Characterization of binary constraint system games. In J. Esparza, P . Fraigniaud, T. Husfeldt, and E. Koutsoupias, editors, Automata, Languages, and Programming , pages 320–331, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg

work page 2014
[8]

C. Eder, W. Decker, C. Fieker, M. Horn, and M. Joswig, editors. The OSCAR book. Springer, 2024

work page 2024

Show all 20 references

[9]

A. Freslon. Compact matrix quantum groups and their combinatorics, volume 106 ofLondon Mathematical Society Student Texts. Cambridge University Press, Cambridge, 2023

2023
[10]

N. D. Mermin. Simple unified form for the major no-hidden-variables theorems. Phys. Rev. Lett., 65:3373– 3376, Dec 1990

1990
[11]

J. Oxley. Matroid theory, volume 21 ofOxford Graduate Texts in Mathematics. Oxford University Press, Oxford, second edition, 2011

2011
[12]

V . I. Paulsen and M. Rahaman. Bisynchronous games and factorizable maps.Ann. Henri Poincaré, 22(2):593– 614, 2021

2021
[13]

V . I. Paulsen, S. Severini, D. Stahlke, I. G. Todorov, and A. Winter. Estimating quantum chromatic numbers. J. Funct. Anal., 270(6):2188–2222, 2016

2016
[14]

D. E. Roberson and S. Schmidt. Solution group representations as quantum symmetries of graphs. Journal of the London Mathematical Society, 106(4):3379–3410, 2022

2022
[15]

S. Schmidt. Quantum automorphism groups of finite graphs. PhD thesis, Universität des Saarlandes, 2020

2020
[16]

S. Schmidt. Quantum automorphisms of folded cube graphs. Ann. Inst. Fourier (Grenoble) , 70(3):949–970, 2020

2020
[17]

OSCAR – Open Source Computer Algebra Research system, version 1.4.1, 2023

The OSCAR Team. OSCAR – Open Source Computer Algebra Research system, version 1.4.1, 2023

2023
[18]

S. Wang. Ergodic actions of universal quantum groups on operator algebras.Comm. Math. Phys., 203(2):481– 498, 1999

1999
[19]

M. Weber. Quantum permutation matrices. Complex Anal. Oper. Theory, 17(3):Paper No. 37, 26, 2023

2023
[20]

H. Whitney. On the abstract properties of linear dependence. Amer. J. Math., 57(3):509–533, 1935. DANIEL COREY, E MBRY–R IDDLE AERONAUTICAL UNIVERSITY , D EPARTMENT OF MATHEMATICS . D AY- TONA BEACH , FLORIDA . Email address: daniel.corey@unlv.edu SIMON SCHMIDT , RUHR UNIVERSI...

1935

Pith tools

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

[1] [3]

Brannan, A

M. Brannan, A. Chirvasitu, K. Eifler, S. Harris, V . Paulsen, X. Su, and M. Wasilewski. Bigalois extensions and the graph isomorphism game. Comm. Math. Phys., 375(3):1777–1809, 2020

work page 2020

[2] [7]

Corey, M

D. Corey, M. Joswig, J. Schanz, M. Wack, and M. Weber. Quantum automorphisms of matroids. J. Algebra, 667:480–507, 2025

work page 2025

[3] [1]

Atserias, L

A. Atserias, L. Manˇ cinska, D. E. Roberson, R. Šámal, S. Severini, and A. Varvitsiotis. Quantum and non- signalling graph isomorphisms. Journal of Combinatorial Theory, Series B, 136:289–328, 2019

work page 2019

[4] [2]

J. E. Bonin and A. de Mier. The lattice of cyclic flats of a matroid. Ann. Comb., 12(2):155–170, 2008

work page 2008

[5] [4]

Cleve, P

R. Cleve, P . Hoyer, B. Toner, and J. Watrous. Consequences and limits of nonlocal strategies. InProceedings. 19th IEEE Annual Conference on Computational Complexity, 2004., pages 236–249, 2004

work page 2004

[6] [5]

Cleve, L

R. Cleve, L. Liu, and W. Slofstra. Perfect commuting-operator strategies for linear system games. Journal of Mathematical Physics, 58(1):012202, 01 2017

work page 2017

[7] [6]

Cleve and R

R. Cleve and R. Mittal. Characterization of binary constraint system games. In J. Esparza, P . Fraigniaud, T. Husfeldt, and E. Koutsoupias, editors, Automata, Languages, and Programming , pages 320–331, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg

work page 2014

[8] [8]

C. Eder, W. Decker, C. Fieker, M. Horn, and M. Joswig, editors. The OSCAR book. Springer, 2024

work page 2024