Statement and source
Tomack Gilmore's Trees, forests, and total positivity: I. q-trees and q-forests matrices, Electronic Journal of Combinatorics 28(3) (2021), P3.54, states the following as Conjecture 6.16, equation (6.133), on printed page 65:
For every integer ,
Here denotes the perfect matchings of . Two arcs , , with , cross when , nest when , and align when .
- Published article and DOI.
- Published PDF at UCL.
- arXiv v2. In this version the same assertion is Conjecture 6.11, equation (6.130), printed page 56.
The theorem below proves this identity for all , with both and indeterminate. It also identifies the parameter with aligned arc pairs. The classical matching/Dyck-path correspondence and its continued fraction are not new results. The assertion being proved is their identification with Gilmore's product-defined matrix.
The exact matrix
Write
All matrix indices start at zero. Let be the unit-lower-triangular matrix
and zero if . Empty products are one.
Equivalently is the inverse of the unit-lower-bidiagonal matrix with subdiagonal entries . This is Gilmore's with .
Set , and define
This is precisely the factorization in the published equation (6.108), or arXiv equation (6.105). For every fixed finite leading block, all sufficiently high-index factors are identity on that block, so the product is well-defined algebraically. In particular, , for , and if .
The formula for follows by multiplying its subdiagonal weights. In particular its power of is , consistent with Gilmore's displayed example matrix (6.110). This avoids relying on the isolated, apparently missing exponent in the printed equation (6.109).
A recurrence from the product
Each is homogeneous of degree in : every product term telescopes its row-to-column decreases.
Removing the rightmost factor and shifting indices down by one gives the identity
Indeed the factor with index , after deleting the first row and column, is the factor with index and replaced by .
Consequently, for ,
Separating the term from this sum proves
No division or nonvanishing parameter assumption is used. The boundary values and (2) determine every row uniquely by descending induction on .
Weighted paths
For and , consider paths with unit up-steps and down-steps that:
- start at height zero and never go below zero;
- have exactly up-steps and down-steps;
- therefore have length and finish at height .
Give a down-step from height weight . Give an up-step weight , where is the number of down-steps preceding it. Let be the sum of these path weights.
The empty path gives . The all-up path gives . A path ending with a down-step has a predecessor counted by , and its final step has weight . A path ending with an up-step has a predecessor counted by . This predecessor has down-steps, so its final up-step has weight . The second possibility is absent at .
Thus the satisfy (2) with the same boundary values, and
This is an all-entry path interpretation of Gilmore's matrix. The exponent of is the number of ordered pairs of steps in which a down-step occurs before an up-step.
Perfect matchings and the proof
For , the paths in (3) are Dyck excursions with up-steps and down-steps.
Read a perfect matching from left to right. An arc's left endpoint is an up-step; its right endpoint is a down-step. At a right endpoint with current height , there are exactly open arcs. Order their left endpoints increasingly and suppose the arc being closed has position .
Of the other open arcs:
- the arcs opened earlier will close later, and nest around the closing arc;
- the arcs opened later will close later, and cross the closing arc.
This right endpoint therefore contributes
to the crossing–nesting weight. Each crossing or nesting is counted exactly once, at the first right endpoint of its two arcs. Summing over the choices gives
A Dyck path together with these closing choices uniquely specifies a matching, and every matching has exactly one such encoding.
Moreover, each down-step occurring before a later up-step records exactly one aligned pair: the earlier arc has closed before the later arc opens. Thus the path's exponent of equals the number of aligned arc pairs. There is one factor per down-step.
We conclude, as an identity in , that
This holds also for , using the empty matching. Setting proves Gilmore's crossing–nesting conjecture in full.
Checks and limits
Run python3 results/gilmore-crossing-nesting/verify.py from the repository root. The companion verifier compares three independently implemented objects: the defining matrix product, the recurrence, and literal enumeration of perfect matchings with crossing/nesting/alignment statistics. All 64 entries of the leading 8-by-8 matrix agree exactly, and the first-column identities agree through matchings on 12 vertices (10,395 matchings at the last size), with all four variables formal. These are finite consistency checks; the argument above proves the unrestricted identity.
A second research agent independently derived the block self-similarity, recurrence, path coordinates, closing-choice weights, and alignment statistic. No gap was found in that internal audit.
The neighboring shifted reverse Bessel Hankel-total-positivity conjecture is different. It concerns all finite minors formed from the entire row-polynomial sequence after a column twist and parameter shifts. Equation (4) does not settle it.