Weak generalized lifting property, Bruhat intervals, and Coxeter matroids

Fabrizio Caselli, Michele D’Adderio, Mario MariettiUniversità Politecnica Delle Marche (Università Politecnica Delle Marche) 2021 · DOI

TL;DR

This paper introduces a "weak generalized lifting property" that applies to all finite Coxeter groups. This property is then used to prove that any parabolic Bruhat interval within a finite Coxeter group is a "Coxeter matroid," a significant generalization of standard matroids. The work also sheds light on the geometric structure of associated polytopes.

What Problem Does This Paper Address?

The paper builds upon existing work on "Coxeter matroids" and "Bruhat interval polytopes," primarily developed for the symmetric group. While these concepts have been studied, their generalization to arbitrary finite Coxeter groups has been limited. Specifically, a key property called the "generalized lifting property" was known to hold only for finite, simply-laced Coxeter groups (like the symmetric group). This paper addresses the question of whether a more general version of this property exists and if it can be used to establish that all parabolic Bruhat intervals in any finite Coxeter group are Coxeter matroids. This would be a significant step towards a unified understanding of these combinatorial structures across a broader class of groups.

Methods

The core of the paper lies in introducing and proving a "weak generalized lifting property." This property, unlike its predecessor, holds for all finite Coxeter groups. The proof relies on the theory of "reflection orderings" on the set of positive roots within a Coxeter system.

The authors then leverage this weak generalized lifting property to prove their main result: that every parabolic Bruhat interval in a finite Coxeter group is a Coxeter matroid. This is achieved by showing that the associated polytopes, called "Bruhat interval polytopes," satisfy certain geometric and combinatorial conditions that define Coxeter matroids. The paper also develops tools from convex geometry to extend results from the standard (non-parabolic) case to the more general parabolic setting.

Key techniques include:

  • Reflection Orderings: A total ordering on reflections that satisfies specific properties related to root combinations.
  • Convex Geometry: Utilizing concepts like convex hulls, faces of polytopes, and hyperplane separation theorems.
  • Induction: Employing inductive arguments on the length of intervals or relationships between elements.
  • Geometric Representation: Working with the standard geometric representation of Coxeter groups on a vector space.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Universality of the Weak Lifting Property: The discovery that a weaker form of the generalized lifting property holds for all finite Coxeter groups is a major breakthrough. This suggests a more fundamental and widespread combinatorial phenomenon than previously understood.
  • Coxeter Matroids for All Parabolic Intervals: The paper establishes that the concept of a Coxeter matroid, a generalization of standard matroids, applies to all parabolic Bruhat intervals in finite Coxeter groups. This unifies a significant class of combinatorial objects.
  • Geometric Structure of Bruhat Intervals: The work provides a deeper understanding of the structure of Bruhat interval polytopes, showing that their faces are themselves Bruhat interval polytopes. This reveals a recursive or fractal-like nature in their geometry.
  • Combinatorial Nature of Proofs: The authors emphasize that their proofs are primarily combinatorial and do not rely on the classification of Coxeter groups, making the results broadly applicable.

Key Results

  • Theorem 3.5 (Weak Generalized Lifting Property): For any finite Coxeter system (W, S) and any $u < v \in W$, there exist positive roots $\alpha$ and $\beta$ such that $\alpha \in \text{cone}(R)$ and $\beta \in \text{cone}(R')$, where $R = \{\alpha_t \in \Phi^+ : u < tv < v\}$ and $R' = \{\alpha_t \in \Phi^+ : u < tu \le v\}$. This property holds universally for finite Coxeter groups.
  • Theorem 4.4: For any finite Coxeter system (W, S) and any $u \le v \in W$, the Bruhat interval $[u, v]$ is a Coxeter matroid.
  • Theorem 5.1: Every face of a Bruhat interval polytope $\Delta_{[u,v]}(p)$ is itself a Bruhat interval polytope $\Delta_{[x,y]}(p)$ for some $u \le x \le y \le v$.
  • Theorem 6.3: For any finite Coxeter system (W, S), $J \subseteq S$, and $A < B \in W/W_J$, the parabolic interval $[A, B]$ is a Coxeter matroid, and its associated polytope's faces are also parabolic Bruhat interval polytopes.

Limitations and Future Work

  • Focus on Finite Coxeter Groups: The results presented are for finite Coxeter groups. Extending these findings to infinite Coxeter groups would be a natural next step.
  • Combinatorial vs. Algorithmic: While the proofs are combinatorial, the paper doesn't explicitly focus on algorithmic aspects. Developing efficient algorithms for constructing or manipulating these structures could be a future direction.
  • Specific Coxeter Group Types: While the proofs are general, specific examples and computations for particular types of Coxeter groups (beyond the symmetric group) could offer further intuition and applications.
  • Further Exploration of Polytopes: The paper touches upon the combinatorial properties of associated polytopes. A deeper investigation into their geometric and topological features could be fruitful.

Summary updated

Abstract

We provide a weaker version of the generalized lifting property that holds in complete generality for all Coxeter groups, and we use it to show that every parabolic Bruhat interval of a finite Coxeter group is a Coxeter matroid. We also describe some combinatorial properties of the associated polytopes.
BibTeX
@inproceedings{caselli2021weak,
  author = {Fabrizio Caselli and Michele D’Adderio and Mario Marietti},
  title = {{Weak generalized lifting property, Bruhat intervals, and Coxeter matroids}},
  booktitle = {Università Politecnica Delle Marche (Università Politecnica Delle Marche)},
  year = {2021},
  doi = {10.1093/imrn/rnaa124},
}

Loading related content...

Figure