math.CO — Combinatorics
Contributed by Jungang Chen
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) 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 M of rank 32 on 64 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 Mm of rank 2m on 4m 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 60 elements whose ground set is partitioned into two bases and for which TM(2,0)<TM(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.
Primarily AI-generated textHuman understanding: some parts