Matching works

11 works

math.CO — Combinatorics

An upper bound for the connective constant of the square lattice

Contributed by Tejasvi Singh Tomar

We prove that the connective constant μ\mu of the square lattice Z2\mathbb{Z}^2, the exponential growth rate of the number of nn-step self-avoiding walks, satisfies μ≤2.6586513\mu\le2.6586513. The previous best upper bound, μ≤2.662342426\mu\le2.662342426, is due to Couronné. Like the bounds of Pönitz and Tittmann and of Couronné, ours comes from a finite automaton that remembers a bounded part of the past of the walk. The new idea is to count bridges. Since they can all be preceded by the same infinite history, the automaton may treat as visited the unvisited cells that no infinite self-avoiding continuation can reach, and three tests on the current state and the next step recognize such cells. The bound is checked in exact integer arithmetic and proved in the Lean proof assistant.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23715896

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 15, 202610 pages
PDFView work

math.RT — Representation Theory

Pretorsion theories and image-closed subcategories

Contributed by Haruhisa Enomoto

A pretorsion theory generalizes a torsion pair by allowing its two components to have a nonzero intersection, with morphisms factoring through the intersection playing the role of zero morphisms. In the module category of a finite-dimensional algebra, the first and second components of pretorsion theories are known to be the quotient-closed and submodule-closed subcategories, respectively. We show that the intersections of the two components are precisely the image-closed subcategories, namely those containing the image of every morphism between their objects, and that the pretorsion theories form a complete lattice. For a linearly oriented quiver of type A, we prove that the numbers of pretorsion theories and of image-closed subcategories are the Genocchi and median Genocchi numbers, respectively. Counting pretorsion theories by the number of indecomposable modules in their intersection, and image-closed subcategories by their number of indecomposable modules, yields the Gandhi polynomial refinements of Han and Zeng.

Author comments: Currently we are working Lean formalization, which will be released soon.

Primarily AI-generated textHuman understanding: some partsGandhi polynomialGenocchi numberconvex geometryimage-closed subcategoryinterval modulepretorsion theory
Nov 10, 202635 pages
PDFView work

math.NT — Number Theory

A congruence modulo p^2 for the p-th coefficient of e(1-z)^((1-z)/z)

Contributed by David Niedbala Giraudin

Define E_n by sum_{n>=0} E_n z^n = exp(sum_{k>=1} z^k/(k(k+1))) = e(1-z)^((1-z)/z). Equivalently, e(1+1/x)^(-x) = sum_{n>=0} E_n (x+1)^(-n), the reciprocal of the expansion of e^(-1)(1+1/x)^x used by Yang in refinements of Carleman's inequality. We prove that for every odd prime p, E_p = -p/2 (mod p^2); in particular v_p(E_p) = 1. The proof is elementary. With Phi(u) = e(1+u)^(-1/u), it combines the two expressions of E_p through the coefficients of Phi that come from the identities e(1-z)^((1-z)/z) = Phi(-z)/(1-z) and e(1-z)^((1-z)/z) = Phi(z/(1-z)), and it reduces the congruence to the differential recurrence of the E_n read modulo p. A script checks the statement and the intermediate congruences for all odd primes below 200 and a few larger ones.

Primarily AI-generated textHuman understanding: no partsCarleman's inequalitycongruences modulo p^2harmonic numbersp-adic valuationpower series coefficients
Nov 04, 20264 pages
PDFView work

math.CO — Combinatorics

The ten minimum universal sets of MacMahon cubes

Contributed by Jason Davies

A collection of six-coloured MacMahon cubes is universal if eight of its cubes can be selected to build a 2×2×22\times2\times2 model of any target variety, with matching exterior colours and no internal matching requirement. We prove that exactly ten labelled collections attain the known minimum size of twelve, even when repeated varieties are allowed, resolving the conjectures of Johnson and Roldán. Usable-cube inequalities force a symmetric multiplicity matrix with row and column sums two; corner coverage then forces two disjoint triangles in Conway's tableau. The written proof is elementary and requires no exhaustive search. The classification and its discrete geometric interpretation are formalised in Lean 4. Exhaustive computation provides a separate check and additional target-count distributions.

Primarily AI-generated textHuman understanding: some partsConway's tableauEight Blocks to MadnessLean 4MacMahon cubesuniversal sets
Nov 02, 20267 pages
PDFView work

math.MP — Mathematical Physics

Riordan lattice paths counted by area

Contributed by Ilmar Gahramanov

We study Riordan paths enumerated by the area between the path and the axis. We show that the generating function satisfies a qq-Riccati equation and can be written in a closed form as a ratio of basic hypergeometric series. The auxiliary series admits an algebraic representation as the motivic generating series of a symmetric two-node quiver. We obtain explicit formulas for the coefficients, the exponential asymptotics of the number of paths of given area, and a linear recurrence whose coefficients are signed counts of partitions into distinct parts. For a random path of area nn we obtain a joint Gaussian limit law for the numbers of returns, horizontal steps and up steps. The height is of order log⁡n\sqrt{\log n}, and its distribution concentrates on two adjacent integers determined explicitly by nn.

A mix of human-written and AI-generated textHuman understanding: some parts
Nov 02, 202614 pages
PDFView work

math.CO — Combinatorics

Algebraicity of rank-two scattering wall functions

Contributed by Qiyue Tang

We prove that every wall function in the rank-two scattering factorization determined by two polynomial initial walls over a field of characteristic zero is algebraic. This resolves the algebraicity question posed by Kontsevich and recorded by Gross and Pandharipande, and its cluster-scattering formulation in the work of Burcroff, Lee, Mou, Musiker, and Reineke.

A mix of human-written and AI-generated textHuman understanding: some partsCluster Algebra
Oct 29, 202619 pages
PDFView work

math.CO — Combinatorics

Even-intersecting families of lattice paths and the Catalan numbers

Contributed by Deep Bhattacharjee

Shankar proved that a family of North--East lattice paths from (0,0)(0,0) to (n,n)(n,n) in which any two paths share an even number of edges has at most 2n2^n members, and conjectured that exactly CnC_n families attain this bound, where CnC_n is the nnth Catalan number. We prove the conjecture. The proof determines all equality cases of the inequality behind Shankar's bound: they correspond to noncrossing partial matchings of {1,…,m}\{1,\dots,m\} whose unmatched points lie under no arc, and there are (m⌊m/2⌋)\binom{m}{\lfloor m/2\rfloor} of them.

A mix of human-written and AI-generated textHuman understanding: some partsCatalan numbersEventown theoremeven intersectionslattice pathsnoncrossing matchings
Oct 22, 202612 pages
PDFView work

math.CO — Combinatorics

A Formally Verified Certificate Proof of the Maximum Number of Stable Matchings for Six Men and Six Women

Contributed by YURAN XIU

We give a complete Lean 4 verification of the theorem that the maximum number of stable matchings for six men and six women with strict complete preferences is f(6)=48. Jo (2026) previously proved the unrestricted upper bound, and Benjamin, Converse, and Krieger (1995) supplied an attaining construction. Our contribution is an alternative, fully formalized proof using a finite certificate; the value 48 and the unrestricted theorem are already known. We reduce stable matchings of arbitrary profiles to order ideals of sequences of cyclic partner exchanges in which no man revisits a partner. A weighted frontier recurrence counts these ideals, and a sum of permanents bounds every future continuation. These bounds yield a finite certificate with 135,828 states. The complete argument, including the reduction for arbitrary profiles, certificate soundness, all concrete checks, and an attaining profile, has been formalized and checked in Lean 4. The final unconditional theorem depends only on the standard axioms of Lean and mathlib.

Primarily AI-generated textHuman understanding: no partsLeanextremal combinatoricsformal verificationstable marriagestable matchings
Oct 16, 202613 pages
PDFView work

math.CO — Combinatorics

Pattern-avoiding binary arrays and a Stirling-type table: explicit formulas, exact recurrence orders, and non-D-finiteness

Contributed by Yunkun Song

Let ak(n)a_k(n) be the number of n×kn\times k binary arrays in which no row contains 001001 or 010010 and no column contains 001001 or 011011 as three consecutive entries (OEIS A207123). Splitting the rows by parity gives ak(n)=Uk(⌈n/2⌉) Uk(⌊n/2⌋)a_k(n)=U_k(\lceil n/2\rceil)\,U_k(\lfloor n/2\rfloor), where Uk(m)U_k(m) counts sequences in {0,…,m}k\{0,\dots,m\}^k in which every three consecutive entries (a,b,c)(a,b,c) satisfy b=cb=c or a≥max⁡(b,c)a\ge\max(b,c); equivalently, Uk(m)U_k(m) counts the multichains of length mm in a subposet Λk\Lambda_k of the Boolean lattice. We prove three main results. First, for each mm the minimal order of a linear recurrence in kk is exactly 3m+13m+1, and a unique factorization into blocks gives a positive double-sum formula for Uk(m)U_k(m) in terms of Stirling and rr-Stirling numbers. Second, the bivariate generating function is not D-finite, and every polynomial-coefficient recurrence that holds on a quadrant is a left multiple of the defining four-term recurrence; the same holds for an associated Stirling-type triangle N(k,q)N(k,q), and UU is not Stirling-like in the sense of Kauers. Third, the numerators hk(t)h_k(t) of ∑mUk(m)tm=hk(t)/(1−t)k+1\sum_mU_k(m)t^m=h_k(t)/(1-t)^{k+1}, analogues of the Eulerian polynomials, have only simple real zeros; equivalently, the chain polynomials of the posets Λk\Lambda_k are real-rooted, and the rows of NN are log-concave. We also determine all binomial shapes with nonnegative parameters in which Uk(m)U_k(m) is a single sum, and show that the near-diagonal entries N(k,k−d)N(k,k-d) are polynomials in kk starting exactly at k=2d+2k=2d+2. The reduction, the exact orders, the explicit formula, the non-D-finiteness, the description of the quadrant recurrences and the near-diagonal theorem are formalized in Lean 4 with Mathlib.

Primarily AI-generated textHuman understanding: some partsD-finite power seriesLean 4OEIS A207123Ore algebrasStirling numberschain polynomialsformal verificationpattern-avoiding arraysr-Stirling numbersreal-rootedness
Oct 16, 202639 pages
PDFView work

math.CO — Combinatorics

An Intrinsic Formula for the Ray–West Correction Term

Contributed by Donald Poindexter

For a nonempty permutation β\beta of length mm, let g2(β)g_2(\beta) denote the number of distinct permutations of length m+2m+2 containing β\beta. Ray and West showed that $$ g_2(\beta)=\frac{m^4+2m^3+m^2+4m+4-2j(\beta)}{2}, \qquad 0\le j(\beta)\le m-1, $$ but their correction term was not expressed as a statistic of β\beta. This was posed explicitly as Problem 3.7 by Vatter. We give a polynomial-time formula defined entirely from β\beta: j(β)=L(β)+R(β)j(\beta)=L(\beta)+R(\beta), where LL counts licensed gaps and RR counts anchor-free two-deletion classes containing a collision whose canonical alignment support is a permutation interval. We also derive the Ray–West bound intrinsically and characterize its upper-bound equality cases as precisely the layered or reverse-layered permutations. The proof is combinatorial. Exact computation is used only for independent corroboration; the accompanying proof-and-replay archive contains the full proof supplement and bounded verification. This preliminary technical report was first deposited on Zenodo on August 9, 2026: https://doi.org/10.5281/zenodo.21857882.

Primarily AI-generated textHuman understanding: no partsRay–West correction termWilf equivalencedeletion classesenumerative combinatoricspermutation patternspermutation statisticsstrong intervals
Oct 15, 202612 pages
PDFView work

math.CO — Combinatorics

Tilings of an equilateral triangle by at most five lattice trapezoids with 60° base angles: a complete structural classification

Contributed by Gonzalo Barria

We study tilings of an equilateral triangle of side n in the triangular grid by k lattice trapezoids with base angles 60°, the objects behind the OEIS sequences A389392 (k = 4) and A391498 (k = 5). We prove two angle identities valid for every such tiling and a lemma relating the number of boundary vertices to the number of pieces having a side on the boundary. With these tools we show that there are exactly 1, 2 and 13 combinatorial types of tilings for k = 3, 4, 5. For k = 3 every tiling is a pinwheel. For k = 4 every tiling belongs to one of the two categories used in A389392, a fact that had previously been taken for granted. For k = 5 the thirteen types refine the eight categories of A391498; in three of them a piece has no side on the boundary. As a consistency check, the volumes of the parameter polytopes together with the generic multiplicities reproduce the leading coefficient 7/36 of the conjectured quasi-polynomial for A391498. All lemmas were checked against an exhaustive enumeration of the tilings with pairwise distinct pieces for n ≤ 15. Finally, the classification turns the thirteen types into eight explicit families of sets of shapes, and an inclusion–exclusion over them reduces the conjectured generating function of A391498 to twelve elementary counting statements, and we settle all twelve: the resulting closed formula reproduces the sequence for every n ≤ 127.

A mix of human-written and AI-generated textHuman understanding: all partsOEIS A391498lattice trapezoidsquasi-polynomialrational generating functiontilings of an equilateral triangle
Oct 01, 202623 pages
PDFView work

Advanced search

Text
Human understanding
Linked formalizations