Informal Friday Seminar: Burrull -- The Bruhat graph of a Coxeter group

Let (W,S) be a Coxeter system with length function l.  Here arises a very natural
question in combinatorics.  For each positive integer n, how many types of intervals [x,
y] of length n (i.e.  l(y)-l(x)=n) are possible? 

In 1991, Dyer provided a partial answer for finite Coxeter groups by introducing the
"Bruhat graph" associated to (W, S) [Dye91].  He proved that there are only finitely
many types of intervals of fixed length.  On the other hand, the seminal paper [KL79]
introduced for elements x,y of the Coxeter group the so-called Kazhdan-Lusztig
polynomials Px,y(q).  In this paper, they conjectured that the polynomials Px,y only
depend on the poset type of [x, y], this conjecture is known as the "combinatorial
invariance conjecture".  Dyer’s answer gives support to this conjecture, which is
nowadays - even in finite type - a major unsolved problem in combinatorics.  

In this talk I will define the Bruhat graph (which carries more information than the
Bruhat order) and reflection subgroups.  I will state the main theorem of [Dye90] and
other useful propositions.  Finally, I will explain the proof of the main result of
[Dye91] thus providing an answer to our original question.  

I will provide many illustrative examples to keep your feet on the ground during the
talk.