Toric Heaps, Cyclic Reducibility, and Conjugacy in Coxeter Groups ()
1. Introduction and Overview
In mathematics and computer science, a trace is a set of strings or words over an alphabet
for which certain pairs are allowed to commute. The commutativity rules can be encoded by an undirected graph
called the dependency graph, where the vertices are the letters and edges correspond to non-commuting pairs. Given a trace, the associated trace monoid is the set of finite words under the equivalence relation generated by these commutations, where the binary operation is concatenation. The combinatorics of trace monoids were studied by Cartier and Foata in the 1960s, who called them partially commutative monoids [1]. They are now sometimes known as Cartier-Foata monoids. We will stick with the term “trace monoid” for brevity. In 1986, G. X. Viennot [2] introduced the theory of heaps of pieces, which is a combinatorial interpretation of these objects that leads to a nice way to visualize them. The “pieces” represent the distinct letters in the alphabet, and a string is represented by a vertical stack, or “heap” of these pieces. Two pieces overlap vertically if the corresponding letters do not commute, as elements in the monoid. A simple example of this follows.
Example 1.1. Consider the trace monoid
over the alphabet
with dependency graph
shown on the left in Figure 1. That is, two letters commute if and only if they are non-adjacent in
. The string
in
defines a heap of pieces shown in the middle of Figure 1. One can think of this as being built by dropping balls in a “Towers of Hanoi” fashion onto this dependency graph—pieces of the same type are aligned vertically, and two pieces of different types overlap vertically if they do not commute. This heap (of pieces) is just a labeled poset (sometimes called its skeleton), whose Hasse diagram is shown on the right in Figure 1. Note that every “labeled” linear extension is a string that gives rise to the same heap.
Trace monoids can be defined for arbitrary graphs, though the visualization of the heap in Figure 1 works well because
is a line-graph. For more complicated planar graphs, we might need to make the pieces oddly shaped for the “Towers of Hanoi” visualization to work, which originally motivated Viennot’s heaps of pieces. For example, in Figure 1 the piece
does not commute with either
or
. If we want to further require that it does not commute with
and
, one way to represent this is to elongate it, as shown in Figure 2. The new dependency graph and Hasse diagram of the labeled poset are shown as well.
For more complicated dependency graphs
, e.g. non-planar ones, the labeled poset arising from a trace monoid over
does not have a nice visual realization
![]()
Figure 1. The dependency graph
of a trace monoid (left), a heap of pieces (middle), and its associated labeled poset
(right).
![]()
Figure 2. This heap of pieces is created from the heap in Figure 1 by additionally restricting
from commuting with
and
. This adds new edges to the dependency graph and new relations to the poset.
in 2- or 3-dimensional space as a stack of pieces. However, there is still an underlying labeled poset which we can rigorously formalize as a heap. In Section 3, we will formally define all terms so there is no ambiguity about our notation. However, in the remainder of this section, we will assume a few basic definitions that the reader likely already knows, so we can summarize the outline, goals, and main ideas of this paper.
Since Viennot introduced them in 1986, heaps have been defined in various ways, depending on the context, and usually with the “of pieces” dropped from the name. The following definition is due to R.M. Green [3] , who defined the category of heaps and applied it to Lie theory. Having a category makes definitions like a subheap and a morphism between heaps both natural and precise, and we will revisit this in Section 3.
Definition 1.2. A heap is a triple
consisting of a poset
, a graph
, and a function
to its vertex set, satisfying:
1) For every vertex
of
, the subset
is a chain in
, called a vertex chain.
2) For every edge
of
, the subset
is a chain in
, called an edge chain.
3) If
is another poset over the same set satisfying (1) and (2), then
is an extension of
.
Heaps arise naturally in Coxeter theory, because every reduced word in a Coxeter group can be thought of as a labeled linear extension of a heap over the Coxeter graph
. This is best seen by an example, and the one that follows should be quite illustrative. It will be a running example that we will revisit throughout this paper.
Running Example 1. Consider the finite Coxeter group
, whose Coxeter graph is shown in Figure 3 on the left1. In this Coxeter group,
, and so the element
can also be written as
. Both of these reduced words gives rise to a heap, which are shown in Figure 3. It is easy to see that these two heaps describe different words in the trace monoid
, where
. However, they represent the same group element in
.
1Normally, the vertices of
are
, but we are using
, for consistency with the vertex sets of
and
, which will appear in later examples.
Heaps generally do not provide a “magic bullet” for proving theorems in Coxeter theory or elsewhere, but they are often quite useful. They have been applied to a variety of topics in pure and applied mathematics, physics, computer science,
![]()
Figure 3. The element
in the Coxeter group
has two heaps, one for each commutativity class.
and engineering. Examples include fully commutative [4] [5] and freely braided [6] elements in Coxeter groups, Kazhdan-Lusztig polynomials [7] , representations of Kac-Moody [8] and Lie algebras [9] , Q-system cluster algebras [10] , parallelogram polyominoes [11] ,
-analogues of Bessel functions [12] , Lyndon words [13] , lattice animals [14] , Motzkin path models for polymers [15] , Lorentzian quantum gravity [16] , modeling with Petri nets [17] , control theory of discrete-event systems [18] , and many more.
Returning to Coxeter groups, heaps provide a framework for reducibility: commutativity classes of elements correspond to heaps, and reduced words to labeled linear extensions. The goal of this paper is to develop and study a cyclic version of a heap. This was originally motivated by a need for a framework of cyclic reducibility in Coxeter groups, though we expect that this structure will appear in other settings in combinatorics and beyond. Cyclic reducibility in Coxeter groups is closely related to the conjugacy problem, but it is also interesting in its own right. To motivate this connection, note that conjugating a reduced word
by the initial generator
cyclically shifts it, e.g.
(1.1)
Loosely speaking, one can think of our cyclic version of a heap as the result of identifying (or gluing) the top with the bottom of the diagrams in Figures 1-3, so that the “heap of pieces” is not a vertical stack, but rather a cylinder. For simple examples, such as the ones already given, this concept is visually clear. However, it is much less clear to how to formalize this mathematically and what the underlying structure should be, especially for general dependency graphs.
The answer to this involves a fairly new concept of a toric poset, introduced by Develin, Macauley, and Reiner in 2016 [19]. A toric poset is a cyclic version of an ordinary poset, that is generated by the equivalence under making minimal elements maximal, in the sense of Equation (1.1) above. Many fundamental features of posets have very natural cyclic, or “toric” analogues. For example, a chain in a poset is a totally ordered set, but a toric chain in a toric poset represents a totally cyclically ordered set. An extension of a poset is defined by adding relations. The toric counterpart to this concept is called a toric extension, but in order to see how these are analogous, one has to view things geometrically, and that is where the “toric” name comes from. A finite poset
can be viewed as an acyclic directed graph (but not uniquely), and that can be associated with a chamber
of a graphic hyperplane arrangement
in
. Though
and hence
are not uniquely determined by the poset, the particular chamber
is. The geometric interpretation of the equivalence generated by making minimal elements maximal is quotienting out by the integer lattice
. The result is a (toric) hyperplane arrangement
in the n-torus
. The chambers of
are in bijection with the acyclic orientations of
under the equivalence of converting sources into sinks, and these are called toric posets over
. Now, back to extensions: an extension of a poset can be described geometrically as adding hyperplanes to the arrangement
, and a (toric) extension of a toric poset corresponds to adding (toric) hyperplanes to
. There are also natural toric analogues of linear extensions, transitivity, Hasse diagrams, intervals, antichains, order ideals, morphisms, and
-partitions, among others. The ones relevant to toric heaps will be discussed later when we formalize them in Section 6. More details about these and others can be found in [19] [20] [21].
The formal definition of a toric poset can be found in Definition/Theorem 5.1. However, now that we have conveyed the intuitive idea of it, we can give the formal definition of a toric heap. It should be thought of as a labeled toric poset—a cyclic version of an ordinary heap.
Definition 1.3. A toric heap is a triple
consisting of a toric poset
, a graph
, and a function
to its vertex set, satisfying:
1) For every vertex
of
, the subset
is a toric chain in
, called a toric vertex chain.
2) For every edge
of
, the subset
is a toric chain in
, called a toric edge chain.
3) If
is another toric poset over the same set satisfying (1) and (2), then
is a toric extension of
.
The remainder of this paper is organized as follows. In Section 2, we discuss posets over graphs, and review relevant concepts in Coxeter theory. We use these concepts as motivating examples in Section 3, where we further study heaps over graphs and the resulting categories. In Section 4, we show how conjugation of Coxeter elements can be described by a source-to-sink operation on acyclic orientations. Generalizing this construction leads to the fully commutative (FC) and cyclically fully commutative (CFC) elements, which illustrate the need for a framework of cyclic reducibility in Coxeter theory. In Section 5, we review the concept of a toric poset, both geometrically as a chamber of a graphic toric hyperplane arrangement, and combinatorially as an equivalence class of acyclic orientations. This allows us to finally define toric heaps formally, and we look at the resulting categories. In Section 6, we formalize cyclic reducibility in Coxeter groups. We start with cyclic words, and distinguish between words and group elements being cyclically reduced and torically reduced. This leads us to the concept of cyclic commutativity classes. Next, we define the toric heap of a torically reduced word in any Coxeter group. In Section 7, we analyze new classes of elements that arise in this paper that are called torically fully commutative (TFC) and faux CFC. The former are the elements that have only one cyclic commutativity class, and the latter are those that additionally admit long braid relations. Finally, in Section 8, we discuss recent work on reducibility, cyclic reducibility, and conjugacy using the toric heap framework. A few beautiful results by T. Marquis in [22] are inaccurate as stated, but easily corrected by replacing “cyclically reduced” with “torically reduced”. We conclude in Section 9 with some open problems and directions for future research.
2. Combinatorial Coxeter Theory
Though the theory of heaps can be developed independently, Coxeter groups provide a wealth of useful and motivating examples, and so we will introduce them right away. More information can be found in classic texts such as Humphreys [23] or Björner and Brenti [24]. In this section, we will begin by defining posets over graphs, and then show how they arise in Coxeter theory. That will naturally lead us into heaps, which will be done in Section 3.
2.1. Posets over Graphs
Throughout this paper,
will be an undirected graph without loops,
a nonempty finite set, and
a binary relation that is reflexive, antisymmetric, and transitive. The pair
is a partially ordered set, or poset. Usually we will write
instead of
, as the relation is generally understood.
An acyclic orientation
of
determines a partial ordering on
, where
if and only if there is an
-directed path from
to
. We denote this poset by
, and say that it is a poset on
. Let
be the set of all acyclic orientations of
. It should be noted that a (finite) poset does not uniquely determine a graph. However, given a poset
, there is a unique minimal graph
with respect to edge-inclusion, called the Hasse diagram, and a unique maximal graph
, called the transitive closure, from which
arises as an acyclic orientation. A simple example of this is shown in Figure 4, where acyclic orientations of four different graphs (the undirected versions of those shown) all describe the same 5-element poset.
If for every
in
, either
or
holds, then
is a total order, and
is a totally ordered set. Naturally, we write
if
and
. A totally ordered subset of a poset is called a chain.
2.2. Coxeter Groups
A rank-
Coxeter system is a pair
consisting of a set
that generates a Coxeter group
by the presentation
![]()
Figure 4. Four acyclic directed graphs that describe the same 5-element poset.
Each bond strength
if and only if
, and
is precisely the order2 of
. Distinct generators
commute if and only if
. A Coxeter system has a Coxeter graph
which has vertex set
(or alternatively,
) and an edge
with label
for each noncommuting pair of generators. Labels of 3 are usually omitted because they are the most common. A Coxeter system
is irreducible if
is connected.
If a word
is equal to
when considered as an element of
, we say that it is a word or expression for
. If furthermore,
is minimal, we call it a reduced word for
, and we call
its length, denoted
. Let
be the set of reduced words for
and
be the set of all reduced words. We typically write words using an upright font, though it is common to speak of a word
as also being a group element
.
For each integer
and distinct generators
, define
A relation of the form
is a braid relation, and a short braid relation3 if
. The braid relations generate an equivalence on
, denoted
. A classic theorem of Matsumoto [25] says that the resulting equivalence classes are in bijection with the elements of
.
Theorem 2.1 (Matsumoto). Any two reduced words for
differ only by braid relations.
2For ease of notation, we allow
, and say that
for any
.
3Some authors call
a short braid relation if
, and a commutation relation if
.
By Matsumoto’s theorem, it is well-defined to let the support of an element
, denoted
, be the set of all generators appearing in any reduced word for
. If
, then we say that
has full support.
The short braid relations generate an equivalence relation ~ on
that is coarser than
. The resulting equivalence classes are called commutativity classes. Clearly, the reduced words of any
are a disjoint union of commutativity classes, i.e.
for some reduced words
, and where
is the commutativity class that contains
.
Definition 2.2. An element
is fully commutative (FC) if
contains only one commutativity class. Let
denote the set of fully commutative elements of
.
The classification of finite and affine Coxeter groups is well known, and it consists of several infinite families and some exceptional cases [24]. We will denote these groups by e.g.
,
, and their Coxeter graphs by, e.g.
,
, etc.
Running Example 1 (continued). Consider the word
as an element of three different Coxeter groups, one for each of the Coxeter graphs shown below. Recall that we are deliberately using
instead of the usual
as the generating set of
so that all three Coxeter graphs have the same vertex sets.

The word
is not reduced in
because
. It is reduced in
but not FC, because
. The partition of the reduced words into commutativity classes is
Finally, the word
is reduced in
and the corresponding group element
has a unique commutativity class,
, so it is FC.
3. Labeled Posets and Heaps
Recall from Definition 1.2 that a heap is a triple
, where
is a map from a poset to a graph. We will call
the heap poset,
the heap graph, and
the labeling map. Recall that the partial order on
is minimal (coarsest) such that the preimage
of each vertex and the preimage
of each edge in
are chains. However, when defining the heap from a concrete object, such as a reduced word in a Coxeter group, it is also necessary to specify the relative order of the elements within each of these chains. We will do this with an acyclic orientation.
Definition 3.1. Given a word
in
, consider the graph
, where
and
is the set of all
for which
and
. Let
be the orientation where each edge
is oriented as
if
and
otherwise. Define the poset
.
Definition 3.2. Fix a Coxeter system
, and let
be a word in
. Define the labeling map
The triple
is called the heap of
. If
, then we say it is a heap of the group element
.
By construction, distinct words in
give rise to distinct heaps, even if they are in the same commutativity class. For example, consider the words
and
in
. Even though
, the heaps
and
are different. We would like to say that they are “the same,” and we can do this using the concept of a heap isomorphism from [3]. Let Heap be the category of heaps, where morphisms are defined below.
Definition 3.3. A morphism from one heap
to another
is a pair
, where
is a poset morphism and
is a graph homomorphism, satisfying
:

If
is a heap morphism with
being the identity map on
, and
is injective, then
is a subheap of
. If
and
are both bijective, then the two heaps are isomorphic. If we want to only consider heaps over a fixed graph
, which is often the case, we can define
. We will mostly refrain from the category theory point of view in this paper, because the focus is more on Coxeter theory. A thorough categorical treatment of heaps and toric heaps will be done in a forthcoming paper. However, in order to speak about morphisms in Coxeter theory where
, we would need to be clear on how to define a homomorphism between Coxeter graphs, especially regarding edge weights. We will not do that here because we will not be using it.
Proposition 3.4. If
are reduced words in
, then the heaps
and
are isomorphic.
Proof. Since
and
differ by a sequence of short braid relations, it suffices to consider the case when they differ by a single adjacent transposition
. In this case, the heap isomorphism is
, where the transposition
is a poset isomorphism and
is the identity.
Henceforth, we will always speak of heaps up to isomorphism. By Proposition 3.4, each commutativity class of
has a unique heap. Therefore, if
is FC, then we may speak of
as the heap of the group element
. In contrast, for non-FC elements, different commutativity classes generally give non-isomorphic heaps. Our running example illustrates this nicely.
Running Example 1 (continued). Let us recall
first as an element in the Coxeter group
, and then in
. In
, it has two commutativity classes, and the associated heaps were shown in Figure 3. In
, the bond strength between
and
is increased to
. This means that
is FC, and so the only heap of this group element is the first one shown in Figure 3.
Heaps of reduced words in Coxeter groups were studied by Stembridge in [4] , though his definition was slightly different, in that he considered
and
incomparable if
. For reduced words, this makes no difference. In our setting, such an
and
must be comparable because the
-preimage of each edge is a chain, and also contains the preimages of two vertices, and chains in posets are closed under subsets. This is also why the vertex chain requirement is built into the definition. The advantage of our framework and this requirement will become more apparent when we formalize cyclic reducibility using toric heaps. This is also in line with Viennot’s original definition [2].
The concept of a labeled linear extension of a heap was studied in [4]. Here, we give an abstract definition of a more general concept in our framework. We also drop the word “labeled” because it is implied in the context of heaps. Say that a map
is an edge-inclusion if it is the identity map between graphs on the same vertex set, and every edge in
is also in
.
Definition 3.5. If
is the image of a morphism from a heap
, where
is an extension, and
is an edge-inclusion, then we say that it is an extension of
. Moreover, it is a linear extension of heaps if
is a linear extension of posets.
Given a heap
and a graph homomorphism
, there need not be a poset
and a map
such that
is a morphism to a heap
. However, there will always be (at least) one if
is an edge-inclusion, and it is easy to see how to construct
—it is a poset generated by the relations in
with edge chains for each additional edge in
. In general, such a
is not unique because there could be a choice of how to order the elements within each new edge chain, as shown in the following simple example.
Example 3.6. Let
be the edge-inclusion between the edgeless graph on
to the complete graph. The antichain
and labeling map
define a heap
. There are two linear extensions of
: let
denote the one with
and
the one with
. There are canonical heap morphisms
and
from
to
and
, respectively. Here,
and
both send
, and
and
both send
. These are shown in Figure 5.
Let
denote the set of linear extensions of a heap
. In [4] , these are called labeled linear extensions because they can be canonically indexed by words. For example, a linear extension
can be described by the word
, where
.
Example 3.7. Let
be the heap from Figure 1 and
the heap from Figure 2. Note that it is easy to define the labeling maps
and
to adapt those heaps to our framework. Since
is an extension and
an edge-inclusion, the morphism
is an extension of heaps. The total order
uniquely describes a heap that is a linear extension of both
and
.
In the examples from Figure 5, the two linear extensions are clearly characterized by the words
(left) and
(right).
![]()
Figure 5. Two linear extensions of the same heap from Example 3.6.
4. Coxeter, FC, and CFC Elements
One of the goals of this paper is to develop a framework for studying what we call “cyclic reducibility” in Coxeter groups. In this section, we will formalize concepts such as cyclic words and cyclic commutativity classes. In a subsequent section, we will develop a cyclic version of a heap called a toric heap, which is essentially a labeled toric poset. To motivate this, we will begin with conjugation of Coxeter elements, and then extend that to the cyclically fully commutative (CFC) elements. Throughout, let
be a fixed Coxeter system with Coxeter graph
. Given words, e.g.
in
, we will denote the corresponding group elements by
in
.
4.1. Conjugation of Coxeter Elements
Let
be a Coxeter system. A Coxeter element is the product of all generators in some order. We denote the set of all Coxeter elements by
. Every Coxeter element of
gives rise to a canonical acyclic orientation of the Coxeter graph
, defined by
where
is any linear extension of
. It is easy to see that this map is a bijection, and so we write
to denote “the Coxeter element defined by
”, and
for “the acyclic orientation given by
”. Since Coxeter elements are FC, the heap poset of
does not depend on the choice of reduced word, so we may write
.
Proposition 4.1. The heap poset of a Coxeter element
is
for any reduced word
.
Proof. Let
. By construction,
, and the labeling map
is defined by
. Since
has no repeated generators, each preimage
has size 1, and so is trivially a chain. For each edge
in
, say
without loss of generality, the preimage
is a chain with
. This matches the orientation of the edge
by
from Definition 3.1.
Since linear extensions of heaps can be indexed with words, we can consider the set
as a collection of words in
. A subset of
is said to be order-theoretic if it is the set of linear extensions of a heap. The following is a slight reformulation of Theorem 3.2 from [4].
Proposition 4.2. For an element
, the following are equivalent:
1)
is fully commutative.
2)
is order-theoretic.
3)
for some (equivalently, every)
.
We will state and prove a cyclic analogue of this result in Theorem 7.2, which involves a new class of elements that are called torically fully commutative (TFC). Before we can get there, we will first motivate the idea of cyclic reducibility with a simple example involving Coxeter elements. Observe that a cyclic shift of a Coxeter element is also a Coxeter element, and because
for every
, it is also a conjugation by the initial letter:
On the level of acyclic orientations, these two Coxeter elements are related by converting the source vertex
(an initial generator) into a sink (a terminal generator). This generates an equivalence relation
on
, and hence on
, that we call toric equivalence. This was first studied by Pretzel in [26] via an operation he called “pushing down maximal vertices”. In [27] , H. Eriksson and K. Eriksson showed that these equivalence classes are in 1-1 correspondence with the conjugacy classes of
. In a recent preprint of Adin et al. that introduces toric
-partitions, these equivalence classes are called toric DAGs [21].
Theorem 4.3 ( [27] ). In any Coxeter group,
are conjugate if and only if
.
Thus, there are bijections between the Coxeter elements and
, and between their conjugacy classes and toric equivalence classes, defined as follows:
The sets
and
are enumerated by the Tutte polynomial
at
and
, respectively [19].
Example 4.4. Consider the affine Coxeter group
, whose Coxeter graph is the circular graph
. Consider the following three reduced words for Coxeter elements:
,
, and
(using
instead of the usual
). The corresponding acyclic orientations are shown below4.
(4.1)
The
reduced words for Coxeter elements in
comprise
distinct elements. The 14 acyclic orientations fall into
toric equivalence classes:
and
have size 4, and
has size 6, the elements of which are shown below.
(4.2)
4For convenience, in the examples in this section, all of the graphs are drawn so that their vertices are the actual generators, rather than labeled bullets.
By Theorem 4.3, the 14 Coxeter elements fall into 3 distinct conjugacy classes, and any two conjugate Coxeter elements differ only by cyclic shifts and short braid relations. This can be visualized by writing the reduced words as circular words, and allowing the usual braid relations:
In the circular words
and
above, no short braid relations can be

applied, so both
and
are conjugate to only 4 Coxeter elements each—all cyclic shifts. In contrast, the relations
and
can be applied to
, yielding three other “reduced cyclic words”:
(4.3)
There are six distinct Coxeter elements, and 16 reduced words, that can arise from these four cyclic words, assuming they are read off clockwise:
(4.4)
The elements in the ith column above are the linear extensions of the poset defined by the ith orientation in Equation (4.2).
Example 4.4 should motivate the value of developing a theory of cyclic reducibility in Coxeter groups. For example, the four cyclic words in Equation (4.3) should be thought of as lying in the “cyclic commutativity class” containing the “cyclic word”
. In Section 6, we will develop this framework. But first, we need to focus on the curious “cyclic partial order” structure that arises. Cyclic words under the equivalence generated by short braid relations are like cyclic analogues of traces, though without the monoid structure, because there is no canonical way to concatenate cyclic words. This cyclic poset structure can be formalized via toric posets [19] , which leads to the concept of a toric heap. This is essentially a labeled toric poset, in the same sense of how ordinary heaps are labeled ordinary posets. It allows us to extend the examples shown in this section far beyond just Coxeter elements, which we will do next.
4.2. Cyclically Fully Commutative (CFC) Elements
Now that we have seen the interplay between Coxeter elements, acyclic orientations, and heaps, and how they behave under conjugacy, we will extend these ideas to a larger class of elements. This will elucidate the key structural properties as well as motivate the main ideas of our cyclic reducibility framework.
5Some authors call this property straight, which is motivated by a geometric view of Coxeter groups. We will use the term logarithmic, as our viewpoint is more purely combinatorial.
It is well known that in any Coxeter group, if
, then
, and so
. If equality holds for all
, then we say that
is logarithmic5. In 2009, it was shown independently by D. Speyer [28] and H. Eriksson and K. Eriksson [27] that in infinite irreducible Coxeter systems, Coxeter elements are logarithmic. It is simple to extend this to the non-irreducible case—each connected component of
must be the Coxeter graph of an infinite group. The logarithmic property was key to the Erikssons’ proof of the conjugacy problem (Theorem 4.3). Also crucial was the source-to-sink property, i.e. toric equivalence. In plain English, we mean that 1) Coxeter elements are FC (they avoid long braids), and 2) cyclic shifts of Coxeter elements remain FC. These properties can naturally be extended beyond Coxeter elements.
Definition 4.5. An element
is cyclically fully commutative (CFC) if for any reduced word of
, every cyclic shift is reduced and FC.
Example 4.6. Figure 6 shows examples of CFC elements in two affine Coxeter groups. On the left is the Coxeter graph of the group
and the CFC element
drawn in a circle so the reader can visually see how there are no long braids. To the right is the Coxeter graph of the group
and the CFC element
, also drawn in a circle.
CFC elements were introduced and studied in 2012 by Boothby et al. [29]. They have recently been characterized and enumerated in all affine Coxeter groups, and their generating functions were shown to be rational in all Coxeter groups [30] [31].
5. Labeled Toric Posets and Toric Heaps
5.1. Posets and Toric Posets, Geometrically
Throughout this section,
is a Coxeter graph,
is an undirected graph,
is the set of acyclic orientations of
, and
is toric equivalence, i.e. the equivalence relation on
generated by source-to-sink conversions.
A toric poset should be thought of as a cyclic version of a poset. The most concrete way to define them are as toric equivalence classes of
, and we write this as, e.g.
. However, this has two significant drawbacks: first, it suggests a dependence on the graph
, which is a little misleading. Recall that we can similarly define a poset
on a graph, though in actuality,
is almost never uniquely determined. Specifically, there is a unique minimal graph (the Hasse diagram,
), and a unique maximal graph (the transitive closure,
) on
such that any
whose edge set
is between the edge sets of these two extremes (with respect to subset inclusion) will work. Of course, care must also be taken with how to define
so that
, but that is straightforward—any shared edges must be oriented the same way.
![]()
Figure 6. CFC elements in affine Coxeter groups, drawn in a circle to highlight the absence of long braids, as well as to motivate concepts such as “cyclic words” and “cyclic commutativity classes”, which toric heaps will allow us to formalize.
The second drawback of the notation
is that it obscures the “more proper” geometric way to define a toric poset. We will motivate this by revisiting the geometric interpretation of
. In fact, finite posets can be defined and developed purely geometrically, as chambers of graphic hyperplane arrangements. For distinct vertices
and
in
, let
be the hyperplane
in
. The graphic arrangement of
is the set
. Each point
in the complement
determines a canonical acyclic orientation
, by directing the edge
as
if
. The fibers of this mapping are the chambers of the
, and so this induces a bijection between chambers of
and acyclic orientations of
:

At this point, one could define a poset to be any subset of
that arises as a chamber of some graphic hyperplane arrangement. This removes the reference to a particular graph in the definition. Given a poset
, we write
for the chamber in
determined by
. Given a chamber
, we write
for the poset determined by
.
Though this geometric perspective is a bit superfluous for ordinary posets, it is absolutely necessary for toric posets, where it is not so clear how to pull apart the concept of a toric poset from the underlying graph. The geometric definition of a toric poset arises from the observation that if we first quotient out
by the integer lattice
, then converting a source
into a sink corresponds to crossing a coordinate hyperplane
, and this does not change the corresponding connected component in the torus
. An example of this is shown in Figure 7.
This leads us to our first of five “Definition/Theorems”. We use that term
![]()
Figure 7. The hyperplane arrangement
of the complete graph
. The toric arrangement
is achieved by identifying opposite sides of the unit cube. Doing this merges the three regions corresponding to the three acyclic orientations shown into one single toric chamber.
because each of them involves a non-trivial statement or equivalence proven in [19] , which allows us to take them as the definition in this paper.
Definition/Theorem 5.1. A toric poset over
is characterized by either:
1) an equivalence class
in
,
2) a chamber
of the toric hyperplane arrangement
in
.
We will write
to mean the toric poset characterized by
in
. Given a toric poset
, we write
when we wish to speak of the chamber in
determined by
, and given a chamber
, we write
to emphasize the toric poset determined by it.
Aside from the definition not depending on a distinguished graph
, the second advantage to the geometric perspective is the recurring theme that many standard features of ordinary posets, such as chains, antichains, Hasse diagrams, transitive closure, order ideals, and so on, have natural toric analogues. However, it is usually not clear how these should be defined in terms of an equivalence class of acyclic orientations. Instead, the natural definition often only becomes apparent when one interprets the classical definition geometrically, and then passes to the quotient
, as illustrated by the following commutative diagram:

Often, this toric analogue then has a natural combinatorial interpretation in terms of directed graphs, which usually ends up being more convenient. A list of these can be found in the Introduction of [20].
For an example of this, consider a non-edge
. One might ask whether
and
are comparable in
. In other words, would adding
to
force its orientation by
, which happens when one of the two ways to orient it would create a directed cycle? If so,
is implied by transitivity, and either
or
. Geometrically, this means that the hyperplane
is disjoint from the chamber
of
. The combinatorial condition is also straightforward:
is implied by transitivity if and only if
and
lie on a common directed path in
(i.e. lie on a chain in
).
There is a toric analogue of transitivity, which is easy to state geometrically: the edge
is implied by toric transitivity if the toric hyperplane
is disjoint from the chamber
of
. The combinatorial condition of this is less clear due to the absence of a binary relation, but luckily, it has a simple answer, which is basically just adding the word “toric” to the ordinary case. Specifically, a toric directed path in
is a directed path
such that the edge
is also present, as shown in Figure 8. It was shown in [19] that if
is a toric directed path in
, then some cyclic shift is a toric directed path in
for each
.
It is worth noting that just like directed paths in ordinary posets, a two-element
![]()
Figure 8. A chain in a poset is any subset that lies on a directed path (left). A toric chain in a toric poset is any subset that lies on a toric directed path (right).
toric directed path is an edge, and all vertices are one-element toric directed paths. We will say that the empty set is vacuously a directed path and a toric directed path.
Definition/Theorem 5.2. A non-edge
is implied by transitivity in
if and only if
and
lie on a directed path in
.
A non-edge
is implied by toric transitivity in
if and only if
and
lie on a toric directed path in
.
For ordinary posets, adding all edges implied by transitivity, in any order, yields the transitive closure,
. The toric transitive closure
can be defined analogously.
For ordinary posets, removing all unnecessary edges, in any order, yields the Hasse diagram, denoted
. Geometrically, this just means removing all hyperplanes
that are disjoint from the chamber
. The toric Hasse diagram is completely analogous, and denoted
. However, the Hasse diagram of
and the toric Hasse diagram of
are generally not the same. To see why, we need the notion of a toric chain.
A key concept behind the aforementioned features of posets is that of a chain, which is a totally ordered set. This can be characterized geometrically in terms of the coordinates of the entries of all points in the corresponding chamber, or combinatorially as a subset of vertices lying on a directed path in
. A toric chain in
is a totally cyclically ordered set. This can also be characterized geometrically in terms of the coordinates of the entries of all points in the corresponding toric chambers. Luckily, its combinatorial characterization is both simple and analogous to the ordinary poset case.
Definition/Theorem 5.3. A set
is a:
• chain of
if it lies on a directed path in
;
• toric chain of
if it lies on a toric directed path in
.
Both chains and toric chains are closed under subsets.
Example 5.4. Let
,
, and
be the line, circular, and complete graph on 4 vertices, respectively. Assume that the vertices are ordered “naturally,” i.e. they all contain (at least) the edges
,
, and
. Define
,
, and
so that
is oriented
if
. Then
Figure 9 shows a visual of these examples. The solid lines show the edges that
![]()
Figure 9. Left: The Hasse diagram of
consists of the solid edges (undirected). The dashed edges are additionally implied by transitivity. Right: The toric Hasse diagram of
consists of the solid edges (undirected). The dashed edges are implied by toric transitivity. See Example 5.4 for details.
make up the Hasse and toric Hasse diagram. The transitive closure and toric transitive closure are given by including the (undirected) dashed edges as well.
The last concepts that we need the toric analogue of are extensions and total orders. A total order is a poset
, where
is the complete graph. Geometrically, this corresponds to a chamber of
. Intuitively, a total toric order is a toric poset that is totally cyclically ordered.
Definition/Theorem 5.5. A total toric order is characterized by either:
1) a toric poset
,
2) a chamber of
.
An extension
of a poset
is characterized combinatorially by adding relations (or edges to
), or geometrically by
in
(the result of adding hyperplanes to
). Moreover,
is a linear extension of
if it is an extension and a total order.
Definition/Theorem 5.6. Let
be a toric poset, and assume without loss of generality that
is its toric Hasse diagram. A toric extension
of a toric poset
is characterized by either:
1)
in
,
2)
, where
,
, and all edges in
are oriented the same way by
and
.
If
is a toric extension of
and a total toric order, then it is a total toric extension.
There are
total orders on a size-
set
, where
is the Tutte polynomial. In contrast, there are
total toric orders on
. Each one is indexed by a cyclic equivalence class of permutations
Geometrically, these correspond to the
toric chambers of
.
5.2. Toric Heaps
Before we formalize cyclic reducibility, it is worth pausing to return to our familiar example for guiding intuition. Recall (see Definition 1.3) that a toric heap has a labeling map
such that the inverse image of every vertex and every edge is a toric chain. Moreover,
must be minimal with respect to these chains.
Running Example 1 (continued). Recall that the element
in
has two distinct heaps, shown in Figure 3. Note that in each heap, the edge chain
forms a length-4 directed path in the Hasse diagram, and the size-3 edge chain
lies on a length-4 directed path. In the toric heap, these directed paths become toric directed paths, and so the toric Hasse diagram gets two additional edges. This is shown in Figure 10; the curved edges are these two additional ones.
Note that the two toric heaps shown in Figure 10 are actually the same, because the Hasse diagrams of the toric heap posets differ by a single source-to-sink conversion. Algebraically, this is because the word
can be transformed into
two ways: by a long braid relation
, or by a sequence of short braid relations and cyclic shifts. When we formalize this, we will say that the cyclic words
and
are in the same cyclic commutativity class. This is shown in Figure 11.
We can define structure-preserving maps between toric heaps using commutative diagrams in the same manner that we did between ordinary heaps in Definition 3.3. This leads to the category torHeap of toric heaps and toric heap morphisms. To properly define a toric heap morphism, we need the definition of a general toric poset morphism. However, we will omit this and instead refer the reader to [20] , because in this paper, the only morphisms we will use are extensions and isomorphisms. The former has been introduced and the latter is elementary: if there is a graph isomorphism
carrying the acyclic orientation
, then the toric posets
and
are isomorphic. Alternatively, it is straightforward to define this geometrically.
![]()
Figure 10. Though the element
in the Coxeter group
has two distinct heaps (see Figure 3), one for each commutativity class, both of these give rise to the same toric heap. Intuitively, one can think of this as identifying the top with the bottom of a stack of balls, making it cylindrical. The undirected versions of the digraphs shown are the toric Hasse diagrams of the toric heap posets.
![]()
Figure 11. A non-CFC element with only one cyclic commutativity class. The cyclic word
shown in the middle differs from
via a long braid relation
, but also via a short braid relation,
. This will be formalized in Section 6; this type of element will be called torically fully commutative (TFC).
Definition 5.7. A morphism from one toric heap
to another
is a pair
, where
is a toric poset morphism and
is a graph homomorphism, satisfying
:
![]()
As before, if
and
are both bijective, then the two toric heaps are isomorphic. The concept of a toric subheap is not as natural as an ordinary subheap, because the concept of a cyclic subword of a cyclic word is not as natural as subwords of regular words.
The concept of an extension naturally carries through from heaps to toric heaps. Recall that this is needed to properly formalize the minimality condition in Definition 1.3(3). We often drop the word “toric” for brevity, i.e. there is no difference between an extension and a toric extension of a toric heap.
Definition 5.8. If
is the image of a morphism from a toric heap
, where
is an extension, and
is an edge-inclusion, then we say that it is a (toric) extension of
. Moreover, it is a total (toric) extension of toric heaps if
is a total toric extension of toric posets.
As we did with heaps, if we want to only consider toric heaps over a fixed graph
, we can define the category
. However, we will generally avoid such language here, and save a thorough categorical treatment of heaps and toric heaps for a future paper.
Now that we have laid out the fundamentals for cyclic reducibility in Coxeter groups, we will develop a framework to describe it using a cyclic analogue of a heap. The basic idea is to take our “ball stack” heap of pieces and wrap it in a cylinder by identifying the top with the bottom of the picture. Obviously, this idea in such a simplistic form is well-suited for line graphs. In her 2014 masters thesis [32] , B. Fox proposed this idea in type A Coxeter groups (though it works equally well as long as
is a line graph), calling it a “cylindrical heap”. She acknowledged that in doing this, one loses the natural poset structure. In a 2017 paper, M. Pétréolle defined an operation on heaps he called the “cylindric closure” [31]. He basically turned each maximal edge chain and vertex chain into a cyclically ordered set by declaring for each vertex chain and each edge chain, the minimal element
and the maximal element
are related by
. This relation extends the partial order, but since antisymmetry is immediately destroyed, it is not a poset. For example, the relation between the elements in the toric directed path in Figure 8 would be
In some sense, Pétréolle uses this relation
as an effective “hack” to prove some beautiful results. Namely, he characterizes CFC elements in terms of pattern-avoidance of these cylindrical closures, and uses this to enumerate the CFC elements in all affine types. In the next section, we will formally define and develop the mathematical structure that lies behind the scenes here, and certainly elsewhere in combinatorics.
6. Cyclic Reducibility in Coxeter Groups
Throughout, let
be a fixed Coxeter system with Coxeter graph
. As before, given words, e.g.
in
, we will denote the corresponding group elements by
in
. At times, we can even go the other direction. Specifically, when given an element
, we may write
to mean “an arbitrary reduced word for
”.
6.1. Cyclic Words and Commutativity Classes
Definition 6.1. A word
is cyclically reduced if every cyclic shift of it is a reduced word for some element in
. A group element
is cyclically reduced if every reduced word for
is cyclically reduced.
A word
is torically reduced if it remains reduced under any sequence of cyclic shifts and/or braids. A group element
is torically reduced if any (equivalently, every) reduced word for
is torically reduced.
It is clear that torically reduced implies cyclically reduced, for both words and elements. However, the converse fails, as shown by the following example.
Example 6.2. The element
is cyclically reduced because it has only one reduced word, and every cyclic shift of it is reduced. However, it is not torically reduced because its cyclic shift
, and this latter word is not cyclically reduced. This also shows how a word
can be cyclically reduced despite the group element
failing to be cyclically reduced. These examples are illustrated in Figure 12.
At this point, we will formalize the notion of circular words, that we have been seeing in Section 4.1 and in Figure 6, Figure 11, and Figure 12.
Definition 6.3. Let
be a word in
. The cyclic word or cyclic expression containing
is the equivalence class
If
is cyclically reduced, then we say that the cyclic word
is reduced, and vice-versa. We say that
is torically reduced if
is torically reduced.
Let
denote the set of all cyclic words and let
be the set of all reduced cyclic words. Write
and
for the set of torically reduced words and cyclic words, respectively.
![]()
Figure 12. The element
in
is cyclically reduced but not torically reduced.
A word is a subword of
if it appears as a (consecutive) subword of some cyclic shift of
. Loosely speaking, we say that
and
differ by a braid if one can be converted into the other by replacing a subword
with
. The formal definition follows.
Definition 6.4. Two cyclic words
and
differ by a braid if there is some
and
such that
can be converted into
by replacing a subword of the form
with
for some
.
The equivalence relations
and
, generated by short braids and all braids, respectively, each define natural equivalence classes on the set
of reduced words. Elements of
are commutativity classes, and by Matsumoto’s theorem, elements of
are in 1-1 correspondence with the group elements of W. Since we are looking for cyclic analogues of classical results, it is natural to look at the equivalence classes of the set
of torically reduced words defined by these relations.
Definition 6.5. Let
be torically reduced. The cyclic commutativity classes of
and of
are defined as
Definition 6.6. Let
be torically reduced. The toric equivalence classes containing
and
are
The toric equivalence class of a torically reduced element
, denoted
, is defined as
We write
whenever
.
By Matsumoto’s theorem, it is well-founded to define
and
. Since
is coarser than
, the set
consists of at least the cyclic commutativity class of
, and potentially more. In other words, for every torically reduced
, we have a unique decomposition
(6.1)
of its torically equivalent cyclic words into cyclic commutativity classes, where each
, and each
is a union of cyclic words. We also have a similar decomposition of torically reduced words,
(6.2)
It is clear that
is contained in the conjugacy class
. It is an open question as to when
contains torically reduced elements not in
. This will be discussed more in Section 8.
Example 6.7. The element
is torically reduced in the affine Coxeter group
, and
contains three cyclic commutativity classes, each containing one cyclic word:
,
, and
, shown below.
![]()
It is clear that all three cyclic words above lie in different cyclic commutativity classes, because they have a different multiset of generators that appear in them. Additionally, each cyclic commutativity class contains only one cyclic word because none of the generators pairwise commute. The set
contains 12 torically reduced words: four from each of the three cyclic commutativity classes. The set
consists of the 6 distinct group elements in
defined by these 12 words—each one has exactly two reduced expressions for it.
An interesting difference between reducibility and cyclic reducibility lies in the fact that in the cyclic case, the presence of long braid relations does not necessarily imply multiple (cyclic) commutativity classes. Specifically,
is FC if and only if
contains only one commutativity class. Our running example shows how this fails in the cyclic case.
Running Example 1 (continued). The element
in
(see Figure 10) is not CFC. However,
contains two cyclic words,
and
, but only one cyclic commutativity class, as shown in Figure 11. The set
consists of the ten reduced words that lie in one of these two equivalence classes. These reduced words describe four distinct group elements:
and these comprise the set
of torically equivalent elements to
.
Definition 6.8. A torically reduced element with a unique cyclic commutativity class is called torically fully commutative (TFC). If it is additionally not CFC, then we call it faux CFC.
The element
in
from Running Example 1 is faux CFC. We will return to the TFC and faux CFC elements in Section 7.
6.2. Toric Heaps in Coxeter Groups
Just like how a word
gives rise to a canonical heap (Definition 3.2), it also gives rise to a canonical toric heap. With ordinary heaps, we are mainly only concerned with reduced words. Similarly, with toric heaps, we only need to focus on torically reduced words.
Though many ordinary poset features have natural toric analogues, there is one crucial property that fails to carry over, and as a result, the toric heap from a word
must be carefully defined. Every finite poset is completely determined by knowing 1) its set (a simplicial complex) of chains, and 2) the total order within each chain. Among other things, this gives rise to the order complex of a poset, which is fundamental to poset topology [33]. Unfortunately, there does not appear to be a toric analogue of this property, and hence, no sort of toric order complex either. To see why, consider the toric posets
and
, where
is a 5-cycle, and the acyclic orientations
and
are shown below:
![]()
It is elementary to see that source-to-sink conversions preserve the difference between the number of clockwise edges and counterclockwise edges. Since this quantity is
in
and
in
, then
, and hence T and
are distinct toric posets. However, both of them have the same set of nonempty toric chains: five of size 1 (the vertices), and five of size 2 (the edges). Moreover, each size-2 toric chain trivially has the same cyclic order. Thus, to define a toric poset over a graph, it is not enough to just specify the toric chains and the cyclic order within each one.
The easiest way to resolve this is to simply define the toric heap poset directly from an acyclic orientation. Recall how the poset
naturally arises from a word
in Definition 3.1. This also defines a natural toric poset, denoted
. Compare the following definition to that of the heap
from Definition 3.2.
Definition 6.9. Fix a Coxeter system
, and let
be a word in
. Define the labeling map
The triple
is called the toric heap of
.
Given a word
, the labeling maps of the heap poset
and toric heap poset
are described by the following commutative diagram, where
is the identity map on the underlying set
.
(6.3)
Since toric directed paths are directed paths,
pulls back toric chains in
to chains in
. However, the converse need not hold. For example, consider the word
in
. The heap poset
is totally ordered. However, there is no size-3 toric chain in
.
Consider two torically reduced words in the same commutativity class,
. By Proposition 3.4, the heaps
and
are isomorphic. Let
be the poset isomorphism. The toric heaps
and
are related by the following commutative diagram
(6.4)
where
is a bijection, and so
is a toric poset isomorphism. A similar argument shows that if
and
differ by a single cyclic shift, then
and
are isomorphic. Specifically, define
by
, and consider only the right-hand side of the commutative diagram in Equation (6.4). Since toric heaps are preserved by cyclic shifts and short braid relations, then torically equivalent words
will yield isomorphic toric heaps. Thus, as with heaps, we will henceforth only consider toric heaps up to isomorphism.
Recall that there is a bijection between the linear extensions of a heap
and words in the commutativity class
. The cyclic analogue of this holds as well. Since a total toric extension is a toric poset that is a total toric order, we usually denote it with a cyclic word, e.g.
, instead of as a toric heap
over the complete graph. Clearly,
is one total toric extension of
. Given
, define
(6.5)
Running Example 1 (continued). The toric heap
of the word
in
, shown in Figure 10 and Figure 11, has two total toric extensions which are both in the same cyclic commutativity class:
As with the case of ordinary reducibility, there is a bijection between total toric extensions and cyclic commutativity classes.
Theorem 6.10. Let
be a torically reduced word in a Coxeter system
. Then
Proof. Suppose
, and pick
from
, which defines a toric heap
over the complete graph. Let
be the extension, where
is the edge-inclusion map.
![]()
Since
and
are total toric extensions of
, then
and
differ by a sequence of cyclic shifts and short braid relations. Therefore,
.
Conversely, let
, which means there is a sequence of cyclic shifts and short braid relations that carries
to
. By Corollary 5.2 in [19] , every (closed) toric chamber
is the union of closed chambers
corresponding to the total toric extensions of
. This means that
and
are both total toric extensions of
.
Example 6.11. Let us revisit the Coxeter elements in the affine Coxeter group
from Example 4.4. As before, let
,
, and
; see Equation (4.1). Both
and
are the only cyclic words in their cyclic commutativity class, and so
Additionally, for both
, the set
contains four reduced words—the cyclic shifts of
.
In contrast,
contains four cyclic words that comprise a single cyclic commutativity class:
These were shown in Equation (4.3). Finally,
contains 16 reduced words, four from each cyclic word above. These fall into six distinct group elements, which appeared in Equation (4.4).
7. Torically Fully Commutative (TFC) Elements
We begin this section with a reminder of a notational convention that we will use frequently: if we have a group element
and write
, we are referring to an arbitrary fixed reduced word for
.
The fully commutative (FC) elements have been well-studied; see [4] [5] [34]. It is clear that we have inclusions
![]()
The FC elements are those that have a unique heap, i.e. for any reduced word
, we have
. In this section, we will establish that the torically fully commutative (TFC) elements are those that have a unique toric heap: if
, then
. After that, we will study basic properties of TFC and the faux CFC elements—those that are TFC but not CFC.
Say that a subset of
is torically order-theoretic if it is the set of total toric extensions of a toric heap, i.e. if it can be expressed as
for some torically reduced word
. We will begin with a simple lemma; note that the converse of it is trivial.
Lemma 7.1. If
is torically order-theoretic, then
.
Proof. Write
, its unique decomposition as a disjoint union of cyclic commutativity classes, as in Equation (6.1). Since it is torically order-theoretic,
for some
. The proof will follow once we establish the following:
(7.1)
The subset containment is immediate, and we have already seen the first equality. The second and fourth equalities are due to Theorem 6.10, and so now we can deduce that
. However, since these are non-disjoint equivalence classes, they must be the same, which confirms that the containment in Equation (7.1) is actually an equality and completes the proof of the lemma.
Though the CFC elements are a natural cyclic analogue of the FC elements, one must go up to the TFC elements to get the cyclic version of Proposition 4.2.
Theorem 7.2. For a torically reduced element
, the following are equivalent:
1)
is TFC.
2)
is torically order-theoretic.
3)
for some (equivalently, every)
.
Proof. The implication (2)
(1) was established in the proof of Lemma 7.1, where it was shown that
. Also simple is (3)
(2), which is immediate from the definition.
For (1)
(3): If
is TFC, then it has only one cyclic commutativity class,
. The first equality is from Equation (6.1) and the second is by Theorem 6.10. This establishes the “for some” part of (3); it suffices to prove the stronger “for every” part. Let
, which means that
, and
is TFC because
is. The following chain of equalities will complete the theorem:
Specifically, the first and third are by definition, and the second is because
. The fourth equality follows from the proof of the “for some” implication above, applied to the TFC element
.
Since every toric poset is completely determined by its set of total toric extensions ( [19] , Corollary 5.2), Theorem 7.2 implies that the TFC elements are those that have a unique toric heap. An open question is to classify all TFC and faux CFC elements in an arbitrary Coxeter group. In this section, we will begin with some examples, and then give some necessary and sufficient conditions for an element to be TFC or faux CFC. Throughout,
will be a torically reduced word.
Example 7.3. The following elements are all faux CFC:
1) The element
in
from Running Example 1.
2) The element
in the affine group
, which has Coxeter graph
![]()
3) The element
in the Coxeter group whose Coxeter graph is shown below.
![]()
It is obvious that a faux CFC element cannot contain a long braid relation of odd length, because applying a single such relation changes the number of individual generators in the word.
Proposition 7.4. If
is faux CFC and
is odd, then none of the torically reduced words
contain
as a subword.
The previous result is a necessary condition for
to be faux CFC. Next, we will provide a sufficient condition. Say that
is an endpoint of the Coxeter graph
if it has degree 1, and is even (respectively, odd) if
is even (respectively, odd) for the unique
for which
. In this case, we call
a spoke of
, and can speak of spokes being even or odd.
Proposition 7.5. Let
be a Coxeter graph with an even endpoint
with adjacent vertex
. Suppose
is a reduced word for some element
where the subword
satisfies the following two properties:
•
contains no generators
and
, and
•
is a reduced word for some CFC element in
.
Then
is TFC.
Proof. Since
is a reduced word for some CFC element containing no
nor
, then
is torically reduced, and the only long braid relation that can be applied to
is
. Thus,
is torically reduced but not CFC. Since
commutes with every generator in
,
That is,
has only one equivalence (cyclic commutativity) class, and so
is TFC.
We conjecture that faux CFC elements (with full support) only occur when the Coxeter graph has at least one even endpoint. It would be desirable to understand how faux CFC elements can be “reduced” down to CFC elements. In our prior examples of faux CFC elements of the form
, removing
from the word yields an element that can be:
1) CFC, as in Example 7.3(1), or
2) faux CFC, as in Example 7.3(2), or
3) not TFC, as in Example 7.3(3).
Whether the new word
is CFC, faux CFC, or not TFC, depends on
. For the three cases above,
is 1) CFC, 2) faux CFC, 3) not cyclically reduced. We end this section with a conjecture.
Conjecture 7.6. If
is faux CFC and
torically reduced, then
is TFC.
8. Toric Heaps and Conjugacy in Coxeter Groups
We will wrap up this paper by revisiting some of the existing results on Coxeter theory from Section 4, cast them in a cyclic reducibility framework, and discuss some open problems.
Theorem 8.1. Let
and
be Coxeter elements of W. Then
1)
if and only if they have the same heap, and
2)
and
are conjugate if and only if they have the same toric heap.
The first statement in Theorem 8.1 is an immediate consequence of Matsumoto’s theorem, and the second is Theorem 4.3 using the toric heap language. Note that this fails if we drop the assumption that
is a Coxeter element, because in the finite Coxeter group
,
(8.1)
More generally, examples like this exist when distinct subsets
, and hence, their standard parabolic subgroups,
and
, are conjugate in
. This phenomenon has been completely characterized by Deodhar [35] , and it only happens when
is finite. The technical condition can be found in ( [36] , Theorem 3.1.3).
The proof of the second statement in Theorem 8.1 heavily relies on two properties of Coxeter elements. The first is toric equivalence, and the second is a theorem proven independently by Speyer in 2009 [28] and by the Erikssons in 2010 [37] : In an infinite irreducible Coxeter group, all Coxeter elements are logarithmic. It is a simple exercise to extend this to the general case of reducible Coxeter groups. Of course, the necessary and sufficient condition is that every connected component of
describes an infinite group. In [29] , a CFC element
was said to be torsion free if every factor of the parabolic subgroup
describes an infinite group. Equivalently, none of the connected components of the induced graph
are of finite-type. It has been proven (see [22] [29] ) that CFC elements are logarithmic if and only if they are torsion free. Marquis proved that a similar result holds more generally, but it requires a relaxation of the definition of torsion free.
Definition 8.2 ( [22] ). An element
is torsion free if it has no reduced decomposition of the form
for some spherical subset
, some
, and some
normalizing
.
To see why this is a necessary requirement to being logarithmic, suppose that
is not torsion free and write
. Then for each
, we can write
for some
. Since
is finite, there must be some
such that
, and so
Note that such a
is not logarithmic because
Remarkably, Marquis proved that up to toric equivalence, this is the only barrier to a torically reduced element being logarithmic.
Theorem 8.3 ( [22] ). A torically reduced
is logarithmic if and only if every torically equivalent
is torsion-free.
A simple example of a non torsion-free element in an infinite group can be found by modifying our Running Example from living in the group
to
.
Example 8.4. Consider the faux CFC element
in
, as shown below:
![]()
Clearly,
is faux CFC but is not logarithmic because
. It is not torsion-free because taking
, we can write
for
and
.
Thus far, we have seen how cyclic reducibility affects ordinary reducibility. Now, we ask how it affects conjugacy.
Matsumoto’s theorem says that if
and
are reduced words for the same group element, then they differ by braids, i.e.
. We are interested in a “cyclic version” of Matsumoto’s theorem, which asks whether the cyclic words of torically reduced conjugate elements differ by braids, i.e.
. This is to the conjugacy problem what Matsumoto’s theorem is to the word problem.
Definition 8.5. A
-conjugacy class
satisfies the cyclic version of Matsumoto’s theorem (CVMT) if any two reduced words of torically reduced elements in C differ by braid relations and cyclic shifts.
As we have seen in Equation (8.1), the CVMT trivially fails in conjugacy classes that have a minimal cyclically reduced element with support
conjugate to some other
. We conjecture that this is the only times where it fails. In a recent paper [22] , Marquis proved the CVMT for all elements
of infinite order with property (Cent), which means that whenever
normalizes a finite parabolic subgroup of
, it centralizes the subgroup. Though this condition may seem peculiar, it is quite mild, as it is satisfied by any torsion-free normal subgroup
of finite index, which always exists in any infinite Coxeter group by Selberg’s Lemma and the linearity of Coxeter groups ( [38] , Lemma 1). Torically reduced elements that have property (Cent), or are in finite groups, are additionally strongly cyclically reduced ( [22] , Corollary C), which means that
, or equivalently,
is of minimal length in its conjugacy class. As a corollary, it follows that the CVMT holds for torsion-free CFC elements. Equivalently, Theorem 8.1 can be extended to this class of elements.
Conjecture 8.6. The cyclic version of Matsumoto’s theorem holds for a
-conjugacy classes, as long as the parabolic closure
of its minimal elements contains only infinite irreducible components.
Finally, it should be noted that Marquis’ aforementioned results were incorrectly stated with “cyclically reduced” instead of “torically reduced”. For example, the cyclically reduced element
in
from Example 6.2 is not strongly cyclically reduced as ( [22] , Corollary C) would suggest, because
Fortunately, this flaw is easily fixable. The author defined cyclically reduced elements as we did in Definition 6.1, but then in the proofs, used the subtly stronger concept of being torically reduced.
9. Concluding Remarks
The purpose of this paper is to present a framework for studying what we call “cyclic reducibility” in Coxeter groups, and show how this relates to ordinary problems in reducibility and conjugacy. We introduced the concept of a toric heap, which is a labeled toric poset and a cyclic version of Viennot’s classic “heaps of pieces”. We also formalized concepts such as cyclic words, cyclic commutativity classes, as well as cyclically and torically reduced words and elements in Coxeter groups. The notion of a toric heap morphism allowed us to formalize concepts such as labeled toric extensions, and prove that there is a bijection between (labeled) total toric extensions of the toric heap of a word, and its cyclic commutativity classes. This is a cyclic analogue of a theorem by Stembridge about labeled linear extensions of a heap and commutativity classes [4]. However, not all fundamental properties carried over. We saw how elements can admit long braid relations but still have a unique toric heap. This brought up a new class of elements called torically fully commutative (TFC), which generalized the notion of the cyclically fully commutative (CFC) elements. These elements led to another theorem of Stembridge that generalized a characterization of the FC elements. Classifying elements that are TFC but not CFC remains an open question (see Conjecture 7.6). Our cyclic reducibility framework casts old and new results in a more transparent light. We are currently exploring whether techniques and proofs involving cyclic reducibility and conjugacy can be simplified and streamlined using toric heaps.
Toric heaps should be of general interest outside of Coxeter groups, both as interesting mathematical objects in their own right, and as a convenient framework when labeled cyclic poset structures arise in various applications. A common theme with toric poset research has been to explore toric analogues of features of ordinary posets. Similarly, ordinary heaps have been applied in many settings, and some of these should have natural toric analogues that can be explored. We are also working on a more thorough analysis of the categories of heaps and toric heaps. Regarding applications, it is difficult to predict where and how toric heaps might arise in the future. Naturally, this should not come as a surprise; back in 1986, Viennot surely did not anticipate his new theory of heaps springing up in Coxeter groups, Lorentzian quantum gravity [16] , models for polymers [15] , modeling with Petri nets [17] , and discrete-event systems [18].
Acknowledgements
The second author was partially supported by a Simons Foundation Collaboration Grant for Mathematicians, Award #358242.