photo DAVID ILIFF

Christophe Hohlweg

Christophe Hohlweg  

Professeur, département de mathématiques, Université du Québec À Montréal, et Laboratoire de Combinatoire et d'Informatique Mathématique (LaCIM); Curriculum Vitae.

Address: Département de Mathématiques - LaCIM Université du Québec à Montréal CP 8888 Succ. Centre-Ville Montréal, Québec H3C 3P8 Canada

Phone: +1 514 987 3000 ext. 2566

Email: [hohlweg.christophe(no-spam)@(no-spam)uqam.ca][hohlweg.christophe(no-spam)@(no-spam)uqam.ca]

Office: PK-4230 (Pavillon Président Kennedy)

Expérimenter avec les associaèdres

CAMBRIAN is a library for the GAP3 package CHEVIE ** You need the last version of CHEVIE (2002) **     CAMBRIAN is for computing:         * Vertices and Halfspaces defining the Permutahedron of a finite Coxeter Group;         * Cambrian lattices, Coxeter sortable elements, c-clusters and Coxeter singletons;         * Vertices and halfspaces of Generalized Associahedra.    Let (W,S) be a finite Coxeter system acting by reflections on an euclidean space (V,< , >) . Let a be a point in the complement of the hyperplanes in V corresponding to the reflections of W . The convex hull of the W-orbit of a is a simple convex polytope: the permutahedron Perm^a (W). The normal fan of this polytope is the Coxeter fan.      Generalized associahedra have been introduced by S. Fomin and Zelevinsky in their works on finite type Cluster Algebras [FZ]. To each Weyl groups it corresponds a generalized associahedron: it is a simplicial complex with associated fan called the cluster fan. Relating generalized associahedra to quivers theory, R. Marsh, M. Reineke and A. Zelevinsky introduce in [MRZ] the c-cluster fan which generalized the cluster fan to any finite Coxeter group W and Coxeter element c in W. The simplicial complex associated to this fan is called the c-generalized associahedron Asso_c(W). They are all combinatorially isomorph, but they differ in their geometry. CAMBRIAN is based on the results of [HLT], [R1], [R2], [R3] and [RS]: CAMBRIAN provides functions to compute the Halfspaces-representation and the Vertices-representation of Permutahedra and c-Generalized Associahedra. A polytopal realization for a c-generalized associahedron uses as data only Perm^{a} (W), the initial point a and a particular reduced expressions of the longest element w_0 of W. It takes on my labtop only 20 minutes compute the coordinates of the vertices of a generalized associahedron for E8 (allowing 60MB to GAP).     How to run CAMBRIAN     First, download Cambrian.zip. Then unzip this file in a new folder. Run GAP (from this folder). Then  

    gap> Read("Cambrian.g");

    This command will load automatically CHEVIE. **   How does CAMBRIAN work **     In what follows, (W,S) is a finite Coxeter system and c is a Coxeter element of W , that is, the product of the simple generators in some order.  

    gap> W := CoxeterGroup( "A",5 );;
    gap> c := [3,5,4,2,1];;

    Let (W,S) act by reflections on an real euclidean space (V,( , )). Without loss of generality, we assume that the action of W is essential relative to V , that is, has no non trivial space fixed pointwise. Let R be a root system corresponding to (W,S) with simple roots D={r_s | s in S}. The set D is a basis of V. Let D^={v_s | s in S} be the set of fundamental weights, that is, the orthonormal basis of D, see FundamentalWeights. For going from the basis D to the basis D^ and vice-versa, see FromSimpleToWeights and FromWeightsToSimple.     We now aim for a definition of the Perm^{a} (W). Pick a point a in V contained in the complement of the reflection hyperplanes of W, that is, a strictly positive sum of the fundamental weights: a = sum_{sS} k_s v_s, k_s > 0. For w in W we write M(e) = a and M(w) = w( M(e)) and obtain the permutahedron Perm^{a} (W) as convex hull of {M(w) | w in W}. The index a will be omitted for brevity. This is the V-representation of Perm(W), see VRepresentationPermutahedron.  

    gap> W := CoxeterGroup( "B",2 );
    CoxeterGroup("B",2)
    gap> a := FromWeightsToSimple(W,[1,2]);
    [ 4, 3 ]
    gap> eltW := Elements(W);;
    gap> VRepresentationPermutahedron(W,eltW,a);
    [ [ 4, 3 ], [ -2, -3 ], [ 4, 1 ], [ 2, -1 ], [ 2, 3 ], [ -4, -3 ],
      [ -4, -1 ], [ -2, 1 ] ]
    gap> List(eltW,w->CoxeterWord(W,w));
    [ [  ], [ 2, 1, 2 ], [ 2 ], [ 2, 1 ], [ 1 ], [ 1, 2, 1, 2 ],
      [ 1, 2, 1 ], [ 1, 2 ] ]

    Equivalently, Perm(W) is the intersection of halfspaces H^+{(x,s)}, for all s in S and x in W, where H^+{(x,s)} = { v in V | ( v , x(v_s) ) <= ( M(e) , v_s ) = a_s } if a=sum_{s in S} a_s r_s. We consider also the hyperplane H_{(x,s)} = { v in V | ( v , x(v_s) ) = ( M(e) , v_s ) = a_s }.     Denote by W_I the standard parabolic subgroup of W generated by I in S. Note that H_{(w,s)}=H_{(x,s)} if and only if w in xW_{S {s}}. This is the H-representation of Perm(W), see HRepresentationPermutahedron.  

    gap> W := CoxeterGroup( "B",2 );
    CoxeterGroup("B",2)
    gap> a := FromWeightsToSimple(W,[1,2]);
    [ 4, 3 ]
    gap> HRepresentationPermutahedron(W,a);
    [ [ [ [ 1, 0 ], 4 ], [ [ -1, 2 ], 4 ], [ [ 1, -2 ], 4 ], [ [ -1, 0 ], 4 ] ],
      [ [ [ 0, 1 ], 3 ], [ [ 1, -1 ], 3 ], [ [ -1, 1 ], 3 ], [ [ 0, -1 ], 3 ] ] ]
    gap> l := List([1..W.rank],i->ReflectionSubgroup(W,Filtered([1..n],a->a<>i)));
    [ ReflectionSubgroup(CoxeterGroup("B",2), [ 2 ]),
      ReflectionSubgroup(CoxeterGroup("B",2), [ 1 ]) ]
    gap> CR := List(l,i->List( ReducedRightCosetRepresentatives(W,i),w->CoxeterWord(W,w^-1) ));
    [ [ [  ], [ 1 ], [ 2, 1 ], [ 1, 2, 1 ] ],
      [ [  ], [ 2 ], [ 1, 2 ], [ 2, 1, 2 ] ] ]

The V-representation and the H-representation of Perm(W) are linked as follows: M(w) in H_{(x,s)} if and only if H_{(x,s)}=H_{(w,s)}. Hence {M(w)} is the intersection of H_{(w,s)} for all s in S.     For c a Coxeter element in W and I a subset of S, we denote by c_I the subword of c obtained by taking only the simple reflections in I. So c_I is a Coxeter element of W_I. The c-sorting word of w in W is the unique subword of the infinite word c^=cccccc... that is a reduced expression for w and is the lexicographically smallest sequence of positions occupied by this subword, see CWord.

    gap> W := CoxeterGroup( "A",5 );
    CoxeterGroup("A",5)
    gap> w := [ 1, 2, 1, 3, 2, 1, 4, 3, 2, 1, 5, 4, 3, 2, 1 ];;
    gap> c := [5,4,3,1,2];
    [ 5, 4, 3, 1, 2 ]
    gap> CWord(W,c,w);
    [ 5, 4, 3, 1, 2, 5, 4, 3, 1, 2, 5, 4, 3, 5, 4 ]

    In particular, the c-sorting word of w