math.CO — Combinatorics
Counterexamples to the Two-Bases Conjecture for the Tutte Polynomial
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 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 of rank on 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 of rank on 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 elements whose ground set is partitioned into two bases and for which . 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.