Search

Several classical formulae for the growth series of a Coxeter group are proved in a new way, using the structure of the Coxeter complex, the Davis complex, or the Tits non-complex., 7 pages

In this paper we give a description of the structure of the based ring of the lowest two-sided cell for a weighted Coxeter group with complete graph. It is proved that this ring is generated, in a simple way, by some subrings which are isomorphic to the based rings of the lowest two-sided cells for affine Weyl groups of type A ˜ 1 or A ˜ 2 .

The main algorithmic problems of group theory posed by M. Dehn are the problem of words, the problem of the conjugation of words for finitely presented groups, and the group’s isomorphism problem. Among the works related to the study of the M. Dehn’s problems, the most outstanding ones are the work of P. S. Novikov who proved the undecidability of the problem of words and the conjugacy problem for finitely presented groups as well as the undecidability of the problem of isomorphism of groups. In this regard, the main algorithmic problems and their various generalizations are studied in certain classes of groups. Coxeter groups were introduced by H. S. M. Coxeter: every reflection group is a Coxeter group if its generating elements are reflections with respect to hyperplanes limiting its fundamental polyhedron. H. S. M. Coxeter listed all the reflection groups in three-dimensional Euclidean space and proved that they are all Coxeter groups and every finite Coxeter group is isomorphic to some reflection group in the three-dimensional Euclidean space which elements have a common fixed point. In an algebraic aspect Coxeter groups are studied starting with works by J. Tits who solved the problem of words in certain Coxeter groups. The article describes the known results obtained in solving algorithmic problems in Coxeter groups; the main purpose of the paper is to analyze of the results of solving algorithmic problems in Coxeter groups that were obtained by members of the Tula algebraic school ’Algorithmic problems of theory of the groups and semigroups ’ under the supervision of V. N. Bezverkhnii. It reviews assertions and theorems proved by the authors of the article for the various classes of Coxeter groups: Coxeter groups of large and extra-large types, Coxeter groups with a tree-structure, and Coxeter groups with n-angled structure. The basic approaches and methods of evidence among which the method of diagrams worked out by van Kampen, reopened by R. Lindon and refined by V. N. Bezverkhnii concerning the introduction of R-cancellations, special R-cancellations, special ring cancellations as well as method of graphs, method of types worked out by V. N. Bezverkhnii, method of special set of words designed by V. N. Bezverkhnii on the basis of the generalization of Nielsen method for free construction of groups. Classes of group considered in the article include all Coxeter groups which may be represented as generalized tree structures of Coxeter groups formed from Coxeter groups with tree structure with replacing some vertices of the corresponding tree-graph by Coxeter groups of large or extra-large types as well as Coxeter groups with n-angled structure.

We prove a characterization of irreducible, non-spherical and non-affine Coxeter groups, motivated by applications to metric commensurators of Kac-Moody groups and twinnings at finite distance.

We present new efficient data structures for elements of Coxeter groups of type $A_m$ and their associated Iwahori--Hecke algebras $H(A_m)$. Usually, elements of $H(A_m)$ are represented as simple coefficient list of length $M = (m+1)!$ with respect to the standard basis, indexed by the elements of the Coxeter group. In the new data structure, elements of $H(A_m)$ are represented as nested coefficient lists. While the cost of addition is the same in both data structures, the new data structure leads to a huge improvement in the cost of multiplication in~$H(A_m)$., Comment: 17 pages; errors corrected; example added. To appear in J. Symb. Comp

For a given $w$ in a Coxeter group $W$ the elements $u$ smaller than $w$ in Bruhat order can be seen as the end-alcoves of stammering galleries of type $w$ in the Coxeter complex $\Sigma$. We generalize this notion and consider sets of end-alcoves of galleries that are positively folded with respect to certain orientation $\phi$ of $\Sigma$. We call these sets shadows. Positively folded galleries are closely related to the geometric study of affine Deligne-Lusztig varieties, MV polytopes, Hall-Littlewood polynomials and many more agebraic structures. In this paper we will introduce various notions of orientations and hence shadows and study some of their algorithmic properties., Comment: 30 pages, 8 figures, revised and final version

Motivated by applications to perverse sheaves, we study combinatorics of two cell decompositions of the symmetric product of the complex line, refining the complex stratification by multiplicities. Contingency matrices, appearing in classical statistics, parametrize the cells of one such decomposition, which has the property of being quasi-regular. The other, more economical, decomposition, goes back to the work of Fox-Neuwirth and Fuchs on the cohomology of braid groups. We give a criterion for a sheaf constructible with respect to the ''contingency decomposition'' to be constructible with respect to the complex stratification. We also study a polyhedral ball which we call the stochastihedron and whose boundary is dual to the two-sided Coxeter complex (for the root system $A_n$) introduced by T.K. Petersen. The Appendix by P. Etingof studies enumerative aspects of contingency matrices. In particular, it is proved that the ''meta-matrix'' formed by the numbers of contingency matrices of various sizes, is totally positive.

Besides simplices, n -cubes form an important class of simple polyhedra. Unlike hyperbolic Coxeter simplices, hyperbolic Coxeter n -cubes are not classified. In this work, we first show that there are no Coxeter n -cubes in H n for n ≥ 10 . Then, we show that the ideal ones exist only for n = 2 and 3 , and provide a classification. The methods used are of combinatorial and algebraic nature, using properties of a Coxeter graph, its Schlafli matrix, and the Gram matrix of a polyhedron.

We produce an explicit recursive formula which computes the idempotent projecting to any indecomposable Soergel bimodule for a universal Coxeter system. This gives the exact set of primes for which the positive characteristic analogue of Soergel’s conjecture holds. Along the way, we introduce the multicolored Temperley-Lieb algebra.

In this paper we prove that the parabolic Kazhdan–Lusztig polynomials and the parabolic R -polynomials of the universal Coxeter group can be computed in a combinatorial way, by using special matchings.

We study the concept of the Coxeter energy of graphs and digraphs (quivers) as an analogue of Gutman's adjacency energy, which has applications in theoretical chemistry and is a recently widely investigated graph invariant. Coxeter energy CE ( G ) of a (di)graph G is defined to be the sum of the absolute values of all complex eigenvalues of the Coxeter matrix associated with G. Our main inspiration for the study comes from the Coxeter formalism appearing in group theory, Lie theory, representation theory of algebras, mathematical physics and other contexts. We focus on the Coxeter energy of trees and we prove that the path (resp. the maximal star) has the smallest (resp. the greatest) Coxeter energy among all trees (resp. two large subclasses of trees) with fixed number of vertices. We provide several other related results, as the characterization of trees with second smallest and second greatest Coxeter energy, bounds for Coxeter energy, and general facts on Coxeter spectra of graphs extending known results e.g. for Salem trees and for certain special real Coxeter eigenvalues of trees. Additionally, we discuss few other energy-like quantities for the Coxeter spectra of (di)graphs, including Coxeter energy “normalized” by the trace of the Coxeter matrix and the quantities derived from variants of Coulson integral formula.

It is an open question whether right-angled Coxeter groups have unique group-equivariant visual boundaries. In Croke and Kleiner (Topology 39(3):549–556, 2000. doi: 10.1016/S0040-9383(99)00016-6 ), presented a right-angled Artin group with more than one visual boundary. In this paper we examine the space constructed by Croke and Kleiner and present a right-angled Coxeter group that is quasi-isometric to this space. Then we change the geometric parameters of this space to show that the proposed right-angled Coxeter group has non-unique equivariant visual boundaries, hence answer the open question negatively.

Let G be a finitely generated Coxeter group with presentation G = , where mij — are the elements of the symmetric Coxeter matrix: ∀i, j ∈ 1, n, mii = 1, mij ≥ 2, i 6= j. If mij ≥ 3(mij > 3), i 6= j, then G is a Coxeter group of large (extra-large) type. These groups introduced by K. Appel and P. Schupp. If the group G corresponds to a finite tree-graph Γ such that if the vertices of some edge e of the graph Γ correspond to generators ai , aj , then the edge e corresponds to the ratio of the species (aiaj ) mij = 1, then G is a Coxeter group with a tree-structure. Coxeter groups with a tree-structure introduced by V. N. Bezverkhnii, algorithmic problems in them was considered by V. N. Bezverkhnii and O. V. Inchenko. The group G can be represented as tree product 2-generated of Coxeter groups, amalgamated by cyclic subgroups. Thus from the graph Γ of G will move to the graph Γ in the following way: the vertices of the graph Γ we will put in line Coxeter group on two generators Gij = and Gjk = , to every edge e joining the vertices corresponding to Gij and Gjk is a cyclic subgroup . In this paper we prove the following theorem: normalizer of finitely generated subgroup of Coxeter group with tree-structure G = Gij∗Gjk, Gij = , Gjk = finitely generated and exist algorithm for generating.

In this paper, we present Brauer algebras associated to spherical Coxeter groups of type H3 and H4, which also can be regarded as subalgebras of Brauer algebras D6 and E8 by Muhlherr's admissible partition. Also some basic properties will be described here.

We continue the Coxeter spectral study of the category UBigrm of loop-free edgebipartite (signed) graphs ∆, with m ≥ 2 vertices, we started in [SIAM J. Discr. Math. 27(2013), 827-854] for corank r = 0 and r = 1. Here we study the class of all non-negative edge-bipartite graphs ∆ ∈ UBigrn+r of corank r ≥ 0, up to a pair of the Gram Z-congruences ∼Z and ≈Z, by means of the non-symmetric Gram matrix Ǧ∆ ∈ Mn+r(Z) of ∆, the symmetric Gram matrix G∆ := 1 2 [Ǧ∆ + Ǧ tr ∆ ] ∈ Mn+r(Z), the Coxeter matrix Cox∆ := −Ǧ∆ · Ǧ −tr ∆ ∈ Mn+r(Z) and its spectrum specc∆ ⊂ C, called the Coxeter spectrum of ∆. One of the aims in the study of the category UBigrn+r is to classify the equivalence classes of the non-negative edge-bipartite graphs in UBigrn+r with respect to each of the Gram congruences ∼Z and ≈Z. In particular, the Coxeter spectral analysis question, when the strong congruence ∆ ≈Z ∆′ holds (hence also ∆ ∼Z ∆′ holds), for a pair of connected non-negative graphs ∆,∆′ ∈ UBigrn+r such that specc∆ = specc∆′ , is studied in the paper. One of our main aims is an algorithmic description of a matrix B defining the Gram Z-congruences ∆ ≈Z ∆′ and ∆ ∼Z ∆′, that is, a Z-invertible matrix B ∈Mn+r(Z) such that Ǧ∆′ = B · Ǧ∆ ·B and G∆′ = B ·G∆ ·B, respectively. We show that, given a connected non-negative edge-bipartite graph ∆ in UBigrn+r of corank r ≥ 0 there exists a simply laced Dynkin diagram D, with n vertices, and a connected canonical r-vertex extension D := D of D of corank r (constructed in Section 2) such that ∆ ∼Z D. We also show that every matrix B defining the strong Gram Zcongruence ∆ ≈Z ∆′ in UBigrn+r has the form B = C∆ · B · C−1 ∆′ , where C∆, C∆′ ∈ Mn+r(Z) are fixed Z-invertible matrices defining the weak Gram congruences ∆ ∼Z D and ∆′ ∼Z D with an r-vertex extended graph D, respectively, and B ∈ Mn+r(Z) is Z-invertible matrix lying in the isotropy group Gl(n+r,Z)D of D. Moreover, each of the columns κ ∈ Z n+r of B is a root of ∆, Address for correspondence: Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, 87-100 Torun, Poland. ∗Supported by Polish Research Grant NCN 2011/03/B/ST1/00824. Received November 2015; revised March 2016 20 D. Simson / Symbolic Algorithms Computing the Gram Congruence, I i.e., κ · Ǧ∆ · κ = 1. Algorithms constructing the set of all such matrices B are presented in case when r = 0. We essentially use our construction of a morsification reduction map φD : UBigrD → MorD that reduces (up to ≈Z) the study of the set UBigrD of all connected non-negative edgebipartite graphs ∆ in UBigrn+r such that ∆ ∼Z D to the study of Gl(n+r,Z)D-orbits in the set MorD ⊆ Gl(n+r,Z) of all matrix morsifications of the graph D.

For Coxeter groups acting non-cocompactly but with finite covolume on real hyperbolic space $$\mathbb H^n$$ , new methods are presented to distinguish them up to (wide) commensurability. We exploit these ideas and determine the commensurability classes of all hyperbolic Coxeter groups whose fundamental polyhedra are pyramids over a product of two simplices of positive dimensions.

In well-known work, Kazhdan and Lusztig (1979) defined a new set of Hecke algebra basis elements (actually two such sets) associated to elements in any Coxeter group. Often these basis elements are computed by a standard recursive algorithm which, for Coxeter group elements of long length, generally involves computing most basis elements corresponding to Coxeter group elements of smaller length. Thus, many calculations simply compute all basis elements associated to a given length or less, even if the interest is in a specific Kazhdan-Lusztig basis element. Similar remarks apply to "parabolic" versions of these basis elements defined later by Deodhar (1987, 1990), though the lengths involved are the (smaller) lengths of distinguished coset representatives. We give an algorithm which targets any given Kazhdan-Lusztig basis element or parabolic analog and does not precompute any other Kazhdan-Lusztig basis elements. In particular it does not have to store them. This results in a considerable saving in memory usage, enabling new calculations in an important case (for finite and algebraic group 1-cohomology with irreducible coefficients) analyzed by Scott-Xi (2010).

We introduce and study in detail so-called circulant (Coxeter-periodic) elements and circulant families in a bilinear lattice K as well as their dual versions, called anti-circulant. We show that they form a natural environment for a systematic explanation of certain cyclotomic factors of the Coxeter polynomial χ K of K and in consequence, of Coxeter polynomials of algebras of finite global dimension. We discuss the properties of quadratic forms induced by circulant and anti-circulant families. Moreover, we interpret the results in the language of representation theory of algebras and point out applications (facts concerning tubular families in Auslander–Reiten quivers and quadratic forms of algebras). Abstract considerations in bilinear lattices are illustrated with a collection of non-trivial examples arising from module and derived categories. The results show that techniques of linear algebra and number theory provide efficient tools for explaining various representation theoretic facts.

Let $r$ be a positive integer and let $G_n$ be the reflection group of $n \times n$ monomial matrices whose entries are $r^{th}$ complex roots of unity and let $k \leq n$. We define and study two new graded quotients $R_{n,k}$ and $S_{n,k}$ of the polynomial ring $\mathbb{C}[x_1, \dots, x_n]$ in $n$ variables. When $k = n$, both of these quotients coincide with the classical coinvariant algebra attached to $G_n$. The algebraic properties of our quotients are governed by the combinatorial properties of $k$-dimensional faces in the Coxeter complex attached to $G_n$ (in the case of $R_{n,k}$) and $r$-colored ordered set partitions of $\{1, 2, \dots, n\}$ with $k$ blocks (in the case of $S_{n,k}$). Our work generalizes a construction of Haglund, Rhoades, and Shimozono from the symmetric group $\mathfrak{S}_n$ to the more general wreath products $G_n$., Comment: 44 pages, typos fixed and notation clarified

In the computation of the intersection cohomology of Shimura varieties, or of the $L^2$ cohomology of equal rank locally symmetric spaces, combinatorial identities involving averaged discrete series characters of real reductive groups play a large technical role. These identities can become very complicated and are not always well-understood (see for example the appendix of [8]). We propose a geometric approach to these identities in the case of Siegel modular varieties using the combinatorial properties of the Coxeter complex of the symmetric group. Apart from some introductory remarks about the origin of the identities, our paper is entirely combinatorial and does not require any knowledge of Shimura varieties or of representation theory., Comment: 17 pages, 1 figure; to appear in Algebraic Combinatorics

The growth function W(t) of a Coxeter group W relative to a Coxeter generating set is always a rational function. We prove by an explicit construction that there are infinitely many cocompact Coxeter groups W in hyperbolic 4-space with the following property. All the roots of the denominator of W(t) are on the unit circle except exactly two pairs of real roots.

International audience; In this note, we investigate the representation type of the cambrian lattices and some other related lattices. The result is expressed as a very simple trichotomy. When the rank of the underlined Coxeter group is at most 2, the lattices are of finite representation type. When the Coxeter group is a reducible group of type $A_{1}^{3}$ , the lattices are of tame representation type. In all the other cases they are of wild representation type.