\documentclass[11pt,a4paper]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage[margin=24mm]{geometry}
\usepackage{microtype}
\usepackage[hidelinks]{hyperref}
\usepackage{enumitem}
\usepackage{booktabs}
\allowdisplaybreaks

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{remark}{Remark}
\newcommand{\rank}{\operatorname{rk}}
\newcommand{\Tr}{\operatorname{Tr}}
\newcommand{\ZZ}{\mathbb Z}
\newcommand{\QQ}{\mathbb Q}
\newcommand{\F}{\mathbb F}

\title{Counterexamples to the Two-bases Conjecture\\for the Tutte Polynomial}
% Hexagon contributors are identified via ORCID. A human contributor may
% add their name here before deposit, but an AI system must not be an author.
\author{}
\date{21 October 2026}

\begin{document}
\maketitle
\vspace{-2.5em}
\begin{abstract}
We disprove the two-bases conjecture of Ch\'avez-Lomel\'i, Merino, Noble,
and Ram\'irez-Iba\~nez (Conjecture~5.8 in \emph{Some inequalities for the
Tutte polynomial}), which asserts that
$\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 $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 family $M_m$ of rank~$2m$ on
$4m$ elements satisfying
$\max\{T_{M_m}(2,0),T_{M_m}(0,2)\}/T_{M_m}(1,1)\to0$.
Thus the associated additive and multiplicative Merino--Welsh inequalities
also fail under the two-bases hypothesis. We additionally construct a
simple and cosimple matroid on $60$ elements with complementary bases and
$T_M(2,0)<T_M(1,1)$, disproving the simple-cover formulation of
Conjecture~4.2 of Merino, Iba\~nez, and Rodr\'iguez; its dual disproves
the cosimple two-disjoint-bases formulation. All computations admit exact
integer certificates, while the infinite-family argument is elementary.
\end{abstract}

\noindent\textbf{2020 Mathematics Subject Classification.}
Primary 05B35; Secondary 05A20.\\
\textbf{Keywords.} Tutte polynomial; two-bases conjecture;
Merino--Welsh conjecture; matroids; counterexamples; self-dual matroids.

\section{The conjectures and the main result}

Throughout, $U_{n,r}$ denotes the uniform matroid on $n$ elements of rank
$r$. For a matroid $M$ with ground set $E$ and rank function $r_M$, write
\begin{equation}
 T_M(x,y)=\sum_{A\subseteq E}(x-1)^{r_M(E)-r_M(A)}
                                     (y-1)^{|A|-r_M(A)}.
 \label{eq:tutte}
\end{equation}
In particular, $T_M(1,1)$ is the number of bases of $M$.

Ch\'avez-Lomel\'i, Merino, Noble, and Ram\'irez-Iba\~nez
\cite[Conjecture~5.8]{chavez2011} conjectured
\begin{equation}
 \max\{T_M(2,0),T_M(0,2)\}\ge T_M(1,1)
 \label{eq:max-conj}
\end{equation}
whenever $M$ has two disjoint bases or $E$ is the union of two bases.
These are \emph{alternative} hypotheses. Our counterexamples satisfy
the stronger, simultaneous requirement that $E$ is a \emph{disjoint}
union of two bases.

\begin{theorem}\label{thm:main}
For each integer $m\ge1$ there is a connected matroid $M_m$ of rank
$2m$ on $4m$ elements with the following properties.
\begin{enumerate}[label=(\roman*),itemsep=1pt]
\item Its ground set is the disjoint union of two bases.
\item It is representable over $\QQ$ and $M_m\cong M_m^*$.
\item If $a_m=T_{M_m}(2,0)=T_{M_m}(0,2)$ and
      $b_m=T_{M_m}(1,1)$, then
\begin{align}
 b_m &= \sum_{k=0}^{m}\binom{m}{k}^{\!2}4^k, \label{eq:bases}\\
 a_m &= 2\sum_{j=0}^{m-1}[z^j](1+z)^{m-1}(3+z)^m.
     \label{eq:endpoint}
\end{align}
\item In particular,
\[
 a_{16}=263656235940864 < 275621102802945=b_{16}.
\]
\item The ratio satisfies
\begin{equation}
 \frac{a_m}{b_m}\le (m+1)\left(\frac89\right)^m\longrightarrow0.
 \label{eq:ratio}
\end{equation}
\end{enumerate}
Hence the maximum, additive, and multiplicative Merino--Welsh inequalities
all fail even for connected matroids whose ground sets are partitioned
into two bases.
\end{theorem}

The unrestricted matroidal forms were already disproved by Beke,
Cs\'aji, Csikv\'ari, and Pituk \cite{beke2024}. The point here is that
the counterexample is \emph{connected}, satisfies both two-bases
hypotheses, and belongs to an explicit family with ratio tending to zero.
We make no claim that $64$ is the global minimum number of elements.

\section{Construction, rank function, and complementary bases}

Begin with $U_{2m,m}$ and partition its ground set into two sets of
size $m$, denoted $P$ and $S$. Double each element of $P$ in parallel,
and double each element of $S$ in series. Denote the resulting pairs by
\[
 P_i=\{p_i^0,p_i^1\},\qquad
 S_i=\{s_i^0,s_i^1\}\qquad(1\le i\le m).
\]
The resulting matroid is $M_m$. We give an explicit rational matrix
representation to remove any ambiguity from the construction.

For $1\le i\le2m$, let
\[
 v_i=(1,i,i^2,\ldots,i^{m-1})^{\mathsf T}\in\QQ^m,
\]
and let $e_1,\dots,e_m$ be the standard basis of $\QQ^m$.
Represent the elements by columns in $\QQ^{2m}$ as follows:
\begin{equation}
 p_i^0,p_i^1:\quad
 \begin{pmatrix}v_i\\0\end{pmatrix},
 \begin{pmatrix}v_i\\0\end{pmatrix};\qquad
 s_i^0,s_i^1:\quad
 \begin{pmatrix}v_{m+i}\\e_i\end{pmatrix},
 \begin{pmatrix}0\\e_i\end{pmatrix}.
 \label{eq:representation}
\end{equation}
The Vandermonde determinant shows that any at most $m$ of the distinct
core vectors $v_1,\ldots,v_{2m}$ are independent.

For $A\subseteq E(M_m)$ define
\begin{align*}
 u(A)&=|\{i:A\cap P_i\ne\varnothing\}|,\\
 t(A)&=|\{i:A\cap S_i\ne\varnothing\}|,\\
 v(A)&=|\{i:S_i\subseteq A\}|.
\end{align*}
The lower coordinates of the matrix in \eqref{eq:representation}
contribute one independent direction for each nonempty $S_i$.
If both columns in $S_i$ are present, their difference supplies the
core direction $v_{m+i}$; the nonempty $P_i$ supply the remaining core
directions. It follows that
\begin{equation}
 r_{M_m}(A)=t(A)+\min\{m,u(A)+v(A)\}.
 \label{eq:rank}
\end{equation}
In particular, $r(M_m)=2m$.

Consider the disjoint sets
\[
 B_0=\{p_i^0,s_i^0:1\le i\le m\},\qquad
 B_1=\{p_i^1,s_i^1:1\le i\le m\}.
\]
For either set $u=t=m$ and $v=0$, so \eqref{eq:rank} gives rank
$2m$. Thus $B_0$ and $B_1$ are bases, and
\begin{equation}
 E(M_m)=B_0\mathbin{\dot\cup}B_1.
 \label{eq:partition}
\end{equation}
More generally, every transversal choosing one member of each of the
$2m$ pairs is a basis.

\begin{lemma}\label{lem:connected-selfdual}
The matroid $M_m$ is connected and isomorphic to its dual.
\end{lemma}
\begin{proof}
Let $d(A)=|\{i:P_i\subseteq A\}|$ be the number of full
parallel pairs. Then
$|A|=u(A)+d(A)+t(A)+v(A)$. By the dual-rank identity
$r_{M_m^*}(A)=|A|-2m+r_{M_m}(E\setminus A)$ and \eqref{eq:rank},
\[
 r_{M_m^*}(A)=u(A)+\min\{m,d(A)+t(A)\}.
\]
This is precisely $r_{M_m}(\phi(A))$, where the permutation $\phi$
interchanges the parallel pair $P_i$ with the series pair $S_i$,
preserving the superscript for each $i$. Hence $M_m\cong M_m^*$.

For connectedness, every $(m+1)$-element circuit of the uniform core
lifts to a circuit of $M_m$ by choosing one representative of each
parallel pair and both elements of each series pair appearing in the
core circuit. Indeed, \eqref{eq:rank} gives nullity one for the lifted
set and shows that deleting any element produces an independent set.
Any two elements from distinct pairs can be placed in the same such
lifted circuit. The two elements of a parallel pair form a circuit;
the two elements of a series pair occur together in a lifted circuit.
Thus every two elements belong to a common circuit and $M_m$ is
connected.
\end{proof}

In particular, $M_m$ has neither loops nor coloops. Self-duality is
an isomorphism, not an assertion that each basis has a basis as its
literal complement.

\section{Exact Tutte evaluations}

\subsection{Counting bases}

In a basis, each parallel pair contributes at most one element. By
\eqref{eq:rank}, every series pair must contribute at least one.
Suppose exactly $k$ parallel pairs contribute one element each.
The basis must contain both elements from precisely $m-k$ series pairs,
and one element from each of the remaining $k$ series pairs.
There are
\[
 \binom{m}{k}2^k\binom{m}{m-k}2^k
 =\binom{m}{k}^2 4^k
\]
choices. Summing proves \eqref{eq:bases}; equivalently,
\begin{equation}
 b_m=[z^m](1+2z)^m(2+z)^m
     =[z^m](2+5z+2z^2)^m.
 \label{eq:base-genfn}
\end{equation}

\subsection{The two endpoints}

Set
\[
 F_m(z)=(1+z)^m(3+z)^m=\sum_{j=0}^{2m}f_{m,j}z^j.
\]
At $(2,0)$, the rank expansion \eqref{eq:tutte} is the signed sum
$\sum_{A\subseteq E}(-1)^{|A|-r(A)}$.
Using $d(A)$ as in Lemma~\ref{lem:connected-selfdual}, we have
\[
 |A|-r(A)=d(A)+\max\{0,u(A)+v(A)-m\}.
\]
For each fixed nonempty parallel pair, the two singleton choices
contribute weight~$2$ and the full-pair choice weight~$-1$, for a
total weight~$1$. For each series pair not selected in full, the
empty choice and the two singleton choices contribute total weight~$3$.
Grouping by $j=u(A)+v(A)$ gives
\begin{equation}
 a_m=\sum_{j\le m}f_{m,j}
        +\sum_{j>m}(-1)^{j-m}f_{m,j}.
 \label{eq:a-signed}
\end{equation}
Since $F_m(-1)=0$, this also equals
\begin{align}
 a_m
 &=2\sum_{\substack{0\le j<m\\j\equiv m-1\,\mathrm{(mod\,2)}}}f_{m,j}
 =2[z^{m-1}]\frac{F_m(z)}{1-z^2} \notag\\
 &=2[z^{m-1}]\frac{(1+z)^{m-1}(3+z)^m}{1-z}
 =2\sum_{j=0}^{m-1}[z^j](1+z)^{m-1}(3+z)^m.
 \label{eq:a-positive}
\end{align}
This is \eqref{eq:endpoint}. Tutte duality and
Lemma~\ref{lem:connected-selfdual} give $T_{M_m}(0,2)=a_m$.
For an additional independent check, direct signed-rank enumeration
yields
\begin{equation}
 T_{M_m}(0,2)
 =\sum_{j=0}^{2m}(-1)^{m-\min(m,j)}
       [z^j](1+4z+3z^2)^m.
 \label{eq:other-endpoint}
\end{equation}

\subsection{A 64-element counterexample}

For $m=16$, the integer evaluations from
\eqref{eq:bases} and \eqref{eq:endpoint} are
\begin{align*}
 b_{16}&=\sum_{k=0}^{16}\binom{16}{k}^2 4^k
         =275\,621\,102\,802\,945,\\
 a_{16}&=2\sum_{j=0}^{15}[z^j](1+z)^{15}(3+z)^{16}
         =263\,656\,235\,940\,864.
\end{align*}
The exact positive gap is
\begin{equation}
 b_{16}-a_{16}=11\,964\,866\,862\,081>0.
 \label{eq:gap}
\end{equation}
Since the two endpoints coincide, putting $M=M_{16}$ gives
\begin{align*}
 \max\{T_M(2,0),T_M(0,2)\}&<T_M(1,1),\\
 T_M(2,0)+T_M(0,2)&<2T_M(1,1),\\
 T_M(2,0)T_M(0,2)&<T_M(1,1)^2.
\end{align*}
The normalized maximum ratio is approximately $0.95659$; the
multiplicative ratio is approximately $0.91506$. Within this
one-parameter family, exact evaluation shows that $m=16$ is the first
counterexample. This is not a global minimality assertion.

\section{Infinite families and quantitative failure}

By \eqref{eq:a-positive}, all terms are nonnegative and
\[
 0<a_m<2(1+1)^{m-1}(3+1)^m=8^m.
\]
Applying Cauchy--Schwarz to $c_k=\binom mk2^k$, we get
\[
 b_m=\sum_{k=0}^m c_k^2
 \ge\frac{(\sum_{k=0}^m c_k)^2}{m+1}
 =\frac{9^m}{m+1}.
\]
Consequently,
\begin{equation}
 \frac{\max\{T_{M_m}(2,0),T_{M_m}(0,2)\}}{T_{M_m}(1,1)}
 =\frac{a_m}{b_m}
 \le(m+1)\left(\frac89\right)^m\xrightarrow[m\to\infty]{}0.
 \label{eq:asymptotic}
\end{equation}
In particular, the bound itself certifies a counterexample for every
$m\ge29$: one checks $9^{29}>30\cdot8^{29}$, and the quantity
$9^m/((m+1)8^m)$ increases for $m\ge8$. The separate exact calculation
above establishes the smaller counterexample $m=16$.

\section{The earlier one-sided conjecture}

Merino, Iba\~nez, and Rodr\'iguez \cite[Conjecture~4.2]{merino2009}
conjectured that a \emph{cosimple} matroid with two disjoint bases
satisfies $T_M(0,2)\ge T_M(1,1)$; dually, a \emph{simple} matroid
whose ground set is the union of two bases should satisfy
$T_M(2,0)\ge T_M(1,1)$. Our $M_m$ has both parallel and series
pairs, so we construct a separate example for these stronger
simplicity hypotheses.

\begin{proposition}\label{prop:one-sided}
Let $C_3=U_{3,2}$ and define
\[
 L=\Tr_{30}\!\bigl(C_3^{\oplus20}\bigr),
\]
where $\Tr_{30}$ means truncation to rank~$30$. Then $L$ is a
$60$-element simple and cosimple matroid with its ground set partitioned
into two bases, and
\begin{equation}
 T_L(2,0)=3\,612\,141\,626\,425\,344
 <4\,143\,252\,234\,043\,404=T_L(1,1).
 \label{eq:triangle-gap}
\end{equation}
Thus $L$ disproves the simple-cover formulation and $L^*$
disproves the cosimple-packing formulation of
\cite[Conjecture~4.2]{merino2009}.
\end{proposition}

\begin{proof}
Write $E=\dot\bigcup_{i=1}^{20}E_i$, where each $E_i$ is a
three-element circuit of the direct sum. The rank function is
\[
 r_L(A)=\min\left\{30,\sum_{i=1}^{20}\min\{|A\cap E_i|,2\}\right\}.
\]
Choose two elements from each of the first ten blocks and one element
from each remaining block. This is an independent $30$-element set;
its complement has the same property. Hence the two sets are
complementary bases.

Every two-element set is independent, so $L$ is simple. Removing any
two elements reduces the rank of $C_3^{\oplus20}$ from $40$ to at
least $38$, and the truncation still has rank $30$. Therefore $L$
has no cocircuit of size one or two and is cosimple.

The independent-set enumerator of a single triangle is
$1+3z+3z^2$, so
\begin{equation}
 T_L(1,1)=[z^{30}](1+3z+3z^2)^{20}
           =4\,143\,252\,234\,043\,404.
 \label{eq:triangle-bases}
\end{equation}
Set $q_j=[z^j](1+3z+2z^2)^{20}$. For a triangle, the
rank-grouped signed-nullity weights are $1$, $3z$, and $2z^2$;
the final coefficient is $3-1$, from the three independent pairs
and the dependent triple. The truncation rank formula gives
\[
 T_L(2,0)=\sum_{j\le30}q_j
          +\sum_{j>30}(-1)^{j-30}q_j
       =2\sum_{\substack{0\le j<30\\j\text{ odd}}}q_j.
\]
The final identity uses $(1-3+2)^{20}=0$. It yields the exact value
in \eqref{eq:triangle-gap}. The weaker bound suffices:
\[
 T_L(2,0)\le\sum_{j=0}^{40}q_j
 =6^{20}=3\,656\,158\,440\,062\,976
 <T_L(1,1).
\]
\end{proof}

It is important not to confuse the two results: $L$ itself is
\emph{not} a maximum-form counterexample, since
\[
 T_L(0,2)=243\,284\,737\,468\,137\,472>T_L(1,1).
\]
The $64$-element $M_{16}$ is the maximum-form counterexample.

The one-sided examples can also be made into an infinite family. For
$t\ge1$, put $L_t=\Tr_{30t}(C_3^{\oplus20t})$. Grouping blocks
into $t$ groups of twenty gives $T_{L_t}(1,1)\ge T_L(1,1)^t$,
while the same coefficient argument gives $T_{L_t}(2,0)\le6^{20t}$.
Thus
\[
 \frac{T_{L_t}(2,0)}{T_{L_t}(1,1)}
 \le\left(\frac{6^{20}}{4\,143\,252\,234\,043\,404}\right)^t
 \longrightarrow0.
\]
Each $L_t$ remains simple and cosimple and admits complementary bases.

\section{Scope and verification}

The main family is not graphic. Indeed, deleting one member of each
parallel pair and contracting one member of each series pair recovers
$U_{2m,m}$. For $m\ge2$, the latter has a $U_{4,2}$ minor.
Therefore $M_m$ is not binary, and the construction does not address
the graphic Merino--Welsh conjecture.

The accompanying standalone Python script uses only the standard
library and checks all numerical claims by exact integer arithmetic.
For $m=16$, it computes the two endpoints and the number of bases by
an independent rank-grouped sum over the six possible states of each
parallel/series pair, as well as by \eqref{eq:bases}--\eqref{eq:endpoint}.
It verifies the $m=1,2,3$ cases using matrix rank over $\F_{101}$,
checks the complementary bases for $m=16$, and independently enumerates
rank/size states for the $60$-element truncation. These checks are
not substitutes for independent review of the arguments given above.

\begin{thebibliography}{9}
\bibitem{chavez2011}
L.~E. Ch\'avez-Lomel\'i, C.~Merino, S.~D. Noble, and M.~Ram\'irez-Iba\~nez,
\emph{Some inequalities for the Tutte polynomial},
European Journal of Combinatorics \textbf{32} (2011), 422--433.
\href{https://doi.org/10.1016/j.ejc.2010.11.005}{doi:10.1016/j.ejc.2010.11.005}.
Conjecture~5.8 in \href{https://arxiv.org/abs/1004.2639}{arXiv:1004.2639}.

\bibitem{merino2009}
C.~Merino, M.~Iba\~nez, and M.~G. Rodr\'iguez,
\emph{A note on some inequalities for the Tutte polynomial of a matroid},
Electronic Notes in Discrete Mathematics \textbf{34} (2009), 603--607.
\href{https://doi.org/10.1016/j.endm.2009.07.102}{doi:10.1016/j.endm.2009.07.102}.
Conjecture~4.2.

\bibitem{beke2024}
C.~Beke, G.~K. Cs\'aji, P.~Csikv\'ari, and S.~Pituk,
\emph{The Merino--Welsh conjecture is false for matroids},
Advances in Mathematics \textbf{446} (2024), article 109674.
\href{https://doi.org/10.1016/j.aim.2024.109674}{doi:10.1016/j.aim.2024.109674}.
\end{thebibliography}
\end{document}