Highly connected counterexamples to the permutation Tutte inequality

Jungang Chen

Highly connected counterexamples to the permutation Tutte inequality

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 Conjecture 7.3 of Csikvári, Around the Merino–Welsh conjecture: improving Jackson's inequality, which asserts that

\widetilde T_H(2,0)\widetilde T_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

\widetilde T_H(2,0)

and

\widetilde T_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.

Provenance statement

This work was developed through iterative conversations with OpenAI's ChatGPT under the submitter's direction. The submitter selected the problem and requested counterexamples and strengthenings. AI assistance contributed substantially to the construction, proof development, literature checking, exact-arithmetic verification code, and manuscript preparation. During preparation of this submission, the explicit construction and proof presented here were reconstructed and checked afresh from the available research context. The finite certificate was recomputed using two different exact-arithmetic implementations, and small cases were checked by exhaustive permutation enumeration. These AI-assisted checks do not constitute independent human verification. This statement does not assert that every argument has been independently checked and understood by a human, or that the results have been formally verified or peer reviewed.

Tools used

OpenAI: ChatGPTVersion 6 Pro

References

C. Beke, G. K. Csáji, P. Csikvári, and S. Pituk, Permutation Tutte polynomial , European Journal of Combinatorics 120 (2024), 104003. doi:10.1016/j.ejc.2024.104003 (https://doi.org/10.1016/j.ejc.2024.104003). arXiv:2311.01936 (https://arxiv.org/abs/2311.01936).arXiv DOI
P. Csikvári, Around the Merino--Welsh conjecture: improving Jackson's inequality , European Journal of Combinatorics 137 (2026), 104402. doi:10.1016/j.ejc.2026.104402 (https://doi.org/10.1016/j.ejc.2026.104402). arXiv:2502.19196v2 (https://arxiv.org/abs/2502.19196v2), 19 February 2026. Conjecture 7.3 in v2; Conjecture 7.1 in v1 (https://arxiv.org/abs/2502.19196v1), 26 February 2025.arXiv DOI

Version history

v1Submitted by Jungang ChenInitial depositCurrentOct 21, 2026