# Subword complex¶

Fix a Coxeter system $$(W,S)$$. The subword complex $$\mathcal{SC}(Q,w)$$ associated to a word $$Q \in S^*$$ and an element $$w \in W$$ is the simplicial complex whose ground set is the set of positions in $$Q$$ and whose facets are complements of sets of positions defining a reduced expression for $$w$$.

A subword complex is a shellable sphere if and only if the Demazure product of $$Q$$ equals $$w$$, otherwise it is a shellable ball.

The code is optimized to be used with ReflectionGroup, it works as well with CoxeterGroup, but many methods fail for WeylGroup.

EXAMPLES:

sage: W = ReflectionGroup(['A',3]); I = list(W.index_set())         # optional - gap3
sage: Q = I + W.w0.coxeter_sorting_word(I); Q                       # optional - gap3
[1, 2, 3, 1, 2, 3, 1, 2, 1]

sage: S = SubwordComplex(Q,W.w0)                                    # optional - gap3
sage: for F in S: print("{} {}".format(F, F.root_configuration()))                 # optional - gap3
(0, 1, 2) [(1, 0, 0), (0, 1, 0), (0, 0, 1)]
(0, 1, 8) [(1, 0, 0), (0, 1, 0), (0, 0, -1)]
(0, 2, 6) [(1, 0, 0), (0, 1, 1), (0, -1, 0)]
(0, 6, 7) [(1, 0, 0), (0, 0, 1), (0, -1, -1)]
(0, 7, 8) [(1, 0, 0), (0, -1, 0), (0, 0, -1)]
(1, 2, 3) [(1, 1, 0), (0, 0, 1), (-1, 0, 0)]
(1, 3, 8) [(1, 1, 0), (-1, 0, 0), (0, 0, -1)]
(2, 3, 4) [(1, 1, 1), (0, 1, 0), (-1, -1, 0)]
(2, 4, 6) [(1, 1, 1), (-1, 0, 0), (0, -1, 0)]
(3, 4, 5) [(0, 1, 0), (0, 0, 1), (-1, -1, -1)]
(3, 5, 8) [(0, 1, 0), (-1, -1, 0), (0, 0, -1)]
(4, 5, 6) [(0, 1, 1), (-1, -1, -1), (0, -1, 0)]
(5, 6, 7) [(-1, 0, 0), (0, 0, 1), (0, -1, -1)]
(5, 7, 8) [(-1, 0, 0), (0, -1, 0), (0, 0, -1)]


Testing that the implementation also works with CoxeterGroup:

sage: W = CoxeterGroup(['A',3]); I = list(W.index_set())
sage: Q = I + W.w0.coxeter_sorting_word(I); Q
[1, 2, 3, 1, 2, 3, 1, 2, 1]
sage: S = SubwordComplex(Q,W.w0); S
Subword complex of type ['A', 3] for Q = (1, 2, 3, 1, 2, 3, 1, 2, 1) and pi = [1, 2, 3, 1, 2, 1]
sage: P = S.increasing_flip_poset(); P; len(P.cover_relations())
Finite poset containing 14 elements
21


The root configuration works:

sage: for F in S: print("{} {}".format(F, F.root_configuration()))
(0, 1, 2) [(1, 0, 0), (0, 1, 0), (0, 0, 1)]
(0, 1, 8) [(1, 0, 0), (0, 1, 0), (0, 0, -1)]
(0, 2, 6) [(1, 0, 0), (0, 1, 1), (0, -1, 0)]
(0, 6, 7) [(1, 0, 0), (0, 0, 1), (0, -1, -1)]
(0, 7, 8) [(1, 0, 0), (0, -1, 0), (0, 0, -1)]
(1, 2, 3) [(1, 1, 0), (0, 0, 1), (-1, 0, 0)]
(1, 3, 8) [(1, 1, 0), (-1, 0, 0), (0, 0, -1)]
(2, 3, 4) [(1, 1, 1), (0, 1, 0), (-1, -1, 0)]
(2, 4, 6) [(1, 1, 1), (-1, 0, 0), (0, -1, 0)]
(3, 4, 5) [(0, 1, 0), (0, 0, 1), (-1, -1, -1)]
(3, 5, 8) [(0, 1, 0), (-1, -1, 0), (0, 0, -1)]
(4, 5, 6) [(0, 1, 1), (-1, -1, -1), (0, -1, 0)]
(5, 6, 7) [(-1, 0, 0), (0, 0, 1), (0, -1, -1)]
(5, 7, 8) [(-1, 0, 0), (0, -1, 0), (0, 0, -1)]


And the weight configuration also works:

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1],w)
sage: F = SC([1,2])
sage: F.extended_weight_configuration()
[(4/3, 2/3), (2/3, 4/3), (-2/3, 2/3), (2/3, 4/3), (-2/3, 2/3)]
sage: F.extended_weight_configuration(coefficients=(1,2))
[(4/3, 2/3), (4/3, 8/3), (-2/3, 2/3), (4/3, 8/3), (-2/3, 2/3)]


One finally can compute the brick polytope, using all functionality on weight configurations, though it does not realize to live in real space:

sage: W = CoxeterGroup(['A',3]); I = list(W.index_set())
sage: Q = I + W.w0.coxeter_sorting_word(I)
sage: S = SubwordComplex(Q,W.w0)
sage: S.brick_polytope()
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 14 vertices

sage: W = CoxeterGroup(['H',3]); I = list(W.index_set())
sage: Q = I + W.w0.coxeter_sorting_word(I)
sage: S = SubwordComplex(Q,W.w0)
sage: S.brick_polytope()
doctest:...: RuntimeWarning: the polytope is build with rational vertices
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 32 vertices


AUTHORS:

• Christian Stump: initial version
• Vincent Pilaud: greedy flip algorithm, minor improvements, documentation

REFERENCES:

 [KnuMil] Knutson and Miller. Subword complexes in Coxeter groups. Adv. Math., 184(1):161-176, 2004.
 [PilStu] (1, 2) Pilaud and Stump. Brick polytopes of spherical subword complexes and generalized associahedra. Adv. Math. 276:1-61, 2015.
class sage.combinat.subword_complex.SubwordComplex(Q, w, algorithm='inductive')

Fix a Coxeter system $$(W,S)$$. The subword complex $$\mathcal{SC}(Q,w)$$ associated to a word $$Q \in S^*$$ and an element $$w \in W$$ is the simplicial complex whose ground set is the set of positions in $$Q$$ and whose facets are complements of sets of positions defining a reduced expression for $$w$$.

A subword complex is a shellable sphere if and only if the Demazure product of $$Q$$ equals $$w$$, otherwise it is a shellable ball.

Warning

This implementation only works for groups build using CoxeterGroup, and does not work with groups build using WeylGroup.

EXAMPLES:

As an example, dual associahedra are subword complexes in type $$A_{n-1}$$ given by the word $$[1, \dots, n, 1, \dots, n, 1, \dots, n-1, \dots, 1, 2, 1]$$ and the permutation $$w_0$$.

sage: W = ReflectionGroup(['A',2])                              # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                          # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], w); SC                   # optional - gap3
Subword complex of type ['A', 2] for Q = (1, 2, 1, 2, 1) and pi = [1, 2, 1]
sage: SC.facets()                                               # optional - gap3
[(0, 1), (0, 4), (1, 2), (2, 3), (3, 4)]

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1], w); SC
Subword complex of type ['A', 2] for Q = (1, 2, 1, 2, 1) and pi = [1, 2, 1]
sage: SC.facets()
[(0, 1), (0, 4), (1, 2), (2, 3), (3, 4)]


REFERENCES: [KnuMil], [PilStu]

Element

alias of SubwordComplexFacet

barycenter()

Return the barycenter of the brick polytope of self.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], W.w0)                # optional - gap3
sage: SC.barycenter()                                       # optional - gap3
(2/3, 4/3)

sage: W = CoxeterGroup(['A',2])
sage: SC = SubwordComplex([1,2,1,2,1], W.w0)
sage: SC.barycenter()
(4/3, 8/3)

brick_fan()

Return the brick fan of self.

It is the normal fan of the brick polytope of self. It is formed by the cones generated by the weight configurations of the facets of self.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], w)                   # optional - gap3
sage: SC.brick_fan()                                        # optional - gap3
Rational polyhedral fan in 2-d lattice N

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1], w)
sage: SC.brick_fan()
Rational polyhedral fan in 2-d lattice N

brick_polytope(coefficients=None)

Return the brick polytope of self.

This polytope is the convex hull of the brick vectors of self.

INPUT:

• coefficients – (optional) a list of coefficients used to scale the fundamental weights

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], W.w0)                # optional - gap3
sage: X = SC.brick_polytope(); X                            # optional - gap3
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 5 vertices

sage: Y = SC.brick_polytope(coefficients=[1,2]); Y          # optional - gap3
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 5 vertices

sage: X == Y                                                # optional - gap3
False

sage: W = CoxeterGroup(['A',2])
sage: SC = SubwordComplex([1,2,1,2,1], W.w0)
sage: X = SC.brick_polytope(); X
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 5 vertices

sage: W = ReflectionGroup(['H',3])                          # optional - gap3
sage: c = W.index_set(); Q = c + tuple(W.w0.coxeter_sorting_word(c))    # optional - gap3
sage: SC = SubwordComplex(Q,W.w0)                           # optional - gap3
sage: SC.brick_polytope()                                   # optional - gap3
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 32 vertices

brick_vectors(coefficients=None)

Return the list of all brick vectors of facets of self.

INPUT:

• coefficients – (optional) a list of coefficients used to scale the fundamental weights

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], W.w0)                # optional - gap3
sage: SC.brick_vectors()                                    # optional - gap3
[(5/3, 7/3), (5/3, 1/3), (2/3, 7/3), (-1/3, 4/3), (-1/3, 1/3)]
sage: SC.brick_vectors(coefficients=(1,2))                  # optional - gap3
[(7/3, 11/3), (7/3, 2/3), (4/3, 11/3), (-2/3, 5/3), (-2/3, 2/3)]

sage: W = CoxeterGroup(['A',2])
sage: SC = SubwordComplex([1,2,1,2,1], W.w0)
sage: SC.brick_vectors()
[(10/3, 14/3), (10/3, 2/3), (4/3, 14/3), (-2/3, 8/3), (-2/3, 2/3)]
sage: SC.brick_vectors(coefficients=(1,2))
[(14/3, 22/3), (14/3, 4/3), (8/3, 22/3), (-4/3, 10/3), (-4/3, 4/3)]

cartan_type()

Return the Cartan type of self.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], w)                   # optional - gap3
sage: SC.cartan_type()                                      # optional - gap3
['A', 2]

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1], w)
sage: SC.cartan_type()
['A', 2]

cover_relations(label=False)

Return the set of cover relations in the associated poset.

INPUT:

• label – boolean (default False) whether or not to label the cover relations by the position of flip

OUTPUT:

a list of pairs of facets

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], W.w0)                # optional - gap3
sage: sorted(SC.cover_relations())                          # optional - gap3
[((0, 1), (0, 4)),
((0, 1), (1, 2)),
((0, 4), (3, 4)),
((1, 2), (2, 3)),
((2, 3), (3, 4))]

sage: W = CoxeterGroup(['A',2])
sage: SC = SubwordComplex([1,2,1,2,1], W.w0)
sage: sorted(SC.cover_relations())
[((0, 1), (0, 4)),
((0, 1), (1, 2)),
((0, 4), (3, 4)),
((1, 2), (2, 3)),
((2, 3), (3, 4))]

dimension()

Return the dimension of self.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], W.w0)                # optional - gap3
sage: SC.dimension()                                        # optional - gap3
1

sage: W = CoxeterGroup(['A',2])
sage: SC = SubwordComplex([1,2,1,2,1], W.w0)
sage: SC.dimension()
1

facets()

Return all facets of self.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], w)                   # optional - gap3
sage: SC.facets()                                           # optional - gap3
[(0, 1), (0, 4), (1, 2), (2, 3), (3, 4)]

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1], w)
sage: SC.facets()
[(0, 1), (0, 4), (1, 2), (2, 3), (3, 4)]

greedy_facet(side='positive')

Return the negative (or positive) greedy facet of self.

This is the lexicographically last (or first) facet of self.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], w)                   # optional - gap3
sage: SC.greedy_facet(side="positive")                      # optional - gap3
(0, 1)
sage: SC.greedy_facet(side="negative")                      # optional - gap3
(3, 4)

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1], w)
sage: SC.greedy_facet(side="positive")
(0, 1)
sage: SC.greedy_facet(side="negative")
(3, 4)

group()

Return the group associated to self.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], w)                   # optional - gap3
sage: SC.group()                                            # optional - gap3
Irreducible real reflection group of rank 2 and type A2

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1], w)
sage: SC.group()
Finite Coxeter group over Integer Ring with Coxeter matrix:
[1 3]
[3 1]

increasing_flip_graph(label=True)

Return the increasing flip graph of the subword complex.

OUTPUT:

a directed graph

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], W.w0)                # optional - gap3
sage: SC.increasing_flip_graph()                            # optional - gap3
Digraph on 5 vertices

sage: W = CoxeterGroup(['A',2])
sage: SC = SubwordComplex([1,2,1,2,1], W.w0)
sage: SC.increasing_flip_graph()
Digraph on 5 vertices

increasing_flip_poset()

Return the increasing flip poset of the subword complex.

OUTPUT:

a poset

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], W.w0)                # optional - gap3
sage: SC.increasing_flip_poset()                            # optional - gap3
Finite poset containing 5 elements

sage: W = CoxeterGroup(['A',2])
sage: SC = SubwordComplex([1,2,1,2,1], W.w0)
sage: SC.increasing_flip_poset()
Finite poset containing 5 elements

interval(I, J)

Return the interval [I,J] in the increasing flip graph subword complex.

INPUT:

• I, J – two facets

OUTPUT:

a set of facets

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], W.w0)                # optional - gap3
sage: F = SC([1,2])                                         # optional - gap3
sage: SC.interval(F, F)                                     # optional - gap3
{(1, 2)}

sage: W = CoxeterGroup(['A',2])
sage: SC = SubwordComplex([1,2,1,2,1], W.w0)
sage: F = SC([1,2])
sage: SC.interval(F, F)
{(1, 2)}

is_ball()

Return True if the subword complex self is a ball.

This is the case if and only if it is not a sphere.

EXAMPLES:

sage: W = ReflectionGroup(['A',3])                          # optional - gap3
sage: w = W.from_reduced_word([2,3,2])                      # optional - gap3
sage: SC = SubwordComplex([3,2,3,2,3], w)                   # optional - gap3
sage: SC.is_ball()                                          # optional - gap3
False

sage: SC = SubwordComplex([3,2,1,3,2,3], w)                 # optional - gap3
sage: SC.is_ball()                                          # optional - gap3
True

sage: W = CoxeterGroup(['A',3])
sage: w = W.from_reduced_word([2,3,2])
sage: SC = SubwordComplex([3,2,3,2,3], w)
sage: SC.is_ball()
False

is_double_root_free()

Return True if self is double-root-free.

This means that the root configurations of all facets do not contain a root twice.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], w)                   # optional - gap3
sage: SC.is_double_root_free()                              # optional - gap3
True

sage: SC = SubwordComplex([1,1,2,2,1,1], w)                 # optional - gap3
sage: SC.is_double_root_free()                              # optional - gap3
True

sage: SC = SubwordComplex([1,2,1,2,1,2], w)                 # optional - gap3
sage: SC.is_double_root_free()                              # optional - gap3
False

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1], w)
sage: SC.is_double_root_free()
True

is_pure()

Return True since all subword complexes are pure.

EXAMPLES:

sage: W = ReflectionGroup(['A',3])                          # optional - gap3
sage: w = W.from_reduced_word([2,3,2])                      # optional - gap3
sage: SC = SubwordComplex([3,2,3,2,3], w)                   # optional - gap3
sage: SC.is_pure()                                          # optional - gap3
True

sage: W = CoxeterGroup(['A',3])
sage: w = W.from_reduced_word([2,3,2])
sage: SC = SubwordComplex([3,2,3,2,3], w)
sage: SC.is_pure()
True

is_root_independent()

Return True if self is root-independent.

This means that the root configuration of any (or equivalently all) facets is linearly independent.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], W.w0)                # optional - gap3
sage: SC.is_root_independent()                              # optional - gap3
True

sage: SC = SubwordComplex([1,2,1,2,1,2], W.w0)              # optional - gap3
sage: SC.is_root_independent()                              # optional - gap3
False

sage: W = CoxeterGroup(['A',2])
sage: SC = SubwordComplex([1,2,1,2,1], W.w0)
sage: SC.is_root_independent()
True

is_sphere()

Return True if the subword complex self is a sphere.

EXAMPLES:

sage: W = ReflectionGroup(['A',3])                          # optional - gap3
sage: w = W.from_reduced_word([2,3,2])                      # optional - gap3
sage: SC = SubwordComplex([3,2,3,2,3], w)                   # optional - gap3
sage: SC.is_sphere()                                        # optional - gap3
True

sage: SC = SubwordComplex([3,2,1,3,2,3], w)                 # optional - gap3
sage: SC.is_sphere()                                        # optional - gap3
False

sage: W = CoxeterGroup(['A',3])
sage: w = W.from_reduced_word([2,3,2])
sage: SC = SubwordComplex([3,2,3,2,3], w)
sage: SC.is_sphere()
True

kappa_preimages()

Return a dictionary containing facets of self as keys, and list of elements of self.group() as values.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], w)                   # optional - gap3
sage: kappa = SC.kappa_preimages()                          # optional - gap3
sage: for F in SC: print("{} {}".format(F, [w.reduced_word() for w in kappa[F]]))    # optional - gap3
(0, 1) [[]]
(0, 4) [[2], [2, 1]]
(1, 2) [[1]]
(2, 3) [[1, 2]]
(3, 4) [[1, 2, 1]]

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1], w)
sage: kappa = SC.kappa_preimages()
sage: for F in SC: print("{} {}".format(F, [w.reduced_word() for w in kappa[F]]))
(0, 1) [[]]
(0, 4) [[2], [2, 1]]
(1, 2) [[1]]
(2, 3) [[1, 2]]
(3, 4) [[1, 2, 1]]

minkowski_summand(i)

Return the $$i$$ th Minkowski summand of self.

INPUT:

$$i$$ – an integer defining a position in the word $$Q$$

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], W.w0)                # optional - gap3
sage: SC.minkowski_summand(1)                               # optional - gap3
A 0-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex

sage: W = CoxeterGroup(['A',2])
sage: SC = SubwordComplex([1,2,1,2,1], W.w0)
sage: SC.minkowski_summand(1)
A 0-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex

pi()

Return the element in the Coxeter group associated to self.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], w)                   # optional - gap3
sage: SC.pi().reduced_word()                                # optional - gap3
[1, 2, 1]

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1], w)
sage: SC.pi().reduced_word()
[1, 2, 1]

word()

Return the word in the simple generators associated to self.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], w)                   # optional - gap3
sage: SC.word()                                             # optional - gap3
(1, 2, 1, 2, 1)

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1], w)
sage: SC.word()
(1, 2, 1, 2, 1)

class sage.combinat.subword_complex.SubwordComplexFacet(parent, positions, facet_test=True)

A facet of a subword complex.

Facets of the subword complex $$\mathcal{SC}(Q,w)$$ are complements of sets of positions in $$Q$$ defining a reduced expression for $$w$$.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                              # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                          # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1], w)                       # optional - gap3
sage: F = SC[0]; F                                              # optional - gap3
(0, 1)

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1], w)
sage: F = SC[0]; F
(0, 1)

brick_vector(coefficients=None)

Return the brick vector of self.

This is the sum of the weight vectors in the extended weight configuration.

INPUT:

• coefficients – (optional) a list of coefficients used to scale the fundamental weights

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1],w)                    # optional - gap3
sage: F = SC([1,2]); F                                      # optional - gap3
(1, 2)
sage: F.extended_weight_configuration()                     # optional - gap3
[(2/3, 1/3), (1/3, 2/3), (-1/3, 1/3), (1/3, 2/3), (-1/3, 1/3)]
sage: F.brick_vector()                                      # optional - gap3
(2/3, 7/3)
sage: F.brick_vector(coefficients=[1,2])                    # optional - gap3
(4/3, 11/3)

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1],w)
sage: F = SC([1,2])
sage: F.brick_vector()
(4/3, 14/3)
sage: F.brick_vector(coefficients=[1,2])
(8/3, 22/3)

extended_root_configuration()

Return the extended root configuration of self.

Let $$Q = q_1 \dots q_m \in S^*$$ and $$w \in W$$. The extended root configuration of a facet $$I$$ of $$\mathcal{SC}(Q,w)$$ is the sequence $$\mathsf{r}(I, 1), \dots, \mathsf{r}(I, m)$$ of roots defined by $$\mathsf{r}(I, k) = \Pi Q_{[k-1] \smallsetminus I} (\alpha_{q_k})$$, where $$\Pi Q_{[k-1] \smallsetminus I}$$ is the product of the simple reflections $$q_i$$ for $$i \in [k-1] \smallsetminus I$$ in this order.

The extended root configuration is used to perform flips efficiently.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1],w)                    # optional - gap3
sage: F = SC([1,2]); F                                      # optional - gap3
(1, 2)
sage: F.extended_root_configuration()                       # optional - gap3
[(1, 0), (1, 1), (-1, 0), (1, 1), (0, 1)]

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1],w)
sage: F = SC([1,2]); F
(1, 2)
sage: F.extended_root_configuration()
[(1, 0), (1, 1), (-1, 0), (1, 1), (0, 1)]

extended_weight_configuration(coefficients=None)

Return the extended weight configuration of self.

Let $$Q = q_1 \dots q_m \in S^*$$ and $$w \in W$$. The extended weight configuration of a facet $$I$$ of $$\mathcal{SC}(Q,w)$$ is the sequence $$\mathsf{w}(I, 1), \dots, \mathsf{w}(I, m)$$ of weights defined by $$\mathsf{w}(I, k) = \Pi Q_{[k-1] \smallsetminus I} (\omega_{q_k})$$, where $$\Pi Q_{[k-1] \smallsetminus I}$$ is the product of the simple reflections $$q_i$$ for $$i \in [k-1] \smallsetminus I$$ in this order.

The extended weight configuration is used to compute the brick vector.

INPUT:

• coefficients – (optional) a list of coefficients used to scale the fundamental weights

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1],w)                    # optional - gap3
sage: F = SC([1,2])                                         # optional - gap3
sage: F.extended_weight_configuration()                     # optional - gap3
[(2/3, 1/3), (1/3, 2/3), (-1/3, 1/3), (1/3, 2/3), (-1/3, 1/3)]
sage: F.extended_weight_configuration(coefficients=(1,2))   # optional - gap3
[(2/3, 1/3), (2/3, 4/3), (-1/3, 1/3), (2/3, 4/3), (-1/3, 1/3)]

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1],w)
sage: F = SC([1,2])
sage: F.extended_weight_configuration()
[(4/3, 2/3), (2/3, 4/3), (-2/3, 2/3), (2/3, 4/3), (-2/3, 2/3)]
sage: F.extended_weight_configuration(coefficients=(1,2))
[(4/3, 2/3), (4/3, 8/3), (-2/3, 2/3), (4/3, 8/3), (-2/3, 2/3)]

flip(i, return_position=False)

Return the facet obtained after flipping position i in self.

INPUT:

• i – position in the word $$Q$$ (integer).
• return_position – boolean (default: False) tells whether the new position should be returned as well.

OUTPUT:

• The new subword complex facet.
• The new position if return_position is True.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1],w)                    # optional - gap3
sage: F = SC([1,2]); F                                      # optional - gap3
(1, 2)
sage: F.flip(1)                                             # optional - gap3
(2, 3)
sage: F.flip(1, return_position=True)                       # optional - gap3
((2, 3), 3)

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1],w)
sage: F = SC([1,2]); F
(1, 2)
sage: F.flip(1)
(2, 3)
sage: F.flip(1, return_position=True)
((2, 3), 3)

is_vertex()

Return True if self is a vertex of the brick polytope of self.parent.

A facet is a vertex of the brick polytope if its root cone is pointed. Note that this property is always satisfied for root-independent subword complexes.

EXAMPLES:

sage: W = ReflectionGroup(['A',1])                          # optional - gap3
sage: w = W.from_reduced_word([1])                          # optional - gap3
sage: SC = SubwordComplex([1,1,1],w)                        # optional - gap3
sage: F = SC([0,1]); F.is_vertex()                          # optional - gap3
True
sage: F = SC([0,2]); F.is_vertex()                          # optional - gap3
False

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1,2,1],w)                # optional - gap3
sage: F = SC([0,1,2,3]); F.is_vertex()                      # optional - gap3
True
sage: F = SC([0,1,2,6]); F.is_vertex()                      # optional - gap3
False

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1,2,1],w)
sage: F = SC([0,1,2,3]); F.is_vertex()
True
sage: F = SC([0,1,2,6]); F.is_vertex()
False

kappa_preimage()

Return the fiber of self under the $$\kappa$$ map.

The $$\kappa$$ map sends an element $$w \in W$$ to the unique facet of $$I \in \mathcal{SC}(Q,w)$$ such that the root configuration of $$I$$ is contained in $$w(\Phi^+)$$. In other words, $$w$$ is in the preimage of self under $$\kappa$$ if and only if $$w^{-1}$$ sends every root in the root configuration to a positive root.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1],w)                    # optional - gap3

sage: F = SC([1,2]); F                                      # optional - gap3
(1, 2)
sage: F.kappa_preimage()                                    # optional - gap3
[(1,4)(2,3)(5,6)]

sage: F = SC([0,4]); F                                      # optional - gap3
(0, 4)
sage: F.kappa_preimage()                                    # optional - gap3
[(1,3)(2,5)(4,6), (1,2,6)(3,4,5)]

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1],w)

sage: F = SC([1,2]); F
(1, 2)
sage: F.kappa_preimage()
[
[-1  1]
[ 0  1]
]

sage: F = SC([0,4]); F
(0, 4)
sage: F.kappa_preimage()
[
[ 1  0]  [-1  1]
[ 1 -1], [-1  0]
]

plot(list_colors=None, labels=[], thickness=3, fontsize=14, shift=(0, 0), compact=False, roots=True, **args)

In type $$A$$ or $$B$$, plot a pseudoline arrangement representing the facet self.

Pseudoline arrangements are graphical representations of facets of types A or B subword complexes.

INPUT:

• list_colors – list (default: []) to change the colors of the pseudolines.
• labels – list (default: []) to change the labels of the pseudolines.
• thickness – integer (default: 3) for the thickness of the pseudolines.
• fontsize – integer (default: 14) for the size of the font used for labels.
• shift – couple of coordinates (default: (0,0)) to change the origin.
• compact – boolean (default: False) to require a more compact representation.
• roots – boolean (default: True) to print the extended root configuration.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1],w)                    # optional - gap3
sage: F = SC([1,2]); F.plot()                               # optional - gap3
Graphics object consisting of 26 graphics primitives

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1],w)
sage: F = SC([1,2]); F.plot()
Graphics object consisting of 26 graphics primitives

sage: W = ReflectionGroup(['B',3])                          # optional - gap3
sage: c = W.from_reduced_word([1,2,3])                      # optional - gap3
sage: Q = c.reduced_word()*2 + W.w0.coxeter_sorting_word(c) # optional - gap3
sage: SC = SubwordComplex(Q, W.w0)                          # optional - gap3
sage: F = SC[15]; F.plot()                                  # optional - gap3
Graphics object consisting of 52 graphics primitives


REFERENCES: [PilStu]

root_cone()

Return the polyhedral cone generated by the root configuration of self.

EXAMPLES:

sage: W = ReflectionGroup(['A',1])                          # optional - gap3
sage: w = W.from_reduced_word([1])                          # optional - gap3
sage: SC = SubwordComplex([1,1,1],w)                        # optional - gap3
sage: F = SC([0,2]); F.root_cone()                          # optional - gap3
1-d cone in 1-d lattice N

sage: W = CoxeterGroup(['A',1])
sage: w = W.from_reduced_word([1])
sage: SC = SubwordComplex([1,1,1],w)
sage: F = SC([0,2]); F.root_cone()
1-d cone in 1-d lattice N

root_configuration()

Return the root configuration of self.

Let $$Q = q_1 \dots q_m \in S^*$$ and $$w \in W$$. The root configuration of a facet $$I = [i_1, \dots, i_n]$$ of $$\mathcal{SC}(Q,w)$$ is the sequence $$\mathsf{r}(I, i_1), \dots, \mathsf{r}(I, i_n)$$ of roots defined by $$\mathsf{r}(I, k) = \Pi Q_{[k-1] \smallsetminus I} (\alpha_{q_k})$$, where $$\Pi Q_{[k-1] \smallsetminus I}$$ is the product of the simple reflections $$q_i$$ for $$i \in [k-1] \smallsetminus I$$ in this order.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1],w)                    # optional - gap3
sage: F = SC([1,2]); F                                      # optional - gap3
(1, 2)
sage: F.root_configuration()                                # optional - gap3
[(1, 1), (-1, 0)]

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1],w)
sage: F = SC([1,2]); F
(1, 2)
sage: F.root_configuration()                                # optional - gap3
[(1, 1), (-1, 0)]

show(*kwds, **args)

Show the facet self.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1],w)                    # optional - gap3
sage: F = SC([1,2]); F.show()                               # optional - gap3

upper_root_configuration()

Return the positive roots of the root configuration of self.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1],w)                    # optional - gap3
sage: F = SC([1,2]); F                                      # optional - gap3
(1, 2)
sage: F.root_configuration()                                # optional - gap3
[(1, 1), (-1, 0)]
sage: F.upper_root_configuration()                          # optional - gap3
[(1, 0)]

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1],w)
sage: F = SC([1,2]); F
(1, 2)
sage: F.upper_root_configuration()
[(1, 0)]

weight_cone()

Return the polyhedral cone generated by the weight configuration of self.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1],w)                    # optional - gap3
sage: F = SC([1,2]); F                                      # optional - gap3
(1, 2)
sage: WC = F.weight_cone(); WC                              # optional - gap3
2-d cone in 2-d lattice N
sage: WC.rays()                                             # optional - gap3
N( 1, 2),
N(-1, 1)
in 2-d lattice N

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1],w)
sage: F = SC([1,2]); F
(1, 2)
sage: WC = F.weight_cone(); WC
2-d cone in 2-d lattice N

weight_configuration()

Return the weight configuration of self.

Let $$Q = q_1 \dots q_m \in S^*$$ and $$w \in W$$. The weight configuration of a facet $$I = [i_1, \dots, i_n]$$ of $$\mathcal{SC}(Q,w)$$ is the sequence $$\mathsf{w}(I, i_1), \dots, \mathsf{w}(I, i_n)$$ of weights defined by $$\mathsf{w}(I, k) = \Pi Q_{[k-1] \smallsetminus I} (\omega_{q_k})$$, where $$\Pi Q_{[k-1] \smallsetminus I}$$ is the product of the simple reflections $$q_i$$ for $$i \in [k-1] \smallsetminus I$$ in this order.

EXAMPLES:

sage: W = ReflectionGroup(['A',2])                          # optional - gap3
sage: w = W.from_reduced_word([1,2,1])                      # optional - gap3
sage: SC = SubwordComplex([1,2,1,2,1],w)                    # optional - gap3
sage: F = SC([1,2]); F                                      # optional - gap3
(1, 2)
sage: F.weight_configuration()                              # optional - gap3
[(1/3, 2/3), (-1/3, 1/3)]

sage: W = CoxeterGroup(['A',2])
sage: w = W.from_reduced_word([1,2,1])
sage: SC = SubwordComplex([1,2,1,2,1],w)
sage: F = SC([1,2]); F
(1, 2)
sage: F.weight_configuration()
[(2/3, 4/3), (-2/3, 2/3)]