\documentclass[11pt]{article}
\usepackage[a4paper,margin=27mm]{geometry}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb,amsthm,mathtools,microtype}
\usepackage{booktabs}
\usepackage[hidelinks]{hyperref}
\usepackage{enumitem}
\setlist{topsep=4pt,itemsep=2pt}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\PT}{\widetilde T}
\newcommand{\E}{\mathbb E}
\newcommand{\ind}{\mathbf 1}
\DeclareMathOperator{\lcm}{lcm}
\title{Highly connected counterexamples to the\newline permutation Tutte inequality}
% Insert the human contributor name(s) here before public submission, if desired.
% The contributor and ORCID fields must also be completed in Hexagon.
\author{}
\date{21 October 2026}

\begin{document}
\maketitle
\begin{abstract}
We disprove Conjecture~7.3 of Csikv\'ari, \emph{Around the Merino--Welsh
conjecture: improving Jackson's inequality}, which asserts that
$\PT_H(2,0)\PT_H(0,2)\ge1$ for every bipartite graph $H$ of minimum
degree at least two. For each integer $k\ge2$, we construct an explicit
sequence of finite simple balanced bipartite graphs whose minimum degree
and vertex connectivity are both exactly $k$. The graphs admit
automorphisms interchanging their two vertex classes, and both
$\PT_H(2,0)$ and $\PT_H(0,2)$ tend to zero along the sequence.
Consequently, no fixed minimum-degree or connectivity threshold ensures
the inequality, and even the corresponding maximum and additive
inequalities fail in these classes. The construction consists of a
complete bipartite core with additional vertices of degree $k$ attached
to disjoint $k$-element subsets on each side. A one-variable integral
bound gives explicit exponential decay for each fixed $k$ and a
sufficient size threshold. We also give a 1000-vertex, 2-connected example whose two axis
values are each less than $7/10$, certified by exact rational arithmetic.
These are statements about the permutation Tutte polynomial; a failure
of a local permutation inequality alone does not give a counterexample
to a graph or matroid Merino--Welsh inequality.
\end{abstract}

\noindent\textbf{2020 Mathematics Subject Classification.}
Primary 05C31; Secondary 05A20, 05C07, 05C40.

\smallskip
\noindent\textbf{Keywords.} Permutation Tutte polynomial; bipartite graph;
minimum degree; vertex connectivity; combinatorial inequality.

\section{Introduction}

Let $H=(L,R;E)$ be a finite bipartite graph with a specified bipartition.
For a bijection $\pi:V(H)\to\{1,\ldots,|V(H)|\}$, a vertex is
\emph{active} if its label is greater than the labels of all its
neighbors. Let $a_L(\pi)$ and $a_R(\pi)$ count the active vertices in
the two parts. Beke, Cs\'aji, Csikv\'ari, and Pituk~\cite{PT} defined
the permutation Tutte polynomial by
\begin{equation}\label{eq:def}
 \PT_H(x,y)=\frac{1}{|V(H)|!}\sum_{\pi}
 x^{a_L(\pi)}y^{a_R(\pi)}.
\end{equation}
We use $0^0=1$. In particular, $\PT_H(1,1)=1$.

Csikv\'ari~\cite[Conjecture~7.3 in arXiv v2]{Cs} conjectured that
\begin{equation}\label{eq:conjecture}
 \PT_H(2,0)\PT_H(0,2)\ge1
 \qquad\text{whenever }\delta(H)\ge2.
\end{equation}
The same conjecture appeared as Conjecture~7.1 in the first arXiv
version of that paper. The version distinction matters: Conjecture~7.1
in v2 concerns a different, endpoint inequality for matroids.

We give direct counterexamples to~\eqref{eq:conjecture}, with a stronger
failure under prescribed minimum degree and vertex connectivity.

\begin{theorem}\label{thm:main}
For every integer $k\ge2$, there is an explicit sequence
$(H_{k,n})_{n\ge1}$ of finite simple balanced bipartite graphs such that
\[
 \delta(H_{k,n})=\kappa(H_{k,n})=k,
 \qquad
 \PT_{H_{k,n}}(2,0)=\PT_{H_{k,n}}(0,2)\longrightarrow0.
\]
The graphs have automorphisms interchanging their bipartition classes,
and are pairwise nonisomorphic as $n$ varies. Every
\[
 n\ge4(k+1)^2(2k^2+k+4)
\]
gives a strict counterexample to~\eqref{eq:conjecture}.
\end{theorem}

Here $\kappa$ denotes vertex connectivity. By the usual inequalities
$\kappa\le\lambda\le\delta$, the edge connectivity of these graphs is
also exactly $k$.

The proof conditions on the largest label in one side of a complete
bipartite core. The resulting upper bound is a one-variable integral
whose exponential factor is uniformly smaller than one. This argument
also supplies a finite example, without any claim of minimality.

\begin{proposition}\label{prop:finite-intro}
There is a simple balanced bipartite graph $H$ with 1000 vertices,
160400 edges, and $\delta(H)=\kappa(H)=2$, for which
\[
 \PT_H(2,0)=\PT_H(0,2)<\frac7{10},
 \qquad
 \PT_H(2,0)\PT_H(0,2)<\frac{49}{100}.
\]
\end{proposition}

The general existence theorem is proved by inequalities valid for all
$k$; it does not rely on a search or numerical integration. The rational
calculation in Section~\ref{sec:finite} gives a smaller concrete witness.

\section{The graph construction}

\begin{definition}\label{def:graph}
For integers $k\ge2$, $q\ge0$, and $n\ge1$, put $m=(k+q)n$.
Start with a complete bipartite core $K_{m,m}$, with parts $A$ and $B$.
Choose pairwise disjoint sets $A_1,\ldots,A_n\subseteq A$ and
$B_1,\ldots,B_n\subseteq B$, each of size $k$. For each $i$, add a
vertex $\alpha_i$ adjacent precisely to $A_i$, and a vertex $\beta_i$
adjacent precisely to $B_i$. There are no other vertices or edges.
Denote the resulting graph by $H(k,q,n)$. Its bipartition is
\[
 L=A\mathbin{\dot\cup}\{\beta_1,\ldots,\beta_n\},\qquad
 R=B\mathbin{\dot\cup}\{\alpha_1,\ldots,\alpha_n\}.
\]
The $qn$ unused core vertices on each side are called bare core vertices.
\end{definition}

\begin{lemma}\label{lem:structure}
The graph $H=H(k,q,n)$ is simple and balanced, with
\[
 |V(H)|=2(k+q+1)n,\qquad |E(H)|=(k+q)^2n^2+2kn,
 \qquad\delta(H)=\kappa(H)=k.
\]
There is an automorphism interchanging $L$ and $R$. Consequently
$\PT_H(x,y)=\PT_H(y,x)$.
\end{lemma}

\begin{proof}
The new vertices have degree $k$. The core vertices in the specified
blocks have degree $m+1$, and any bare core vertices have degree $m$.
Since $m\ge k$, the minimum degree is $k$. The order and size follow
directly from the construction.

Delete any set of fewer than $k$ vertices. At least one vertex remains
on each side of the core, so the remaining core is connected. Every
remaining new vertex retains a core neighbor. The whole remaining graph
is therefore connected, proving $\kappa(H)\ge k$. Conversely, deleting
the $k$ neighbors of a new vertex isolates that vertex, with other
vertices remaining, so $\kappa(H)\le k$.

Match $A_i$ with $B_i$ for each $i$, match the two bare core sets, and
interchange $\alpha_i$ and $\beta_i$. These correspondences give an
automorphism swapping the two parts. Applying it to the labelings in
\eqref{eq:def} proves the polynomial symmetry.
\end{proof}

Write
\begin{equation}\label{eq:X}
 X_{k,q,n}=\PT_{H(k,q,n)}(2,0)=\PT_{H(k,q,n)}(0,2).
\end{equation}

\section{A one-variable integral bound}

Assign independent uniform labels in $[0,1]$ to every vertex. Almost
surely these labels are distinct, and all strict total orders are equally
likely. Thus~\eqref{eq:def} is equivalently
\[
 \PT_H(x,y)=\E[x^{a_L}y^{a_R}],\qquad
 \PT_H(2,0)=\E[2^{a_L}\ind_{\{a_R=0\}}].
\]
For fixed $k,q$, define on $[0,1]$
\begin{align}
 F_k(t)&=\frac{(2+kt)(2-t)^k-2}{k+1},\label{eq:F}\\
 U(t)&=(2-t)^qF_k(t),\label{eq:U}\\
 V(t)&=t^{k+q}\left(2-\frac{kt}{k+1}\right),\label{eq:V}\\
 Q(t)&=U(t)V(t).\label{eq:Q}
\end{align}

\begin{lemma}\label{lem:integral}
For every $k\ge2$, $q\ge0$, and $n\ge1$,
\begin{equation}\label{eq:I}
 0<X_{k,q,n}\le I_{k,q,n}:=
 \int_0^1 U(t)^n\,d(V(t)^n)
 =n\int_0^1 Q(t)^{n-1}U(t)V'(t)\,dt.
\end{equation}
In particular, $I_{k,q,n}$ is an explicitly computable rational number.
\end{lemma}

\begin{proof}
In the expectation defining $X_{k,q,n}$, retain the condition that all
$\alpha_i$ are inactive, and omit the condition that all vertices of
$B$ are inactive. Omitting this condition can only increase the
nonnegative expectation. Condition on the labels of $B$, and let $t$
be their maximum.

A bare vertex of $A$ has activity weight $2$ when its label exceeds $t$,
and weight $1$ otherwise. Its integrated weight is $2-t$.

Consider a block $A_i$ and its neighbor $\alpha_i$, whose label is $z$.
The inactivity of $\alpha_i$ requires that some label in $A_i$ exceed
$z$. A vertex in $A_i$ is active precisely when its label exceeds both
$t$ and $z$. If $z\le t$, the integral over the $k$ labels in $A_i$ is
$(2-t)^k-z^k$; if $z>t$, it is $(2-z)^k-z^k$. Integration over $z$
therefore gives
\begin{align*}
 &\int_0^t\bigl((2-t)^k-z^k\bigr)\,dz
 +\int_t^1\bigl((2-z)^k-z^k\bigr)\,dz\\
 &\hspace{35mm}=\frac{(2+kt)(2-t)^k-2}{k+1}=F_k(t).
\end{align*}
The disjoint blocks and bare vertices of $A$ hence contribute $U(t)^n$.

For a block $B_i$ with maximum label $s$, the expected activity weight
of $\beta_i$ is $s+2(1-s)=2-s$. Its integrated weight over labels in
$[0,t]^k$ is
\[
 \int_0^t k s^{k-1}(2-s)\,ds
 =t^k\left(2-\frac{kt}{k+1}\right).
\]
Thus the weighted measure of all labels of $B$ being at most $t$ is
\[
 t^{qn}\left[t^k\left(2-\frac{kt}{k+1}\right)\right]^n=V(t)^n.
\]
Integrating $U(t)^n$ against this weighted maximum-label distribution
proves the first upper bound. Notice that this is a finite positive
measure, not necessarily a probability measure; no normalization is
omitted. Differentiating $V^n$ gives the last expression in~\eqref{eq:I}.
Positivity of $X_{k,q,n}$ follows, for example, from the positive-probability
event on which every label in $L$ exceeds every label in $R$.
Finally, the integrand is a polynomial with rational coefficients.
\end{proof}

\begin{lemma}\label{lem:prefactor}
Let $\rho=\max_{0\le t\le1}Q(t)$. Then
\begin{equation}\label{eq:prefactor}
 X_{k,q,n}\le n C_{k,q}\rho^{n-1},\qquad
 C_{k,q}=2^q\frac{(2^{k+1}-2)(k+2)}{(k+1)^2}
 <2^{q+k+2}.
\end{equation}
\end{lemma}

\begin{proof}
We have $F_k'(t)=-kt(2-t)^{k-1}\le0$, so $U$ is nonnegative and
nonincreasing. Also $V(0)=0$ and $V'\ge0$, as is clear either from
its integral interpretation or from~\eqref{eq:V}. Consequently
\[
 \int_0^1 U(t)V'(t)\,dt
 \le U(0)V(1)
 =2^q\frac{(2^{k+1}-2)(k+2)}{(k+1)^2}.
\]
Combine this with~\eqref{eq:I}. The final rough bound follows from
$2^{k+1}-2<2^{k+1}$ and $(k+2)/(k+1)^2<2$.
\end{proof}

\section{Uniform decay for every prescribed minimum degree}

\begin{lemma}\label{lem:gap}
Fix $k\ge2$ and take $q=2k^2+1$. For every $t\in[0,1]$,
\begin{equation}\label{eq:gap}
 Q(t)\le \exp\left(-\frac{1}{2(k+1)^2}\right)<1.
\end{equation}
\end{lemma}

\begin{proof}
Put $s=1-t$ and $D=(k+1)^2$. Directly from~\eqref{eq:F}--\eqref{eq:Q},
\begin{align*}
 Q(t)=\frac{(1-s^2)^q}{D}\Bigl(&[(k+2)^2-k^2s^2](1-s^2)^k\\
 &-2(k+2+ks)(1-s)^k\Bigr).
\end{align*}
The coefficient $(k+2)^2-k^2s^2$ is positive. Apply
$(1-s^2)^k\le1$ and Bernoulli's inequality $(1-s)^k\ge1-ks$ to obtain
\begin{equation}\label{eq:Q-upper}
 Q(t)\le(1-s^2)^q
 \left(1-\frac1D+\frac{2k}{k+1}s+\frac{k^2}{D}s^2\right).
\end{equation}
For $0<t\le1$, both $Q(t)$ and the parenthesis are positive. Using
$\log(1-s^2)\le-s^2$ and $\log z\le z-1$ yields
\[
 \log Q(t)\le-\frac1D+\frac{2k}{k+1}s
 -\left(q-\frac{k^2}{D}\right)s^2.
\]
Since $q-k^2/D>2k^2$, completing the square gives
\[
 \log Q(t)\le-\frac1D+
 \frac{k^2}{D(q-k^2/D)}
 <-\frac1{2D}.
\]
At $t=0$ we have $Q(0)=0$, so~\eqref{eq:gap} holds on the closed interval.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:main}]
Take $q=2k^2+1$ and $H_{k,n}=H(k,q,n)$. Lemma~\ref{lem:structure}
proves all structural assertions. Lemmas~\ref{lem:prefactor}
and~\ref{lem:gap} give
\begin{equation}\label{eq:decay}
 0<X_{k,q,n}\le nC_{k,q}
 \exp\left(-\frac{n-1}{2(k+1)^2}\right)\longrightarrow0.
\end{equation}
The vertex count is strictly increasing in $n$, proving that the graphs
are pairwise nonisomorphic.

For the stated sufficient threshold, set $D=(k+1)^2$, $L=q+k+3$,
and $n_0=4DL$. Then $D\le L$ and $L\ge14$. The elementary inequality
$4L^2\le2^L$ holds for integers $L\ge8$: it is an equality at $L=8$,
and the ratio $2^L/(4L^2)$ increases thereafter. Hence
\[
 n_0\le4L^2\le2^L,\qquad C_{k,q}<2^{L-1}.
\]
As $(n_0-1)/(2D)=2L-1/(2D)>2L-1$, the upper bound in~\eqref{eq:decay}
at $n=n_0$ is strictly smaller than
\[
 2^{2L-1}e^{-(2L-1)}<1.
\]
The function $n e^{-(n-1)/(2D)}$ is nonincreasing for $n\ge2D$.
Thus every integer $n\ge n_0$ has $X_{k,q,n}<1$, as required.
\end{proof}

\begin{corollary}\label{cor:strengthenings}
For every fixed integer $k\ge2$,
\[
 \inf_H\PT_H(2,0)\PT_H(0,2)=0,
\]
where the infimum is over finite simple balanced bipartite graphs with
$\delta(H)=\kappa(H)=k$. The same infimum is zero for
$\max\{\PT_H(2,0),\PT_H(0,2)\}$ and for
$(\PT_H(2,0)+\PT_H(0,2))/2$. These statements remain true when the
graphs are required to have an automorphism interchanging their parts.
\end{corollary}

\begin{proof}
All three quantities are nonnegative, and the sequence in
Theorem~\ref{thm:main} makes each tend to zero.
\end{proof}

\section{A finite exact certificate}\label{sec:finite}

Take $H=H(2,2,100)$. Its core is $K_{400,400}$; on each side, partition
200 core vertices into 100 pairs and attach one vertex on the opposite
side to each pair. The remaining 200 core vertices on each side are
bare. Lemma~\ref{lem:structure} gives
\[
 |V(H)|=1000,\quad |E(H)|=160400,\quad\delta(H)=\kappa(H)=2.
\]
The choice $q=2$ is used only for this finite witness; the uniform
choice in Theorem~\ref{thm:main} is $q=2k^2+1$.

Here $U=u/3$ and $V=v/3$, where
\begin{align*}
 u(t)&=24-24t-18t^2+32t^3-14t^4+2t^5,\\
 v(t)&=6t^4-2t^5.
\end{align*}
Therefore the rational upper bound in~\eqref{eq:I} is
\begin{equation}\label{eq:finite-certificate}
 I_{2,2,100}=\frac{100}{9^{100}}
 \int_0^1 (u(t)v(t))^{99}u(t)v'(t)\,dt
 <\frac7{10}.
\end{equation}
We describe the exact finite arithmetic certifying this strict
comparison. Write
\[
 (uv)^{99}uv'=\sum_{j=0}^{999}c_jt^j,\qquad
 \Lambda=\lcm(1,2,\ldots,1000).
\]
All coefficients $c_j$ are integers. Set
\begin{equation}\label{eq:integer-certificate}
 N=100\sum_{j=0}^{999}c_j\frac{\Lambda}{j+1},\qquad
 D_0=9^{100}\Lambda.
\end{equation}
Then $I_{2,2,100}=N/D_0$, and the calculation gives $N>0$ and
$7D_0-10N>0$. To make the arithmetic reproducible without special
software, let $a=(24,-24,-18,32,-14,2)$ and
$b=(0,0,0,0,6,-2)$. Compute polynomial products by
\[
 (f*g)_j=\sum_{i=0}^j f_i g_{j-i},
\]
starting with the coefficient array $(1)$, multiplying by $a*b$ a
total of 99 times, and finally multiplying by $a$ and by
$(b_1,2b_2,\ldots,5b_5)$. Formula~\eqref{eq:integer-certificate}
then involves only integer arithmetic. The complete positive integer
$7D_0-10N$ is recorded in Appendix~\ref{app:gap}.

The resulting rational number has reduced numerator and denominator
of 519 digits each. For orientation only,
\[
 I_{2,2,100}=0.67702186967725368440568057708376844\ldots.
\]
This decimal is the \emph{upper bound}, not an asserted exact value
of $\PT_H(2,0)$. A second calculation, expanding $u^{100}$ and
differentiating the binomial expansion
$v^{100}=2^{100}t^{400}(3-t)^{100}$, gives the same reduced rational
number. Both comparisons with $7/10$ use exact arithmetic.

By~\eqref{eq:I} and symmetry, both actual axis values are less than
$7/10$, proving Proposition~\ref{prop:finite-intro}. Exhaustive
permutation enumeration on four small graphs from the construction
(including its $k=1$ instance $P_4$)
was also used as a consistency check of the activity convention and
the integral upper bound. Neither that check nor the finite
calculation is needed for the general existence proof.

\section{Scope and provenance}

The theorem disproves Csikv\'ari's minimum-degree-two permutation
Tutte conjecture and rules out any repair based solely on imposing a
fixed larger minimum degree or vertex connectivity. The maximum and
additive failures in Corollary~\ref{cor:strengthenings} are consequences
of the same two axis values tending to zero; we do not attribute these
variants as separately numbered conjectures in~\cite{Cs}.

The graph has core degrees growing with $n$ and additional vertices of
fixed degree $k$. This distinction is compatible with positive results
that impose an upper degree bound as well as a lower one, such as
\cite[Lemma~6.1]{Cs}.

The permutation Tutte polynomial is different from the ordinary Tutte
polynomial. The local-to-global transfer principle of~\cite{PT} gives
a sufficient condition, applied to every local basis exchange graph,
for a matroid inequality. Failure of that local sufficient condition
does not reverse the implication. Thus the present graph construction
alone does not disprove the graphical or matroid Merino--Welsh
inequalities.

\paragraph{AI assistance and verification.}
This manuscript was developed through iterative interactions with
OpenAI's ChatGPT under the submitter's direction. AI assistance
contributed to the construction, proof development, literature checks,
exact-arithmetic verification, and writing. During preparation of this
version, the explicit construction and proof were reconstructed and
checked afresh from the available research context. The finite
certificate was recomputed with two exact-arithmetic implementations.
These checks do not constitute independent human verification, and
this statement does not assert that every argument has been
independently checked and understood by a human. No formal proof-assistant
verification or peer review is claimed.

\appendix
\section{The finite integer gap}\label{app:gap}

For $N,D_0$ as defined in~\eqref{eq:integer-certificate}, the positive
integer $7D_0-10N$ is the following decimal integer, with line breaks
inserted for readability:
\input{integer_gap.tex}

\begin{thebibliography}{9}

\bibitem{PT}
C.~Beke, G.~K. Cs\'aji, P.~Csikv\'ari, and S.~Pituk,
\emph{Permutation Tutte polynomial},
European Journal of Combinatorics \textbf{120} (2024), 104003.
\href{https://doi.org/10.1016/j.ejc.2024.104003}{doi:10.1016/j.ejc.2024.104003}.
\href{https://arxiv.org/abs/2311.01936}{arXiv:2311.01936}.

\bibitem{Cs}
P.~Csikv\'ari,
\emph{Around the Merino--Welsh conjecture: improving Jackson's inequality},
European Journal of Combinatorics \textbf{137} (2026), 104402.
\href{https://doi.org/10.1016/j.ejc.2026.104402}{doi:10.1016/j.ejc.2026.104402}.
\href{https://arxiv.org/abs/2502.19196v2}{arXiv:2502.19196v2},
19 February 2026. Conjecture~7.3 in v2; Conjecture~7.1 in
\href{https://arxiv.org/abs/2502.19196v1}{v1}, 26 February 2025.

\end{thebibliography}
\end{document}