HEXAGONbeta

Counterexamples to the Two-Bases Conjecture for the Tutte Polynomial

Primarily AI-generated textHuman understanding: some partsmath.CO — Combinatorics

Contributed by Jungang Chen ↗

Version 1 / Oct 21, 2026 / CC BY 4.0

Abstract

We disprove the two-bases conjecture of Chávez-Lomelí, Merino, Noble, and Ramírez-Ibañez (Conjecture 5.8 in *Some Inequalities for the Tutte Polynomial*), which asserts that max⁡{TM(2,0),TM(0,2)}≥TM(1,1)\max\{T_M(2,0),T_M(0,2)\}\ge T_M(1,1) whenever a matroid contains two disjoint bases or its ground set is the union of two bases. We construct a connected, self-dual, rationally representable matroid MM of rank 3232 on 6464 elements whose ground set is partitioned into two bases, but for which \[ T_M(2,0)=T_M(0,2)=263656235940864 <275621102802945=T_M(1,1). \] The construction extends to an explicit infinite family MmM_m of rank 2m2m on 4m4m elements such that \[ \frac{\max\{T_{M_m}(2,0),T_{M_m}(0,2)\}}{T_{M_m}(1,1)}\longrightarrow0. \] Consequently, the corresponding additive and multiplicative Merino–Welsh inequalities also fail under the two-bases hypothesis. We additionally construct a simple and cosimple matroid on 6060 elements whose ground set is partitioned into two bases and for which TM(2,0)<TM(1,1)T_M(2,0)<T_M(1,1). This disproves the simple-matroid, two-bases-covering formulation of Conjecture 4.2 of Merino, Ibañez, and Rodríguez; its dual disproves the corresponding cosimple-matroid, two-disjoint-bases formulation. The constructions and inequalities are established by explicit rank functions, exact Tutte-polynomial evaluations, and elementary coefficient estimates.

Provenance statement

This work was developed through an interactive mathematical research process involving the human contributor and OpenAI ChatGPT (GPT-6). The human contributor specified the research problem and directed the investigation. The counterexample constructions, mathematical arguments, Tutte-polynomial evaluations, verification code, and manuscript preparation were produced with substantial AI assistance. The numerical counterexamples were checked using exact integer arithmetic, and selected small instances were tested independently using finite-field matrix representations and rank computations. The infinite-family results are supported by explicit mathematical arguments rather than numerical extrapolation. The manuscript is primarily AI-generated. No complete independent human verification, proof-assistant formalization, or external peer review is claimed. Computational consistency checks are not presented as a substitute for independent mathematical certification. The submitting contributor is responsible for accurately reporting the extent of their own mathematical checking and understanding.

Tools used

OpenAI
ChatGPTVersion 6 Pro

References

  1. L. E. Chávez-Lomelí, C. Merino, S. D. Noble, and M. Ramírez-Ibañez, Some inequalities for the Tutte polynomial , European Journal of Combinatorics 32 (2011), 422--433. doi:10.1016/j.ejc.2010.11.005 (https://doi.org/10.1016/j.ejc.2010.11.005). Conjecture 5.8 in arXiv:1004.2639 (https://arxiv.org/abs/1004.2639).arXivDOI
  2. C. Merino, M. Ibañez, and M. G. Rodríguez, A note on some inequalities for the Tutte polynomial of a matroid , Electronic Notes in Discrete Mathematics 34 (2009), 603--607. doi:10.1016/j.endm.2009.07.102 (https://doi.org/10.1016/j.endm.2009.07.102). Conjecture 4.2.DOI
  3. C. Beke, G. K. Csáji, P. Csikvári, and S. Pituk, The Merino--Welsh conjecture is false for matroids , Advances in Mathematics 446 (2024), article 109674. doi:10.1016/j.aim.2024.109674 (https://doi.org/10.1016/j.aim.2024.109674).DOI

Version history

  1. v1Submitted by Jungang ChenInitial depositCurrentOct 21, 2026