Matching works

7 works

math.CO — Combinatorics

A new proof of van der Waerden's inequality, and beyond

Contributed by Suvrit Sra

We give a new, self-contained proof of van der Waerden's permanent inequality via a monotone-averaging argument. Specifically, we show that the minimum total correlation of a random permutation with prescribed doubly stochastic marginals never decreases when two rows or two columns of the marginal matrix are averaged. This quantity is largest at the uniform matrix, which yields van der Waerden's bound. The monotone-averaging rests on the quadratic Alexandrov–Fenchel inequality, which lets us extend the argument to many other problems. In this way we also prove the Friedland–Tverberg inequalities and Gurvits's coefficient bound for Lorentzian polynomials.

A mix of human-written and AI-generated textHuman understanding: all partsAlexandrov-Fenchel inequalityFriedland-Tverberg inequalityLorentzian polynomialscapacitydoubly stochastic matricesentropymixed volumespermanenttotal correlationvan der Waerden inequality
Nov 05, 202631 pages
PDFView work

math.RA — Rings and Algebras

Maximal sublattices of convex geometries: four counterexamples

Contributed by Deep Bhattacharjee

Adaricheva, Mata, Silberger and Zamojska-Dzienio conjectured that in a finite convex geometry, and more generally in a finite join-semidistributive lattice, the complement of a maximal sublattice is a union of intervals with a common least element, and proved this for convex dimension two. We give convex geometries of convex dimension four and three in which such a complement has two and three minimal elements, so their theorem does not extend. The same examples refute their Hypothesis 4 and one half of their Question 2; an eleven-element convex geometry refutes the other half, and a ten-element lattice their Hypothesis 3.

A mix of human-written and AI-generated textHuman understanding: some partsconvex geometryformal verificationjoin-semidistributive latticemaximal sublatticemeet-irreducible element
Oct 23, 202611 pages
PDFView work

math.CO — Combinatorics

All τk\tau_k-maximal graphs have the same size

Contributed by Deep Bhattacharjee

A graph is τk\tau_k-maximal if none of its subgraphs has k+1k+1 edge-disjoint spanning trees, but adding any missing edge creates such a subgraph. Wang and Tian conjectured that every τk\tau_k-maximal graph on n≥2k+2n\ge 2k+2 vertices has exactly (k+1)(n−1)−1(k+1)(n-1)-1 edges. We prove this conjecture.

A mix of human-written and AI-generated textHuman understanding: some partscount matroidedge-disjoint spanning treessaturated graphssparse graphs
Oct 22, 20265 pages
PDFView work

math.CO — Combinatorics

Counterexamples to the Two-Bases Conjecture for the Tutte Polynomial

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)\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 MM of rank 3232 on 6464 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 MmM_m of rank 2m2m on 4m4m 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 6060 elements whose ground set is partitioned into two bases and for which TM(2,0)<TM(1,1)T_M(2,0)<T_M(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
Oct 21, 20266 pages
PDFView work

math.CO — Combinatorics

Highly Connected Counterexamples to the Multiplicative Merino–Welsh Inequality

Contributed by Jungang Chen

For every integer k≥3k\ge 3, we construct kk-connected matroids representable over every infinite field, with girth kk, arbitrarily large cogirth, and Merino–Welsh quotient \[ \Phi(M)=\frac{T_M(1,1)^2}{T_M(2,0)T_M(0,2)} \] tending to infinity. In particular, this disproves **Conjecture 7.2 of Csikvári (2026)**, which asserts the multiplicative Merino–Welsh inequality for simple and cosimple matroids, and therefore also the stronger **Conjecture 7.3** therein, as observed by its author. Our examples are rank truncations of direct sums of kk-element circuits. We give a 3-connected counterexample on 1011 elements of rank 433, certified by exact integer arithmetic, and a 6048-element counterexample admitting a proof without computation. Taking the direct sum of a counterexample with its dual also gives a negative answer to **Problem 4.3 of Beke, Csáji, Csikvári, and Pituk (2024)**: the original maximum and additive Merino–Welsh inequalities can fail for simple and cosimple matroids. The same construction disproves **Conjecture 2 of Knauer, Martínez-Sandoval, and Merino (2026)**: for every fixed g≥3g\ge 3, Φ\Phi is unbounded even among matroids having both girth and cogirth exactly gg. The dual direct-sum examples need not be connected; these constructions do not disprove the graphical or binary versions.

Primarily AI-generated textHuman understanding: some parts
Oct 21, 20267 pages
PDFView work

math.CO — Combinatorics

Antimatroid characterization of RAF interior operators

Contributed by Michael Mislan

Addressing the RAF-realizability question in Section 4 of Mike Steel's Interior Operators and Their Relationship to Autocatalytic Networks (arXiv:2305.16714v4, 2023), we characterize which interior operators on the subsets of a finite set E are maxRAF operators of catalytic reaction systems whose reaction set is exactly E. An interior operator is represented by its family of fixed sets, a union-closed family containing the empty set. A same-ground realization is a system with one reaction per element of E, finitely many molecule types, a food set and a catalysis relation; it realizes the empty set together with its RAFs, the nonempty reaction sets whose reactants arise from food by iterated closure under the selected reactions and whose reactions are each catalysed by a molecule of that closure. Such a family has a same-ground realization if and only if it is the intersection of an accessible union-closed family A and a predecessor-support family. Here A contains the empty set, is closed under unions, and every nonempty member of A has an element whose removal leaves a member of A; the members of A need not cover E. A set S is supported by a predecessor map P on E when every element e of S has some element of S in P(e), loops allowed. The family consisting of the empty set and all subsets of size at least three has a same-ground realization if and only if E has at most four elements. This gives the sharp threshold for the family considered in Proposition 5 and its subsequent remarks in Steel (2023). Both results are formalized in Lean 4 with Mathlib.

Primarily AI-generated textHuman understanding: some partsLean formalizationRAF setsantimatroidsfood generationinterior operatorsrealizability
Oct 20, 202616 pages
PDFView work

math.CO — Combinatorics

Collapsibility of Alexander duals for shade maps

Contributed by Darij Grinberg

Let EE be a nonempty finite set. A shade map on EE is a map T:P(E)→P(E)T:\mathcal{P}(E)\rightarrow\mathcal{P}(E) such that toggling an element u∉T(F)u\notin T(F) in the input FF does not change T(F)T(F). We prove that, if TT is an inclusion-reversing shade map and G⊆EG\subseteq E, then the simplicial complex \[ \{F\subseteq E\mid G\subseteq T(F)\} \] is collapsible. Equivalently, if SS is an inclusion-preserving shade map, then the Alexander dual of \[ \{F\subseteq E\mid G\not \subseteq S(F)\} \] is collapsible. This is an Alexander-dual companion to the shade-map collapsibility theorem in \emph{The Elser nuclei sum revisited}. The proof first matches all faces on which T(F)≠ET(F)\neq E by a toggle. The remaining faces, characterized by T(F)=ET(F)=E, form the free convex set complex of an associated antimatroidal quasi-closure operator. We give a self-contained recursive acyclic matching on this complex. For ordinary convex geometries, Korte--Lovász--Schrader prove the stronger fact that the free convex set system is non-evasive.

A mix of human-written and AI-generated textHuman understanding: all partsantimatroidsconvex geometriesdiscrete Morse theorygraphssimplicial complexes
Sep 30, 202618 pages
PDFView work

Advanced search

Text
Human understanding
Linked formalizations