Séminaire Lotharingien de Combinatoire, 89B.86 (2023), 8 pp.
Grant T. Barkley and Christian Gaetz
Combinatorial Invariance for Lower Intervals Using Hypercube Decompositions
Abstract.
We give a new proof of the combinatorial invariance conjecture for lower intervals of the symmetric group. This conjecture posits that Kazhdan--Lusztig polynomials associated to intervals in the Bruhat order depend only on the poset structure of the interval. For lower intervals of the symmetric group, this was originally shown by Brenti using special matchings. Our proof uses a different combinatorial structure, called a hypercube decomposition, which was recently introduced by Blundell, Buesing, Davies, Veli{\v{c}}kovi{\'{c}}, and Williamson as an approach to proving combinatorial invariance for arbitrary intervals. Instead of studying the Kazhdan--Lusztig polynomials directly, we apply hypercube decompositions to the related family of
R~-polynomials. We prove a new, explicit combinatorial recurrence for R~-polynomials using certain hypercube decompositions.
Received: November 15, 2022.
Accepted: February 20, 2023.
Final version: April 1, 2023.