pith. sign in

arxiv: 2606.11776 · v1 · pith:CX2THF5Onew · submitted 2026-06-10 · 🧮 math.CO · math.RT

Special Matchings, Brenti's Conjecture, and the Combinatorial Invariance Conjecture

Fabrizio Caselli , Mario Marietti This is my paper

Pith reviewed 2026-06-27 09:24 UTC · model grok-4.3

classification 🧮 math.CO math.RT
keywords special matchingsBruhat intervalsKazhdan-Lusztig R-polynomialsCoxeter groupstype ABrenti conjecturecombinatorial invariance
0
0 comments X

The pith

Special matchings on Bruhat intervals in type A completely determine the Kazhdan-Lusztig R-polynomials.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives a full combinatorial characterization of special matchings on arbitrary Bruhat intervals in Coxeter groups of type A. This characterization is then used to recover the R-polynomials exactly as a product over the matched edges. The recovery matches the algebraic definition, which proves Brenti's 2003 conjecture. The same result supplies new supporting evidence for the Combinatorial Invariance Conjecture.

Core claim

In Coxeter groups of type A the special matchings of any Bruhat interval are precisely the matchings that arise from a certain explicit combinatorial rule on the underlying permutations. These matchings alone suffice to compute the interval's R-polynomial by a simple product formula that agrees with the standard Kazhdan-Lusztig definition.

What carries the argument

Special matchings of Bruhat intervals: pairings of elements that preserve covering relations and length parity while satisfying a descent-set condition.

If this is right

  • R-polynomials in type A become computable directly from the poset structure of the interval.
  • Brenti's matching-based algorithm works for every interval in type A.
  • The Combinatorial Invariance Conjecture receives verification for all R-polynomials arising in type A.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same exhaustive listing of matchings could be attempted in other finite Coxeter types to test the invariance conjecture.
  • The explicit matching rule may yield non-recursive formulas for R-polynomials restricted to type A.

Load-bearing premise

The combinatorial rules that describe all special matchings in type A are both exhaustive and sufficient to reconstruct the R-polynomials without hidden algebraic dependencies.

What would settle it

A concrete Bruhat interval in the symmetric group whose R-polynomial computed from the listed special matchings differs from the value given by the standard recursive definition.

Figures

Figures reproduced from arXiv: 2606.11776 by Fabrizio Caselli, Mario Marietti.

Figure 1
Figure 1. Figure 1: A k-crown Lemma 2.2. Let W be an arbitrary Coxeter group. Let u, v ∈ W, with u ≤ v and ℓ(v) − ℓ(u) = 3. Then [u, v] is a k-crown for some k ≥ 2. If furthermore W is a Coxeter group of type A, then [u, v] is a k-crown for some k ∈ {2, 3, 4}. The following are two useful ways to decompose elements of W (see [5, §2.4]). Proposition 2.3. Let J ⊆ S and w ∈ W. (i) There is a unique factorization w = w JwJ with w… view at source ↗
Figure 2
Figure 2. Figure 2: A forbidden edge Proposition 3.3. Let M be a matching of W. Let u, v ∈ W with u < v, M(v) ◁ v, and M(u) ▷ u. Then M restricts to a special matching of [u, v] if and only if [u, v] contains no forbidden edges. Proof. It is clear that, if [u, v] contains a forbidden edge, then M does not restrict to a special matching of [u, v]. Suppose now that [u, v] contains no forbidden edges and proceed by induction on … view at source ↗
Figure 3
Figure 3. Figure 3: Proof of Lemma 5.1 If M(x) ̸= (a, b)x then, without loss of generality, we can assume M(x) = (b, c)x, for some c ̸= a. By Lemma 2.5, it follows M(yi) = (a, c)x for i ∈ {1, 2}, which is clearly a contradiction. □ Definition 5.2. We let i(M) be the minimum index i such that there exist z ∈ [u, v] and l ∈ [n] such that M(z) = (i, l)z. We say that i(M) is the smallest index moved by M. Similarly, we define j(M… view at source ↗
Figure 4
Figure 4. Figure 4: Local configurations of a special matching Next result will be extremely useful [PITH_FULL_IMAGE:figures/full_fig_p015_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Proof of Lemma 5.5 for s = 3 Now let z0 = xs+1, and zi = (ci , d)zi−1 for each i ∈ [s]. Note that zi ◁ zi−1, and, by the first part of the proof, M(zi) = (a, b)zi . Notice zs = [ c1 c c2 . . . cs d ] [PITH_FULL_IMAGE:figures/full_fig_p016_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Proof of Proposition 5.6 Another claim that we prove is the following: if there is a sequence am < · · · < a1 < a0 = a for some m ≥ 1 and am > i(M), with u = [ am . . . a1 a b ] which satisfies condition (2) of the statement, then one of the following two conditions apply: (i) there exists am+1 < am such that the sequence am+1 < · · · < a1 < a0 is such that u = [ am+1 . . . a1 a b ] and satisfies condition… view at source ↗
Figure 7
Figure 7. Figure 7: The left and right basic chains We call the sequence u0, u1, . . . , ur and the sequence u ′ 0 , u′ 1 , . . . , u′ s in the statement of Proposition 5.6, respectively, a left basic chain and a right basic chain. Proposition 5.6 has the following notable consequence. Corollary 5.7. There exists z ∈ [u, v] such that M(z) = (i(M), j(M))z. Proof. Keep the notations of Proposition 5.6. For p ∈ [r] and q ∈ [s], … view at source ↗
Figure 8
Figure 8. Figure 8: Proof of Corollary 5.7 6. Towards a contradiction I In this section, we begin the study of the structure of an interval admitting a special matching that does not fall into the desired classification. This will eventually lead to a contradiction. Throughout this section, we fix a special matching M of an interval [u, v] in a Coxeter group W of type A. We set J = J(M) and s = s(M). Suppose that M(x) ̸= λ J … view at source ↗
Figure 9
Figure 9. Figure 9: A partial special matching (left) and its extension (right) Lemma 8.10. Let I = [u, v] be a Bruhat interval of rank r and height h with no special matchings. Then there exists a partial special matching M of I such that I M is isomorphic to a Bruhat interval [u ′ , v′ ] ⊆ W(Ar) with ℓ(u ′ ) = h− 1. In particular, the subinterval [M(u), M(v)] of I M is isomorphic to a Bruhat interval of height at most h − 1… view at source ↗
read the original abstract

In this work, we settle a problem that dates back to the early 2000s. We provide a complete characterization of special matchings of arbitrary Bruhat intervals in Coxeter groups of type $A$ and apply this result to prove a conjecture of Brenti from 2003 concerning the computation of Kazhdan-Lusztig $R$-polynomials via special matchings. This yields new evidence in support of the Combinatorial Invariance Conjecture.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper provides a complete characterization of special matchings on arbitrary Bruhat intervals in Coxeter groups of type A and applies the result to prove Brenti's 2003 conjecture on computing Kazhdan-Lusztig R-polynomials via special matchings, yielding evidence for the Combinatorial Invariance Conjecture.

Significance. A proof of Brenti's conjecture would constitute a notable advance in the combinatorial study of Kazhdan-Lusztig polynomials. If the characterization of special matchings is expressed solely in terms of the covering relations and rank function of the Bruhat interval poset (without reference to descent sets, inversion tables, or generator labels tied to a concrete embedding in S_n), the result would supply direct support for the Combinatorial Invariance Conjecture by exhibiting an intrinsic poset computation of the R-polynomials.

major comments (2)
  1. [§4] §4 (characterization theorem): the stated conditions on special matchings invoke descent sets and reduced-word data specific to the type-A realization. It is therefore unclear whether the recursion for the R-polynomials is independent of the Coxeter embedding, which is load-bearing for the claimed support of the Combinatorial Invariance Conjecture.
  2. [§5] §5 (application to Brenti's conjecture): the proof that the characterized matchings recover the R-polynomials exactly must be checked for hidden dependence on the concrete group presentation; if the matching conditions are not poset-intrinsic, the argument does not establish the conjecture in the form required for CIC evidence.
minor comments (1)
  1. [§2] Notation for Bruhat intervals and covering relations in §2 should be made fully self-contained so that the characterization can be read without external reference to standard Coxeter-group texts.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and for raising important questions about the poset-intrinsic nature of our results and their implications for the Combinatorial Invariance Conjecture. We address the major comments point by point below.

read point-by-point responses

  1. Referee: [§4] §4 (characterization theorem): the stated conditions on special matchings invoke descent sets and reduced-word data specific to the type-A realization. It is therefore unclear whether the recursion for the R-polynomials is independent of the Coxeter embedding, which is load-bearing for the claimed support of the Combinatorial Invariance Conjecture.

    Authors: We acknowledge that the conditions in the characterization theorem of §4 are expressed using descent sets and reduced-word information from the standard embedding of type A into S_n. In type A, however, these data are recoverable from the covering relations and rank function of the Bruhat interval poset. We will revise §4 to include an explicit argument establishing this equivalence, thereby making clear that the recursion for the R-polynomials depends only on poset data. revision: partial

  2. Referee: [§5] §5 (application to Brenti's conjecture): the proof that the characterized matchings recover the R-polynomials exactly must be checked for hidden dependence on the concrete group presentation; if the matching conditions are not poset-intrinsic, the argument does not establish the conjecture in the form required for CIC evidence.

    Authors: The argument in §5 applies the characterization of §4. Once the poset-intrinsic reformulation is added to §4 as planned, the recovery of the R-polynomials will be shown to proceed from poset data alone, with no residual dependence on the concrete Coxeter presentation. We will update the discussion in §5 to emphasize this point and its bearing on the Combinatorial Invariance Conjecture. revision: partial

Circularity Check

0 steps flagged

No circularity detected; derivation is self-contained combinatorial argument

full rationale

The paper claims a direct combinatorial characterization of special matchings on Bruhat intervals in type A, followed by an application to Brenti's 2003 conjecture on R-polynomials. No equations, recursive definitions, or self-citations are presented that reduce the claimed result to a fitted input, renamed ansatz, or prior author work by construction. The abstract and described claims indicate an independent proof resting on poset structure, with no load-bearing reduction to the Combinatorial Invariance Conjecture itself. This is the normal case of a self-contained argument.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no explicit free parameters, axioms, or invented entities; the result is presented as a combinatorial characterization and proof.

pith-pipeline@v0.9.1-grok · 5598 in / 1213 out tokens · 25519 ms · 2026-06-27T09:24:29.285083+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 2 canonical work pages

  1. [1]

    Abdallah, M

    N. Abdallah, M. Hansson, A. Hultman,Topology of posets with special partial matchings, Adv. Math.348(2019), 255–276

    2019

  2. [2]

    Abdallah, A

    N. Abdallah, A. Hultman,Combinatorial invariance of Kazhdan–Lusztig–Vogan polynomials for fixed point free involutions, J. Algebraic Combin.47(2018), 543–560

    2018

  3. [3]

    Barkley, C

    G.T. Barkley, C. Gaetz,Combinatorial invariance for elementary intervals, Math. Ann.392 (2025), 3299–3317. 38 CASELLI, MARIETTI

    2025

  4. [4]

    Barkley, C

    G.T. Barkley, C. Gaetz, T. Lam,Combinatorial invariance for the coefficient ofqin Kazhdan- Lusztig polynomials, arXiv:2601.07793 [math.CO]

    arXiv

  5. [5]

    Bj¨ orner, F

    A. Bj¨ orner, F. Brenti,Combinatorics of Coxeter Groups, Graduate Texts in Mathematics,231, Springer-Verlag, New York, 2005

    2005

  6. [6]

    Blundell, L

    C. Blundell, L. Buesing, A. Davies, P. Veli˘ ckovi´ c, G. Williamson,Towards combinatorial in- variance for Kazhdan-Lusztig polynomials, Represent. Theory26(2022), 1145-1191

    2022

  7. [7]

    Brenti,A combinatorial formula for Kazhdan-Lusztig polynomials, Invent

    F. Brenti,A combinatorial formula for Kazhdan-Lusztig polynomials, Invent. Math.118 (1994), 371-394

    1994

  8. [8]

    Brenti,Kazhdan–Lusztig polynomials: History, Problems, and Combinatorial Invariance, S´ eminaire Lotharingien de Combinatoire49(2003), Article B49bJ

    F. Brenti,Kazhdan–Lusztig polynomials: History, Problems, and Combinatorial Invariance, S´ eminaire Lotharingien de Combinatoire49(2003), Article B49bJ

    2003

  9. [9]

    Brenti,The intersection cohomology of Schubert varieties is a combinatorial invariant, J

    F. Brenti,The intersection cohomology of Schubert varieties is a combinatorial invariant, J. European Combin.25(2004), 1151-1167

    2004

  10. [10]

    Brenti, F

    F. Brenti, F. Caselli, M. Marietti,Special Matchings and Kazhdan–Lusztig polynomials, Adv. Math.202(2006), 555-601

    2006

  11. [11]

    Brenti, F

    F. Brenti, F. Caselli, M. Marietti,Diamonds and Hecke algebra representations, Int. Math. Res. Not. IMRN,2006(2006), 29407

    2006

  12. [12]

    Brenti, M

    F. Brenti, M. Marietti,Kazhdan–Lusztig R-polynomials, combinatorial invariance, and hyper- cube decompositions, Math. Z.30925 (2025)

    2025

  13. [13]

    Burrull, N

    G. Burrull, N. Libedinsky, D. Plaza,Combinatorial invariance conjecture for ˜A2, Int. Math. Res. Not. IMRN,2023, Issue 10, (2023), 8903–8933

    2023

  14. [14]

    Caselli, M

    F. Caselli, M. D’Adderio, M. Marietti,Weak Generalized Lifting Property, Bruhat Intervals, and Coxeter Matroids, Int. Math. Res. Not. IMRN,2021, Issue 3, (2021), 1678–1698

    2021

  15. [15]

    Caselli, M

    F. Caselli, M. Marietti,Special matchings and Coxeter groups, Europ. J. Combin.,61(2017), 151–166

    2017

  16. [16]

    Caselli, M

    F. Caselli, M. Marietti,A simple characterization of special matchings in lower Bruhat inter- vals, Discrete Math.,341(2018), 851–862

    2018

  17. [17]

    Caselli, M

    F. Caselli, M. Marietti,Pircon kernels and up-down symmetry, J. Algebra565(2021), 324–352

    2021

  18. [18]

    Davies, P

    A. Davies, P. Veli˘ ckovi´ c, L. Buesing, S. Blackwell, D. Zheng, N. Tomaˇ sev, R. Tanburn, P. Battaglia, C. Blundell, A. Juh´ asz, M. Lackenby, G. Williamson, D. Hassabis, P. Kohli,Ad- vancing mathematics by guiding human intuition with AI, Nature,600(2021), 70-74

    2021

  19. [19]

    M. J. Dyer,Hecke algebras and reflections in Coxeter groups, Ph. D. Thesis, University of Sydney, 1987

    1987

  20. [20]

    Bruhat graph

    M. J. Dyer,On the “Bruhat graph”of a Coxeter system, Compos. Math.,78(1991), 185-191

    1991

  21. [21]

    Esposito, M

    F. Esposito, M. Marietti,Flipclasses and Combinatorial Invariance for Kazhdan–Lusztig poly- nomials, Sel. Math. New Ser. 31, 98 (2025). https://doi.org/10.1007/s00029-025-01099-6

    work page doi:10.1007/s00029-025-01099-6 2025

  22. [22]

    Esposito, M

    F. Esposito, M. Marietti,A note on Combinatorial Invariance of Kazhdan–Lusztig polynomials (with an appendix by G. T. Barkley and C. Gaetz), preprint arXiv:2404.12834v3

    arXiv

  23. [23]

    Esposito, M

    F. Esposito, M. Marietti, Stella,Flip Combinatorial Invariance and Weyl Groups, preprint arXiv:2509.16433 [math.CO]

    arXiv

  24. [24]

    Gurevich, C

    M. Gurevich, C. Wang,Parabolic recursions for Kazhdan-Lusztig polynomials and the hyper- cube decomposition, Sel. Math. New Ser. 30, 81 (2024). https://doi.org/10.1007/s00029-024- 00972-0

    work page doi:10.1007/s00029-024- 2024

  25. [25]

    Kazhdan, G

    D. Kazhdan, G. Lusztig,Representations of Coxeter groups and Hecke algebras, Invent. Math. 53(1979), 165-184

    1979

  26. [26]

    Marietti,Algebraic and combinatorial properties of zircons, J

    M. Marietti,Algebraic and combinatorial properties of zircons, J. Algebraic Combin.,26(2007), 363-382

    2007

  27. [27]

    Marietti,Special matchings and parabolic Kazhdan–Lusztig polynomials, Trans

    M. Marietti,Special matchings and parabolic Kazhdan–Lusztig polynomials, Trans. Amer. Math. Soc.368(2016), no. 7, 5247-5269. SPECIAL MATCHINGS, BRENTI’S CONJECTURE, AND THE CIC 39

    2016

  28. [28]

    Marietti,The combinatorial invariance conjecture for parabolic Kazhdan–Lusztig polyno- mials of lower intervals, Advances in Math.335(2018), 180-210

    M. Marietti,The combinatorial invariance conjecture for parabolic Kazhdan–Lusztig polyno- mials of lower intervals, Advances in Math.335(2018), 180-210

    2018

  29. [29]

    Marietti,Kazhdan–Lusztig R-polynomials for pircons, J

    M. Marietti,Kazhdan–Lusztig R-polynomials for pircons, J. Algebra534(2019), 245–272. Fabrizio Caselli, Dipartimento di Matematica, Universit`a degli Studi di Bologna, Piazza di Porta San Donato 5, 40126 Bologna, Italy Mario Marietti, Dipartimento di Ingegneria Industriale e Scienze Matematiche, Universit`a Politecnica delle Marche, via Brecce Bianche, 601...

    2019