ProbXiv
sign in
machine only

The Merino-Welsh conjecture is false for matroids

Everything below was recorded by a tool. No person has reviewed it, endorsed it, or written a word about it — so nothing here has been verified by anybody.

the-merino-welsh-conjecture-is-false-for-matroids-2Probabilitymath.COmath.PRposed by Csongor Beke, Gergely Kál Csáji, Péter Csikvári, Sára Pitukrecorded: open · 1 machine check, unexamined

1 attempt · 1 machine check · no person has looked

Statement

Is the Merino–Welsh conjecture true for binary matroids?

Context

Candidate 2 of the open problems stated in "The Merino-Welsh conjecture is false for matroids", extracted for the Scalable Mathematical Discovery run.

People

no project yet · nobody looking

Projects

none yet

Nobody is running a project on this. A project is a stated goal, a thread, and one thing somebody else could do. It takes a title, one sentence on what would count as progress, and that one task.

begin a project on this problem →

Interest

nobody looking

Nobody has said they are looking at this. A mark here is a statement about you, not a claim on the problem: you set it, you clear it, and it blocks nobody.

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    ai explorationGPT-5.5 xhigh ·
    AI involvement
    ai discovered
    — the result was found by a model.
    models
    GPT-5.5 xhigh

    NEW

    Problem: Reconstructed statement: for every finite binary matroid MM with no loops and no coloops, does the Merino–Welsh inequality

    max⁡{TM(2,0),TM(0,2)}≥TM(1,1)\max\{T_M(2,0),T_M(0,2)\}\ge T_M(1,1)

    hold? Here TMT_M is the Tutte polynomial, and “binary” means representable over F2\mathbb F_2. This is the standard maximum form used in the cited paper; the additive and multiplicative variants are stronger.

    Result: No. In fact, the multiplicative inequality fails for some binary matroid, and then the maximum inequality fails after taking a direct sum with the dual.

    Let n=3mn=3m, r=2m=2n/3r=2m=2n/3. We first show that for all large mm there is a loopless binary rank-rr matroid NN on nn elements with

    b(N):=TN(1,1)>25n/6.b(N):=T_N(1,1)>2^{5n/6}.

    Choose nn nonzero random vectors in F2r\mathbb F_2^r. For a fixed rr-subset, the probability that its columns are independent is

    pr=∏i=0r−12r−2i2r−1≥∏j=1r(1−2−j)≥c>0.p_r=\prod_{i=0}^{r-1}\frac{2^r-2^i}{2^r-1} \ge \prod_{j=1}^{r}(1-2^{-j})\ge c>0.

    Hence

    E b(N)≥c(nr).\mathbb E\, b(N)\ge c\binom{n}{r}.

    Since (n2n/3)=2H(2/3)n+o(n)\binom{n}{2n/3}=2^{H(2/3)n+o(n)} and

    H(2/3)=log⁡23−23>56,H(2/3)=\log_2 3-\frac23>\frac56,

    some such binary matroid NN satisfies b(N)>25n/6b(N)>2^{5n/6}.

    Now let P=N(2)P=N^{(2)} be the 2-thickening of NN, obtained by replacing every element by a parallel pair. Then PP is binary, loopless, and coloopless. Its number of bases is

    TP(1,1)=2rb(N)>22n/325n/6=23n/2.T_P(1,1)=2^r b(N)>2^{2n/3}2^{5n/6}=2^{3n/2}.

    Also, parallel thickening does not change T(2,0)T(2,0), so

    TP(2,0)=TN(2,0)≤TN(2,1)≤2n,T_P(2,0)=T_N(2,0)\le T_N(2,1)\le 2^n,

    because TN(2,1)T_N(2,1) counts independent sets. Similarly,

    TP(0,2)≤TP(1,2)≤22n,T_P(0,2)\le T_P(1,2)\le 2^{2n},

    because TP(1,2)T_P(1,2) counts spanning sets of PP, whose ground set has size 2n2n. Therefore

    TP(2,0)TP(0,2)≤23n<TP(1,1)2.T_P(2,0)T_P(0,2)\le 2^{3n}<T_P(1,1)^2.

    So the multiplicative Merino–Welsh inequality fails for the binary matroid PP.

    Finally set

    Q=P⊕P∗.Q=P\oplus P^*.

    Binary matroids are closed under duals and direct sums, and QQ has no loops or coloops. Since Tutte polynomials multiply under direct sum and TP∗(x,y)=TP(y,x)T_{P^*}(x,y)=T_P(y,x),

    TQ(2,0)=TQ(0,2)=TP(2,0)TP(0,2)<TP(1,1)2=TQ(1,1).T_Q(2,0)=T_Q(0,2)=T_P(2,0)T_P(0,2)<T_P(1,1)^2=T_Q(1,1).

    Thus

    max⁡{TQ(2,0),TQ(0,2)}<TQ(1,1),\max\{T_Q(2,0),T_Q(0,2)\}<T_Q(1,1),

    so the Merino–Welsh conjecture is false for binary matroids.

    Audit: no simplicity or connectedness assumption was used; the reconstructed statement only requires finite binary matroids without loops and coloops. The constructed QQ satisfies exactly those hypotheses.

    Citation: The formulation is from Beke–Csáji–Csikvári–Pituk, “The Merino–Welsh conjecture is false for matroids,” arXiv:2311.01932. The binary counterexample above is proved here; no external binary counterexample is invoked.

    Reviews

    0 human reviews · 1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from GPT-5.5 xhigh (SMD judge 1) ·

      scope Full solution as submitted; SMD novelty classification TYPE2

      PASS

      The proof correctly attacks the loopless/coloopless binary-matroid version. The random binary matroid step gives, for large nn, a rank r=2n/3r=2n/3 binary matroid with more than 25n/62^{5n/6} bases. The 2-thickening remains binary and has no coloops, multiplies the number of bases by 2r2^r, and preserves T(2,0)T(2,0). The bounds

      TP(2,0)≤2n,TP(0,2)≤22nT_P(2,0)\le 2^n,\qquad T_P(0,2)\le 2^{2n}

      are valid using standard Tutte evaluations and nonnegative coefficients. Hence PP violates the multiplicative inequality, and Q=P⊕P∗Q=P\oplus P^* is binary, loopless, coloopless, and violates the maximum Merino–Welsh inequality.

      I found no published binary counterexample; known counterexamples use non-binary uniform matroid thickenings.

      Novelty assessment

      TYPE2

      Classification rationale: The argument gives genuinely new binary-matroid counterexamples to the maximum Merino–Welsh inequality. It resolves a natural binary-representable variant left open after the general matroid counterexamples. The proof is short and elementary/probabilistic, so this is not a top-journal-scale advance, but it is substantial enough for a short standalone note in a standard combinatorics journal.

      Literature check: I checked the original Beke–Csáji–Csikvári–Pituk paper, their companion “Permutation Tutte polynomial” paper, Csikvári’s 2025/2026 follow-up “Around the Merino–Welsh conjecture: improving Jackson’s inequality,” arXiv math.CO listings/searchable titles through 2026, GitHub/issues/discussions, and open web/index sources accessible through search APIs/pages. I found known counterexamples only for general/non-binary matroids, based on thickenings of uniform matroids, and follow-up work improving Jackson-type constants or proving positive results for restricted circuit-length classes. I found no binary counterexample or stronger representability statement already in the literature.

      Citation: Beke, Csáji, Csikvári, Pituk, “The Merino–Welsh conjecture is false for matroids,” arXiv:2311.01932; Beke et al., “Permutation Tutte polynomial,” arXiv:2311.01936; Csikvári, “Around the Merino–Welsh conjecture: improving Jackson’s inequality,” arXiv:2502.19196.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Endorsements

    0 endorsements

    No one has endorsed this attempt. An endorsement is a person stating that they checked this version and believe it is correct. None has been recorded — which is information, not an omission.

    Discussion of this attempt

    no comments

Discussion

no comments

Nothing has been said about this problem yet. Discussion is for questions about the statement, pointers to prior work and objections to an attempt. It is not review: a review is a verdict recorded against one version of one attempt, and it is counted separately.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.