How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Coxeter elements of tree type are conjugate by source and sink firings
Statement
Let be a Coxeter system with finite, , Coxeter diagram , and Coxeter elements defined as once-each products (Coxeter diagrams: edges, labels, components and finite type, Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups, Coxeter elements, the noncrossing interval [1,c], and the Kreweras map w ↦ w⁻¹c (1)). Suppose is of finite type. Then every connected component of is a tree: finiteness of makes the Coxeter form positive definite, and its restriction to each component is positive definite (Finiteness criterion: W is finite exactly when the Coxeter form is positive definite (1)); the positive-definite diagram exclusions show each component has no cycle (Exclusions for positive definite diagrams: trees, valency, labels, chains and arms (2)); hence each nonempty connected component is a tree (Trees, forests, leaves and isolated vertices).
(1) Orientation moves on a tree. Let be a finite tree. A source in an orientation is a vertex whose incident arrows all point away from it; a sink is one whose incident arrows all point towards it. Firing a source or sink reverses all its incident arrows. Every orientation of is acyclic, and any two orientations are connected by a finite sequence of firings.
(2) Orderings and orientations. An ordering of orients each edge of from its earlier vertex to its later vertex. This orientation is acyclic, and every acyclic orientation is obtained from some ordering. Its product is independent of the chosen ordering that realizes the orientation, so an acyclic orientation determines a Coxeter element. If a source or sink is fired, the new Coxeter element is .
(3) Conjugacy. If every connected component of is a tree, then any two Coxeter elements are conjugate by a product of simple reflections. In particular this holds in finite type, since then every connected component is a tree. If , then and the unique Coxeter element is conjugate to itself.
(4) Limits. Finite type is sufficient, not necessary, for the conjugacy assertion: its proof only needs each component to be a tree. No conjugacy claim is made for diagrams with cycles. No finite classification or geometric realization is used, and no Choice is needed.
Facts & Assumptions
Given: A Coxeter system with finite , its labelled diagram , Coxeter form , and Coxeter elements defined by once-each orderings. In clauses (1)–(3), finite type means is finite.
The diagram has a finite vertex set , an edge exactly when , and connected components that partition ; a connected component is nonempty. Finite type means that is finite (Coxeter diagrams: edges, labels, components and finite type).
If is finite, then is positive definite. Its restriction to the span of a component's simple roots is positive definite; a connected positive-definite Coxeter diagram has no cycle. A nonempty connected acyclic finite graph is a tree (Finiteness criterion: W is finite exactly when the Coxeter form is positive definite (1), Exclusions for positive definite diagrams: trees, valency, labels, chains and arms (2), Trees, forests, leaves and isolated vertices).
Every Coxeter element is a product of the simple generators in some ordering, with each used once. Under the component decomposition, it has the corresponding component Coxeter elements as coordinates (Coxeter elements, the noncrossing interval [1,c], and the Kreweras map w ↦ w⁻¹c (1),(3)).
In the Coxeter presentation, for every ; if then and therefore . The edge set of is exactly the pairs with (Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups, Coxeter diagrams: edges, labels, components and finite type).
A partial order is reflexive, antisymmetric, and transitive (Partial order and partially ordered set).
The multiplication map from the product of the standard subgroups of the connected components to is an isomorphism, and the component coordinates of a Coxeter element are the products in the restricted orderings (Coxeter elements, the noncrossing interval [1,c], and the Kreweras map w ↦ w⁻¹c (3), The subgroup generated by a subset, the cyclic subgroup , and cyclic groups).
Proof
Given: The data above; for a finite tree , two orientations ; and, for the conjugacy clauses, two once-each orderings defining .
(Firings connect tree orientations.) Every orientation of a tree is acyclic because a directed cycle would be an undirected cycle. Prove firing connectivity by induction on the number of vertices. For one vertex there is only one orientation; for two vertices a single firing of either endpoint reverses the only edge. For a tree with at least three vertices, an endpoint of a longest simple path is a leaf: a neighbour outside the path would extend it, and a second neighbour on the path would create a cycle. Let be its neighbour and put . This is a smaller tree, since a path between remaining vertices cannot use a leaf internally and deleting a vertex creates no cycle. By induction, a finite firing sequence changes to . Lift each firing at directly, since its incident edges are unchanged. Immediately before a firing at , its incident arrows in all point in one direction; if the edge points the other way, fire the leaf first, which is always legal and flips only . Now fire . The restriction to follows the inductive sequence. At the end, if has the wrong direction, fire once more. This reaches and proves (1).
(Orderings encode acyclic orientations.) An ordering gives no directed cycle because the position strictly increases along each oriented edge. Conversely, in a finite acyclic orientation there is a source: otherwise repeatedly following an incoming edge would revisit a vertex and give a directed cycle. Remove a source and repeat to obtain an ordering realizing every edge direction. If two such orderings realize the same orientation, they are linear extensions of the partial order generated by its directed paths. To connect the extensions, move the first vertex of one extension left through the preceding vertices of the other; each crossed vertex is incomparable with it, and induction repeats this on the remaining vertices. Incomparable vertices cannot be joined by an edge, so their generators commute by [F4]. Thus all these orderings give the same product, proving the orientation-to-element assertion.
(One firing is conjugation.) If is a source, choose a realizing ordering that starts with and write . After firing , the ordering with moved to the end realizes the new orientation, so its product is by . If is a sink, choose a realizing ordering ending in , write , and move to the beginning after firing; the new product is . This also covers an isolated vertex: it is both source and sink, firing changes no edge, and it commutes with all other generators. Hence each firing conjugates by its simple reflection.
(Componentwise conjugacy.) If , both products are . Otherwise suppose every connected component of is a tree; finite type guarantees this by [F2]. Restrict the orderings defining to each component. By step 1.1 a finite firing sequence connects the resulting orientations, and by step 2.1 each firing conjugates the corresponding component product by a simple reflection. Thus each component pair is conjugate by some . The component decomposition in [F6] combines these into with . If is connected, this conjugator is a product of simple reflections, as each firing uses one. This proves (3).
Depends on
- Coxeter elements, the noncrossing interval [1,c], and the Kreweras map w ↦ w⁻¹c
- Coxeter diagrams: edges, labels, components and finite type
- Finiteness criterion: W is finite exactly when the Coxeter form is positive definite
- Exclusions for positive definite diagrams: trees, valency, labels, chains and arms
- Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups
- The subgroup $\langle S \rangle$ generated by a subset, the cyclic subgroup $\langle g \rangle$, and cyclic groups
- Trees, forests, leaves and isolated vertices
- Partial order and partially ordered set
Used by
Dependency tree · two levels
98 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- H. Eriksson and K. Eriksson, Conjugacy of Coxeter Elements, Electronic Journal of Combinatorics 16(2) (2009), #R4 (standard reference, not scraped)