ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 11 (2016) 101-106
A note on automorphisms of halved Cayley graphs of Coxeter systems
Mark Pankov
Department of Mathematics and Computer Science, University ofWarmia and Mazury, Sloneczna 54, Olsztyn, Poland
Received 10 February 2015, accepted 12 June 2015, published online 24 September 2015
We consider the halved Cayley graphs of Coxeter systems and show that every automorphism of such a graph can be uniquely extended to an automorphism of the corresponding Cayley graph.
Keywords: Coxeter system, Cayley graph. Math. Subj. Class.: 20F55, 05C12
1 Introduction
Let W be a group generated by a finite set S whose elements are involutions. For distinct s, s' G S we denote by m(s, s') the order of the element ss'. Then m(s, s') = m(s', s) and the condition m(s, s') = 2 is equivalent to the commuting of s and s'. Suppose that (W, S) is a Coxeter system, i.e W is the quotient of the free group over S by the normal subgroup generated by all (ss')m(s,s ) with m(s, s') < to.
The Cayley graph C(W, S) is the graph whose vertex set is W and w, v G W are adjacent vertices of the graph if v = sw for a certain s G S (since S consists of involutions, the adjacency relation is symmetric). For the dihedral Coxeter system I2(n) this graph is the (2n)-cycle and we get an infinite path if n = to. The Cayley graph of An is the permutohedron [6]. See [1, Figures 3.3] for the Cayley graph of H3. Also, C(W, S) can be identified with the graph whose vertices are maximal simplices of the Coxeter complex £(W, S) and two maximal simplices are adjacent vertices if their intersection consists of |S| — 1 elements [5].
In almost all cases, the automorphism group of C(W, S) is known. For every w G W the right multiplication Rw : v ^ vw is an automorphism of the graph. If the diagram of our Coxeter system does not contain adjacent edges labeled by to then the automorphism
E-mail address: pankov@matman.uwm.edu.pl (Mark Pankov)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
102
Ars Math. Contemp. 11 (2016) 101-106
group of C(W, S) is the semidirect product of W and the automorphism group of the diagram [1, Corollary 3.2.6].
The length l(w) of an element w e W is the smallest number m such that w has an expression
w = S1 ...sm, si,...,sm e S.	(1.1)
It is clear that l(w) is the distance between 1 and w in the Cayley graph. Since every right multiplication is an automorphism of the graph, the distance d(w, v) between w,v e W is equal to l(wv-1) = l(vw-1). Recall the following remarkable property of Coxeter systems called the exchange condition: if (1.1) is a reduced expression, i.e. l(w) = m, then for every s e S satisfying l(sw) < m there exists k e {1,..., m} such that
sw = Si . . . Sk . . . Sm
(the symbol * means that the corresponding term is omitted).
The group W can be presented as the disjoint union of the following subsets
W1 := { w e W : l(w) is odd } and W2 := { w e W : l(w) is even }.
Using the exchange condition we establish the following:
•	the distance between any two elements of Wj, i e {1, 2} is even,
•	the distance between every element of W1 and every element of W2 is odd.
Note that W2 is a subgroup of W. Consider the graph Rj, i e {1, 2} whose vertex set is Wj and two elements of Wj are adjacent vertices if the distance between them (in the Cayley graph) is equal to 2. The right multiplication Rw preserves both Wj in the case when w e W2. If w e W1 then Rw transfers W1 to W2 and conversely. The latter implies that r1 and r2 are isomorphic.
The main result of the note is the following.
Theorem 1.1. If |S| > 5 then every isomorphism between rj and Tj i, j e {1, 2} can be uniquely extended to an automorphism of the Cayley graph.
The same fails if |S| e {3,4} (Remark 3.2), but the statement holds for |S| = 2 (the Cayley graph is a cycle or an infinite path) and the case |S| = 1 is trivial.
Theorem 1.1 easily follows from the description of maximal 2-cliques of Cayley graph,
1.e.	maximal cliques of the halved Cayley graph, given in Lemma 2.5.
If S consists of n mutually commuting involutions then C(W, S) is the n-dimensional hypercube graph Hn and every rj is the half-cube graph 2 Hn. So, it is natural to ask which properties of the hypercube and half-cube graphs can be extended to C(W, S) and rj, respectively?
2 Maximal 2-cliques
Two vertices in a graph are said to be 2-adjacent if the distance between them is equal to
2.	Recall that a clique is a subset of the vertex set, where any two distinct vertices are adjacent. We say that a subset in the vertex set is a 2-clique if any two distinct elements of this subset are 2-adjacent vertices.
Consider examples of 2-cliques in C(W, S).
M. Pankov: A note on automorphisms of halved Cayley graphs ofCoxeter systems
103
Example 2.1 (First type). Any two distinct elements of S are 2-adjacent and S is a 2-clique. Since the right multiplication Rw is an automorphism of the Cayley graph, Sw is a 2-clique for every w G W.
Remark 2.2. Suppose that S = Sw. Then for any si, s2 G S there exist si, s2 G S such
that si = siw and s2 = s2w. If w = 1 then s1 = si and s2 = s2. We have
s'isi = w = s2s2 and s2sisi = S2
Since W cannot be generated by a proper subset of S, the latter means that s2 = si. Therefore, S = {si,s2} and sis2 = s2si. So, the equality Sw = Sw' implies that w = w' except the case when our Coxeter system is I2 (2).
Example 2.3 (Second type). Let s, s', s'' be three distinct mutually commuting elements of S. Then ss's'' is 2-adjacent to s, s', s'' and {sw, s'w, s''w, ss's''w} is a 2-clique for every w G W.
Example 2.4 (Third type). Suppose that s, s' G S and m(s, s') = 3. Then ss's = s'ss' and we denote this element by w(s, s'). It is 2-adjacent to s, s' and for every w G W the
set {sw, s'w, w(s, s')w} is a 2-clique.
Lemma 2.5. Every maximal 2-clique of C(W, S) is one of the 2-cliques described above.
Remark 2.6. The n-dimensional hypercube graph contains only maximal 2-cliques of the first and second types if n > 4 [3]. In the case when n = 3, there are precisely two maximal 2-cliques of the second type and 2-cliques of the first type are not maximal.
To prove Lemma 2.5 we use the following properties of Coxeter systems:
(P1) for every w G W there is a subset Sw c S such that every reduced expression of w is formed by all elements of Sw,
(P2) the group W cannot be generated by a proper subset of S.
Lemma 2.7. If u G W \ S is 2-adjacent to three distinct s, s', s'' G S then s, s', s'' are mutually commuting and u = ss's''.
Proof. Since u is 2-adjacent to s, s', s'' and u G S, there are three reduced expressions
u = sis2s, u = sis2s', u = si's2's'', where si, s2, si, s2, si', s2' G S. By (P1), we have Su = {s, s', s''} and
{si, s2} = {s', s''}, {si, s2} = {s, s''}, {si', s2'} = {s, s'}. Thus there are the following possibilities for the first and second expressions:
(1)	u = s''s's = s''ss',
(2)	u = s''s's = ss''s',
(3)	u = s's''s = s''ss',
(4)	u = s's''s = ss''s'.
104	Ars Math. Contemp. 11 (2016) 101-106
Case (1). The involutions s, s' are commuting and the third expression is
(2.1)
Then s''s's = u = s'ss'' and s's''s's = ss''. We apply the exchange condition to w = s"s's and get the following three possibilities:
•	s's = ss",
•	s" s = ss",
ss".
The first and third contradict (P2). So, s and s" are commuting. Similarly, the equality s"s's = u = ss's" shows that ss"s's = s's". Using the above arguments we establish that s' and s'' are commuting.
Case (2). The equality s''s's = ss''s' implies that s's = s''ss''s'. As in the previous case, we show that s and s' are commuting. Then the third expression is (2.1) which implies that ss''s' = u = ss's'' and s', s'' are commuting. The equality
guarantees that s and s'' are commuting.
Case (3). We have s's''s = s''ss' and s''s's''s = ss'. As above, this means that s, s' are commuting and the third expression is (2.1). Then s's''s = u = s'ss'' and s, s'' are commuting. The equality
shows that s' and s'' are commuting.
Case (4). Since s's''s = ss''s', we have s''s = s'ss''s' and ss's''s = s''s'. By the standard arguments, s'' is commuting with both s and s'. Then
which implies that s and s' are commuting.
□
Remark 2.8. If s, s', s'' are distinct elements of S then each of the equalities
implies that s and s' are commuting; moreover, the third equality guarantees that s, s', s'' are mutually commuting. See the cases (2)-(4) in the proof of Lemma 2.7.
Lemma 2.7 shows that for any three distinct mutually commuting s, s', s'' G S the 2-clique formed by s, s', s'' and ss's'' is maximal. Therefore, every 2-clique of the second type is maximal.
Lemma 2.9. If u G W \ S is 2-adjacent to distinct s, s' G S then one of the following possibilities is realized:
ss's''
u
s ss
s''s'
s''ss' = s''s's = u = ss''s'
s's''s = u = s''ss' = s''s' s
s''ss'
ss''s'
u = ss s = s ss
s''s' s = ss''s', s's''s = s''ss', s' s''s = ss''s'
M. Pankov: A note on automorphisms of halved Cayley graphs ofCoxeter systems
105
•	m(s, s') = 3 and u = w(s, s'),
•	s, s' are commuting and u = s''s's for a certain s'' G S.
Proof. Since u is 2-adjacent to s, s' and u G S, there are two reduced expressions
u = sis2s and u = s^s^s',
where si, s2, s1, s'2 G S. By (P1), we have {s, si, s2} = Su = {s', s1, s2}. If |Su| = 2 then Su = {s, s'} and u = ss's = s'ss' which implies that m(s, s') = 3, i.e. the first possibility is realized.
If |Su| = 3 then Su = {s, s', s''} and, as in the proof of Lemma 2.7, we have the following possibilities for the above expressions:
(1)	u = s''s's = s''ss',
(2)	u = s''s's = ss''s',
(3)	u = s's''s = s''ss',
(4)	u = s's''s = ss''s'.
It is clear that s and s' are commuting in the case (1). By Remark 2.8, the same holds for the cases (2) - (4) and s, s', s'' are mutually commuting in the case (4). So, we get the second possibility.	□
By Lemma 2.9, for any s, s' G S satisfying m(s, s') = 3 the 2-clique formed by s, s' and w(s, s') is maximal. Thus every 2-clique of the third type is maximal.
Proof of Lemma 2.5. Let C be a maximal 2-clique. For any distinct u, u' G C there exist w G W and s, s' G S such that u = sw and u' = s'w. The maximal 2-clique Cw-1 contains s and s'. Thus we can suppose that C contains at least two distinct elements of S. Let s and s' be elements of S belonging to C. Suppose that C = S, i.e. there is u g C \ S.
If there is a third element s'' G S contained in C then, by Lemma 2.7, s, s', s'' are mutually commuting and C is the 2-clique of the second type formed by s, s', s'' and u = ss's''. In the case when C contains precisely two elements of S, Lemma 2.9 shows that m(s, s') = 3 and C = {s, s', w(s, s')} or s, s' are commuting and u = s''s's for a certain s'' G S. The latter means that the maximal 2-clique Cs's contains s, s', s'', i.e. it coincides with S or {s, s', s'', ss's''}. Then C is a 2-clique of the first type or the second type. □
3 Proof of Theorem 1.1
We consider the case when i = j = 1. Let f : W1 ^ W1 be an automorphism of r1. Then f preserves the family of maximal cliques of r1. Every maximal clique of r1 is a maximal 2-clique of C(W, S) contained in W1. By Lemma 2.5, there are precisely three types of such subsets. They contain |S| vertices, 4 vertices and 3 vertices, respectively. The condition |S| > 5 guarantees that f preserves the types of maximal cliques.
If w G W2 then Sw is a maximal clique of r1 and f (Sw) = Sw' foracertain w' G W2. We set f (w) := w' and get a bijective transformation of W.
If w, v g W are adjacent vertices of the Cayley graph then one of these vertices belongs to W1 and the other is an element of W2. Suppose that v G W1 and w g W2. Then v G Sw
106
Ars Math. Contemp. 11 (2016) 101-106
and f (v) e f (Sw) = Sf (w) which implies that f (v) and f (w) are adjacent vertices of the Cayley graph. The apply the same arguments to f-1 and establish that f is an automorphism of C(W,S).
The uniqueness of such extension follows from the fact that w is the unique vertex of the Cayley graph adjacent to all vertices from Sw (Remark 2.2).
Remark 3.1. A similar idea was exploited in [4, Section 4.8] for an alternative proof of Cooperstein-Kasikova-Shult's characterization of apartments in half-spin Grassmannians [2].
Remark 3.2. If C(W, S) is H4 then there are automorphisms of r = 1H4 which change the types of 2-cliques contained in Wj. Such automorphisms are not extendable to automorphisms of H4. Similarly, if (W, S) is the direct product of I2 (3) and the group spanned by an involution then every maximal 2-clique of C(W, S) is of the first or of the third type and there are automorphisms of r changing the types of 2-cliques contained in Wj.
References
[1]	A. Bjorner and F. Brenti, Combinatorics of Coxeter groups, Graduate Texts in Mathematics 231, Springer, 2005.
[2]	B.N. Cooperstein , A. Kasikova and E.E. Shult Witt-type Theorems for Grassmannians and Lie Incidence Geometries, Adv. Geom. 5 (2005), 15-36.
[3]	W. Imrich, S. KlavZar and A. Vesel, A characterization of halved cubes, Ars Combin. 48 (1998), 27-32
[4]	M. Pankov, Grassmannians of classical buildings, Algebra and Discrete Math. Series 2, World Scientific, Singapore, 2010.
[5]	J. Tits, Buildings of spherical type and finite BN-pairs, Lecture Notes in Mathematics 386, Springer, 1974.
[6]	G. M. Ziegler, Lectures on Polytopes, Graduate Texts in Mathematics 152, Springer, 1995.