pith. sign in

arxiv: 2606.11014 · v1 · pith:WNK4CX4Anew · submitted 2026-06-09 · 🧮 math.CO · math.AC· math.AG

There are matroid toric ideals without quadratic Gr\"obner bases

Jes\'us A. De Loera , Luis Ferroni , Santiago Morales , J\"org Rambau This is my paper

Pith reviewed 2026-06-27 12:36 UTC · model grok-4.3

classification 🧮 math.CO math.ACmath.AG
keywords matroidtoric idealGröbner basisFano planebase polytopeflag triangulationminor
0
0 comments X

The pith

Matroids containing the Fano plane or its dual as a minor have toric ideals without quadratic Gröbner bases.

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

The paper proves that any matroid with the Fano plane or its dual as a minor yields a toric ideal that admits no quadratic Gröbner basis. This settles a question posed by Herzog and Hibi by translating the algebraic condition into the non-existence of regular unimodular flag triangulations of the corresponding base polytopes. The argument rests on a new lemma relating the 1-skeleton of a lattice polytope to lattice points in its dilates, followed by a SAT-solver search that rules out the desired triangulations for the Fano cases. A reader would care because the result supplies an explicit combinatorial obstruction that separates matroids whose toric ideals behave well under Gröbner-basis computations from those that do not.

Core claim

If a matroid contains the Fano plane or its dual as a minor, then its toric ideal does not have any quadratic Gröbner basis. This is obtained by showing that the base polytopes of the Fano plane and its dual possess no regular unimodular flag triangulations, which by the Hibi-Herzog-Sturmfels correspondence precludes quadratic Gröbner bases; the non-existence is verified via a lattice-point lemma and exhaustive SAT encoding.

What carries the argument

The base polytopes of the Fano plane and its dual, shown to lack regular unimodular flag triangulations and thereby to force the absence of quadratic Gröbner bases for the associated toric ideals.

If this is right

  • Matroid toric ideals are separated into those with and without quadratic Gröbner bases by the presence of the Fano plane or its dual as a minor.
  • The Fano plane and its dual are minimal forbidden minors for the property of possessing a quadratic Gröbner basis.
  • Boolean satisfiability encodings can certify the absence of regular unimodular flag triangulations for concrete base polytopes.
  • The new 1-skeleton-to-dilation lemma supplies a general tool for studying triangulation questions on lattice polytopes arising from matroids.

Where Pith is reading between the lines

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

  • The same minor-based criterion might obstruct other algebraic invariants of matroid ideals, such as the existence of square-free initial ideals.
  • Systematic SAT searches over larger families of matroids could produce a complete list of minimal examples without quadratic Gröbner bases.
  • The result indicates that the quadratic-Gröbner-basis property for matroid toric ideals is minor-closed only after excluding the Fano cases.
  • In applications to algebraic statistics, matroids with these minors can be flagged in advance as requiring non-quadratic Gröbner-basis methods.

Load-bearing premise

The lemma that links the 1-skeleton of a lattice polytope to lattice points in its dilations is correct and the SAT encoding faithfully detects that the Fano base polytopes admit no regular unimodular flag triangulation.

What would settle it

Exhibiting an explicit regular unimodular flag triangulation of the base polytope of the Fano plane (or its dual) would falsify the claim.

read the original abstract

Our paper shows that if a matroid contains the Fano plane or its dual as a minor, then its toric ideal does not have any quadratic Gr\"obner basis. More than 25 years ago, Hibi, Herzog, and Sturmfels established a direct connection between the existence of quadratic Gr\"obner bases and regular unimodular flag triangulations. Our paper solves a famous question posed by Herzog and Hibi on a polyhedral reformulation for the existence of quadratic Gr\"obner bases: we show that the base polytopes of the Fano plane and its dual do not have regular unimodular flag triangulations which implies the main result on Gr\"obner bases. Our proof relies on several novel tools: a lemma that connects the $1$-skeleton of a lattice polytope to the lattice points in its dilations, an encoding with Boolean formulas and SAT solvers, and symmetry-breaking arguments.

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

3 major / 1 minor

Summary. The manuscript proves that if a matroid contains the Fano plane or its dual as a minor, then its toric ideal has no quadratic Gröbner basis. Building on the Hibi-Herzog-Sturmfels equivalence between quadratic Gröbner bases and regular unimodular flag triangulations of base polytopes, the authors show that the base polytopes of the Fano matroid and its dual admit no such triangulations. The proof introduces a new lemma relating the 1-skeleton of a lattice polytope to lattice points in its dilations, encodes the triangulation problem via Boolean formulas, and uses SAT solvers with symmetry-breaking arguments to establish non-existence.

Significance. If the new lemma and SAT encoding are correct, the result supplies the first explicit examples of matroid toric ideals without quadratic Gröbner bases and affirmatively answers a question of Herzog and Hibi on the polyhedral reformulation. The computational approach via SAT solvers for certifying non-existence of regular unimodular flag triangulations is a methodological contribution that could apply to other problems in matroid theory and polyhedral combinatorics.

major comments (3)
  1. [new lemma (abstract and proof description paragraph)] The new lemma (described in the abstract and proof outline) relating the 1-skeleton of a lattice polytope to lattice points in its dilations is invoked to translate polytope data into Boolean constraints for the SAT encoding; its precise statement, proof, and application to the Fano base polytope must be verified, as an error here falsifies the reduction to the triangulation non-existence claim.
  2. [SAT encoding and symmetry-breaking arguments] The SAT encoding asserting non-existence of regular unimodular flag triangulations for the Fano base polytope (and dual) provides no independent certificate such as an UNSAT proof trace, solver log, or formal verification of the encoding; without this, the central computational step remains uninspectable and load-bearing for the main theorem.
  3. [main theorem and Fano base polytope construction] The identification of the base polytope of the Fano matroid and the confirmation that the symmetry-breaking arguments preserve the correctness of the non-existence result need explicit cross-checks against the polytope definition, as any mismatch would undermine the implication from the polyhedral statement to the matroid-minor statement.
minor comments (1)
  1. [Abstract] The abstract could include the precise citation to the Hibi-Herzog-Sturmfels theorem for immediate context.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough review and for recognizing the significance of our results on matroid toric ideals and the polyhedral reformulation of Herzog and Hibi's question. We address each major comment below with clarifications and commitments to revisions where appropriate.

read point-by-point responses

  1. Referee: [new lemma (abstract and proof description paragraph)] The new lemma (described in the abstract and proof outline) relating the 1-skeleton of a lattice polytope to lattice points in its dilations is invoked to translate polytope data into Boolean constraints for the SAT encoding; its precise statement, proof, and application to the Fano base polytope must be verified, as an error here falsifies the reduction to the triangulation non-existence claim.

    Authors: We agree that a fully explicit treatment of the new lemma is essential for verifying the reduction. In the revised manuscript we will state the lemma precisely, provide its complete proof, and include a detailed, step-by-step application to the Fano base polytope that shows exactly how the 1-skeleton data is converted into the Boolean constraints. This will eliminate any ambiguity in the translation step. revision: yes

  2. Referee: [SAT encoding and symmetry-breaking arguments] The SAT encoding asserting non-existence of regular unimodular flag triangulations for the Fano base polytope (and dual) provides no independent certificate such as an UNSAT proof trace, solver log, or formal verification of the encoding; without this, the central computational step remains uninspectable and load-bearing for the main theorem.

    Authors: We acknowledge that an independent certificate would increase inspectability. A full UNSAT proof trace for the instance size is impractical to include, but we will add to an appendix the complete Boolean encoding (including all clauses and symmetry-breaking constraints) together with the solver invocation log and output. Readers will then be able to reproduce or re-encode the instance directly. This constitutes a partial revision that addresses the core concern while remaining feasible for the paper format. revision: partial

  3. Referee: [main theorem and Fano base polytope construction] The identification of the base polytope of the Fano matroid and the confirmation that the symmetry-breaking arguments preserve the correctness of the non-existence result need explicit cross-checks against the polytope definition, as any mismatch would undermine the implication from the polyhedral statement to the matroid-minor statement.

    Authors: We will insert an explicit verification subsection that lists the vertices of the Fano base polytope as defined from the matroid and confirms they match the standard combinatorial description. We will also supply a self-contained argument demonstrating that the symmetry-breaking clauses preserve the satisfiability status of the original encoding, with direct references back to the polytope data. These additions will make the chain from polytope to matroid minor fully traceable. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation uses external theorem plus independent computational verification

full rationale

The paper's main result chains the Hibi-Herzog-Sturmfels equivalence (external, 25+ years old, different authors) to a new non-existence claim for the Fano base polytope. That claim rests on a novel lemma relating 1-skeletons to dilates plus a SAT encoding; neither reduces by definition or self-citation to the target statement, nor is any parameter fitted and relabeled as a prediction. No self-citation is load-bearing, no uniqueness theorem is imported from the present authors, and no ansatz is smuggled. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Central claim rests on the cited equivalence between quadratic Gröbner bases and regular unimodular flag triangulations together with the correctness of the new lemma and the SAT computation for the Fano polytope; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Quadratic Gröbner bases for matroid toric ideals exist if and only if the base polytope admits a regular unimodular flag triangulation (Hibi, Herzog, Sturmfels)
    Invoked in the abstract as the established link that reduces the Gröbner-basis question to the polyhedral question solved here.

pith-pipeline@v0.9.1-grok · 5707 in / 1325 out tokens · 32719 ms · 2026-06-27T12:36:04.472416+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Simplex faces and quadratic toric ideals of lattice polytopes

    math.CO 2026-06 unverdicted novelty 6.0

    Proves that quadratic toric ideal generation implies the clique-face property for lattice polytopes under mild conditions, with characterizations for (0,1)-polytopes and verifications for edge, cut, simple, and matroi...

  2. Simplex faces and quadratic toric ideals of lattice polytopes

    math.CO 2026-06 unverdicted novelty 6.0

    Introduces the clique-face property and proves its relation to quadratic toric ideal generation for lattice polytopes, with equivalences for edge and cut polytopes and verifications for matroid polytopes.

Reference graph

Works this paper leans on

13 extracted references · cited by 1 Pith paper

  1. [1]

    Anick,On the homology of associative algebras, Trans

    [Ani86] David J. Anick,On the homology of associative algebras, Trans. Amer. Math. Soc.296 (1986), no. 2, 641–659. MR 846601 16 [Ard18] Federico Ardila,The geometry of matroids, Notices Amer. Math. Soc.65(2018), no. 8, 902–908. 4 [Ath11] Christos A. Athanasiadis,Some combinatorial properties of flag simplicial pseudomani- folds and spheres, Ark. Mat.49(20...

    1986

  2. [2]

    com/arminbiere/cadical/releases/tag/rel-1.7.3, 2023, GitHub releaserel-1.7.3, commit38e073b

    2 [Bie23] Armin Biere,CaDiCaL simplified satisfiability solver, version 1.7.3,https://github. com/arminbiere/cadical/releases/tag/rel-1.7.3, 2023, GitHub releaserel-1.7.3, commit38e073b. Accessed 8 June

    2023

  3. [3]

    Kotsireas, and Vijay Ganesh,When satisfiability solving meets symbolic computation, Commun

    15 [BKG22] Curtis Bright, Ilias S. Kotsireas, and Vijay Ganesh,When satisfiability solving meets symbolic computation, Commun. ACM65(2022), no. 7, 64–72. 2 [BL25] Spencer Backman and Gaku Liu,A regular unimodular triangulation of the matroid base polytope, Duke Math. J.174(2025), no. 14, 3047–3061. MR 4975040 2 [Blu01] Stefan Blum,Base-sortable matroids a...

    2022

  4. [4]

    De Loera, David C

    7 [DLHK09] Jes´ us A. De Loera, David C. Haws, and Matthias K¨ oppe,Ehrhart polynomials of ma- troid polytopes and polymatroids, Discrete Comput. Geom.42(2009), no. 4, 670–702. MR 2556462 13, 17 [DLRS10] Jes´ us A. De Loera, J¨ org Rambau, and Francisco Santos,Triangulations, Algorithms and Computation in Mathematics, vol. 25, Springer-Verlag, Berlin, 201...

    arXiv 2009

  5. [5]

    5 [Kas10] Kenji Kashiwabara,The toric ideal of a matroid of rank 3 is generated by quadrics, Electron. J. Combin.17(2010), no. 1, Research Paper 28,

    2010

  6. [6]

    Math.259 (2014), 1–12

    3 [LM14] Micha l Laso´ n and Mateusz Micha lek,On the toric ideal of a matroid, Adv. Math.259 (2014), 1–12. MR 3197649 3 [LP07] Thomas Lam and Alexander Postnikov,Alcoved polytopes. I, Discrete Comput. Geom. 38(2007), no. 3, 453–478. MR 2352704 1 [LP18] ,Alcoved polytopes II, Lie groups, geometry, and representation theory, Progr. Math., vol. 326, Birkh¨ ...

    2014

  7. [7]

    Combin.32(2011), no

    MR 4718184 1 [MNWW11] Dillon Mayhew, Mike Newman, Dominic Welsh, and Geoff Whittle,On the asymp- totic proportion of connected matroids, European J. Combin.32(2011), no. 6, 882–890. MR 2821559 3 [MS05] Ezra Miller and Bernd Sturmfels,Combinatorial commutative algebra, Graduate Texts in Mathematics, vol. 227, Springer-Verlag, New York,

    2011

  8. [8]

    MR 4423369 16 [MT02] Diane Maclagan and Rekha R

    ©2021. MR 4423369 16 [MT02] Diane Maclagan and Rekha R. Thomas,Combinatorics of the toric Hilbert scheme, Dis- crete Comput. Geom.27(2002), no. 2, 249–272. 9 [OH99] Hidefumi Ohsugi and Takayuki Hibi,Toric ideals generated by quadratic binomials, J. Algebra218(1999), no. 2, 509–527. MR 1705794 1 [Oxl11] James Oxley,Matroid theory, second ed., Oxford Gradua...

    2021

  9. [9]

    MR 2849819 4, 15 [Pay08] Sam Payne,Ehrhart series and lattice triangulations, Discret. Comput. Geom.40(2008), no. 3, 365–376. 9 MATROID TORIC IDEALS WITHOUT GR ¨OBNER BASES 19 [Pay09] Sam Payne,Lattice polytopes cut out by root systems and the Koszul property, Adv. Math.220(2009), no. 3, 926–935. MR 2483232 16 [PP05] Alexander Polishchuk and Leonid Posits...

    2008

  10. [10]

    MR 2177131 16 [Ram02] J¨ org Rambau,TOPCOM: Triangulations of point configurations and oriented matroids, Mathematical software (Beijing, 2002), World Scientific Publishing, River Edge, NJ, 2002, pp. 330–340. 14 [Ram26] J¨ org Rambau,Symmetric lexicographic symmetric-subset reverse search for the enumer- ation of cocircuits, circuits, and triangulations, ...

    2002

  11. [11]

    Algebra Appl.15(2016), no

    2 [Shi16] Kazuki Shibata,Toric ideals of series and parallel connections of matroids, J. Algebra Appl.15(2016), no. 6, 1650106,

    2016

  12. [12]

    MR 1363949 1, 4 [vdP23] Jorn van der Pol,Almost every matroid has anM(K 4)- or aW 3-minor, Electron. J. Combin.30(2023), no. 4, Paper No. 4.23,

    2023

  13. [13]

    White,A unique exchange property for bases, Linear Algebra Appl.31(1980), 81–91

    4 [Whi80] Neil L. White,A unique exchange property for bases, Linear Algebra Appl.31(1980), 81–91. MR 570381 1, 3 [YY25] Yu-Chuan Yu and Chi Ho Yuen,White’s Conjecture for Paving Matroids, arXiv e-prints (2025), arXiv:2510.04163. 3 [Zie95] G¨ unter M. Ziegler,Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York,

    arXiv 1980