Ryo Uchiumi

Department of Mathematics, Graduate School of Science, Hokkaido University, Japan

uchiumi.ryo.r9@elms.hokudai.ac.jp

For a graph with edge ordering, a linear order on the edge set, we obtain a permutation of vertices by considering the edges as transpositions of endvertices. It is known from Denes' results that ´ the permutation of a tree is a full cyclic for any edge ordering. As a corollary, Denes counted up ´ the number of representations of a full cyclic permutation by means of product of the minimal number of transpositions. Moreover, a graph with an edge ordering which the permutation is a full cyclic is characterized by graph embedding. In this article, we consider an analogy of these results for signed graphs and hyperoctahedral groups. We give a necessary and sufficient condition for a signed graph to have an edge ordering such that the permutation is an even (or odd) full cyclic. We show that the edge ordering of the signed tree with some loops always gives an even (or odd) full cyclic permutation and count up the number of representations of an odd full cyclic permutation by means of product of the minimal number of transpositions.

Keywords: signed graph, hyperoctahedral group, signed permutation Mathematics Subject Classification : 05A05, 05C05, 05C22

DOI: 10.5614/ejgta.2023.11.2.7

1. Introduction

1.1. Background

Let n be a positive integer. Suppose that G = (VG, EG) is a graph and V^G = [n] := {1, . . . , n}. We associate an edge e = {i, j} ∈ E^G with the transposition τ^e := (i j) ∈ Sn, where Sⁿ denotes

Received: 26 December 2022, Revised: 14 April 2023, Accepted: 28 May 2023.

the symmetric group of degree n.

An edge ordering of a graph \(\mathcal{G} \leq_{\omega}\) is a linear order on \(E_{\mathcal{G}}\), denoted as a sequence \(\omega = (e_1, \ldots, e_m)\) in which \(e_i \leq_{\omega} e_j\) if \(i \leq j\). For an edge ordering \(\omega = (e_1, \ldots, e_m)\), we give the product \(\pi_{\omega} \coloneqq \tau_{e_m} \cdots \tau_{e_1} \in \mathfrak{S}_n\).

Definition 1.1. An edge ordering \(\omega\) is a full cyclic permutation ordering if the product \(\pi_{\omega} \in \mathfrak{S}_n\) is a cyclic permutation of length n.

We can characterize a graph with a full cyclic permutation ordering by studying the orbit and the sign of \(\pi_{\omega}\).

Proposition 1.2. If a graph \(\mathcal{G}\) has a full cyclic permutation ordering, then \(\mathcal{G}\) is connected and the Betti number \(\beta(\mathcal{G}) := |E_{\mathcal{G}}| - |V_{\mathcal{G}}| + 1\) is even.

For graphs with full cyclic permutation ordering, the following theorem by Dénes is known.

Theorem 1.3 (Dénes [4, §2, Theorem 1]. See also [8, §2, Lemma], [9, §2, Lemma 2.1]). Given a graph \(\mathcal{G}\), the following are equivalent.

• (i) Any edge ordering of G is a full cyclic permutation ordering.
• (ii) \(\mathcal{G}\) is a tree.

Dénes gives this theorem to count up the number of representations of a cyclic permutation of length n by means of a product of a minimal number of transpositions, and obtains the following corollary.

Corollary 1.4 (Dénes [4, §2, Corollary]). The number of representations of a cyclic permutation of length n by means of a product of n-1 transpositions is \(n^{n-2}\).

The author and Tsujie [10] also characterize graphs having a full cyclic permutation ordering in terms of graph embedding.

1.2. The hyperoctahedral group

In this article, we discuss these arguments in the case of the hyperoctahedral group \(\mathfrak{H}_n\), the Weyl group of type \(B_n\). It is a natural idea since \(\mathfrak{S}_n\) is known as the Weyl group of type \(A_{n-1}\).

Let \(I_n := \{-n, \dots, -1, 1, \dots, n\}\). The hyperoctahedral group \(\mathfrak{H}_n\) is a subgroup of the symmetric group \(\mathfrak{S}_{I_n}\) of \(I_n\), defined by

\[\mathfrak{H}_n := \Big\{ \ \eta \in \mathfrak{S}_{I_n} \ \Big| \ \eta(-i) = -\eta(i) \ \text{for all} \ i \in I_n \ \Big\}.\]

An element \(\eta \in \mathfrak{H}_n\), called a signed permutation, is expressed as

\[\eta = \begin{pmatrix} 1 & 2 & \cdots & n \\ \eta(1) & \eta(2) & \cdots & \eta(n) \end{pmatrix}\]

since \(\eta\) is determined by values at integers in [n]. In particular, given a permutation in \(\mathfrak{S}_n\), the signed permutation in \(\mathfrak{S}_n\) is naturally determined. Thus we can consider \(\mathfrak{S}_n\) to be a subgroup of \(\mathfrak{S}_n\).

The hyperoctahedral groups are well studied (cf. [1, 2, 5, 6, 7, 11]). Here we recall some that are necessary.

There are three types of signed transpositions in \(\mathfrak{H}_n\). For i, j be distinct numbers in [n] and \(\epsilon \in \{+, -\}\), which we consider as a multiplicative group of order two in the natural way, we say that

\[(i \epsilon j) \coloneqq \begin{pmatrix} 1 & \cdots & i & \cdots & j & \cdots & n \\ 1 & \cdots & \epsilon j & \cdots & \epsilon i & \cdots & n \end{pmatrix}\]

is a positive transposition if \(\epsilon = +\) and a negative transposition if \(\epsilon = -\). Note that we can consider a positive transposition (i + j) as a transposition in \(\mathfrak{S}_n\) and abbreviate it as \((i \ j)\). For \(i \in [n]\), we say that

\[(i-i) := \begin{pmatrix} 1 & \cdots & i & \cdots & n \\ 1 & \cdots & -i & \cdots & n \end{pmatrix}\]

is an inversion transposition.

The finite group \(\mathfrak{H}_n\) is generalized by these signed transpositions, but only some positive transpositions and one inversion transposition are sufficient for the generator. Also, The group \(\mathfrak{H}_n\) is isomorphic to the semidirect product \(\mathfrak{S}_2^n \rtimes \mathfrak{S}_n\) (the wreath product \(\mathfrak{S}_2 \wr \mathfrak{S}_n\)). The group \(\mathfrak{S}_2^n\) is regarded as the group generalized by inversion transpositions. Let \(\eta \in \mathfrak{H}_n\), using the relation for signed transpositions given below, we can find \(\sigma_1 \in \mathfrak{S}_2^n\) and \(\sigma_2 \in \mathfrak{S}_n\) such that \(\eta = \sigma_1 \sigma_2\) (more on this later Example 2.3).

Lemma 1.5. Let \(i, j, k \in [n]\) be distinct integers and \(\epsilon \in \{+, -\}\). Then the following three claims hold:

(T-1) \[(i-j) = (i-i)(j-j)(i j);\]

(T-2) \[(i \epsilon j)(j - j) = (i - i)(i \epsilon j);\]

(T-3) \[(i \epsilon j)(k-k) = (k-k)(i \epsilon j)\].

A signed permutation is decomposed uniquely into a product of commuting signed cycles. Let \(i_1, \ldots, i_l\) be distinct numbers in [n] and \(\epsilon_1, \ldots, \epsilon_l \in \{+, -\}\), given such a signed cycle of length l

\[\sigma = \begin{pmatrix} i_1 & i_2 & \cdots & i_{l-1} & i_l \\ \epsilon_1 i_2 & \epsilon_2 i_3 & \cdots & \epsilon_{l-1} i_l & \epsilon_l i_1 \end{pmatrix}, \tag{1}\]

we say that \(\sigma\) is an even l-cycle if \(\epsilon_1 \cdots \epsilon_l = +\) and an odd l-cycle if \(\epsilon_1 \cdots \epsilon_l = -\). In the case of l = n, the signed cycle \(\sigma\) is called an even (resp. odd) full cyclic permutation. Note that a cyclic permutation in \(\mathfrak{S}_n\) is an even cyclic permutation in \(\mathfrak{S}_n\). In addition, formula (1) is written as

\[\sigma = (i_1 \,\varepsilon_1 i_2 \,\varepsilon_2 i_3 \,\cdots \,\varepsilon_{l-1} i_l)_{\varepsilon_l}, \tag{2}\]

where \(\varepsilon_i := \epsilon_1 \cdots \epsilon_i\). Also, we obtain the representation of an even cycle as the product of transpositions as follows:

\[(i_1 \varepsilon_1 i_2 \varepsilon_2 i_3 \cdots \varepsilon_{l-1} i_l)_{\perp} = (i_1 \epsilon_1 i_2)(i_2 \epsilon_2 i_3) \cdots (i_{l-1} \epsilon_{l-1} i_l).\] (3)

We know the following relation for signed cycles and inversion transpositions.

Lemma 1.6. Suppose that \(i_1, \ldots, i_l \in I_n\) have different absolute values and \(\varepsilon \in \{+, -\}\). Then the following three claims hold:

(C-1) \[(i_1 i_2 \cdots i_l)_{\varepsilon} = (i_2 \cdots i_l \varepsilon i_1)_{\varepsilon};\]

(C-2) \[(i_1-i_1)(i_1 \cdots i_l)_{\varepsilon} = (i_1 \cdots i_l)_{\varepsilon}(i_l-i_l) = (i_1 \cdots i_l)_{-\varepsilon}\]

In other words, multiplying a signed cycle by one appropriate inversion transposition changes the even-oddness.

The representation of a signed permutation as the product of signed cycles determines the conjugacy class in \(\mathfrak{H}_n\). The conjugacy class of \(\mathfrak{H}_n\) are parameterized by pair of two integer partition \((\lambda, \mu)\) such that \(|\lambda| + |\mu| = n\), and those containing even and odd n-cycle are represented by ((n), 0) and (0, (n)), respectively.

1.3. Signed graph

We introduce the signed graph to consider an analogy of Dénes' results for \(\mathfrak{H}_n\). Here, define a signed graph as a quadruple \(\mathcal{G}=(V_{\mathcal{G}},E_{\mathcal{G}}^+,E_{\mathcal{G}}^-,L_{\mathcal{G}})\), where \(V_{\mathcal{G}}=[n]\), \(E_{\mathcal{G}}^+\) and \(E_{\mathcal{G}}^-\) are collections consisting of unordered pairs of elements in \(V_{\mathcal{G}}\), and \(L_{\mathcal{G}}\) is a subset of \(V_{\mathcal{G}}\). An element in \(V_{\mathcal{G}}\) is called a vertex, an element in \(E_{\mathcal{G}}^+\) (resp. \(E_{\mathcal{G}}^-\)) is called a positive (resp. negative) edge, and an element in \(L_{\mathcal{G}}\) is called a loop. Denote the set \(E_{\mathcal{G}}^+ \sqcup E_{\mathcal{G}}^- \sqcup L_{\mathcal{G}}\) by \(E_{\mathcal{G}}\), whose element is called an edge.

For a signed graph \(\mathcal{G}=(V_{\mathcal{G}},E_{\mathcal{G}}^+,E_{\mathcal{G}}^-,L_{\mathcal{G}})\), let \(\bar{\mathcal{G}}=(V_{\bar{\mathcal{G}}},E_{\bar{\mathcal{G}}})\) denote an unsigned multigraph such that \(V_{\bar{\mathcal{G}}}=V_{\mathcal{G}},\ E_{\bar{\mathcal{G}}}=E_{\mathcal{G}}^+\sqcup E_{\mathcal{G}}^-\). A signed tree is a graph \(\mathcal{T}=(V_{\mathcal{T}},E_{\mathcal{T}}^+,E_{\mathcal{T}}^-,L_{\mathcal{T}})\) such that \(E_{\mathcal{T}}^+\cap E_{\mathcal{T}}^-=L_{\mathcal{T}}=\emptyset\) and the unsigned graph \(\bar{\mathcal{T}}\) is a tree.

For every edge \(e \in E_{\mathcal{G}}\), define a signed transposition \(\tau_e \in \mathfrak{H}_n\) by

\[\tau_e := \begin{cases} (i \ j), & \text{if } e = \{i, j\} \in E_{\mathcal{G}}^+, \\ (i - j), & \text{if } e = \{i, j\} \in E_{\mathcal{G}}^-, \\ (i - i), & \text{if } e = i \in L_{\mathcal{G}}. \end{cases}\]

Let \(\omega = (e_1, \dots, e_m)\) be an edge ordering of a signed graph \(\mathcal{G}\) (a linear order on \(E_{\mathcal{G}}\)). We give a product \(\pi_{\omega} := \tau_{e_m} \cdots \tau_{e_1} \in \mathfrak{H}_n\).

Definition 1.7. An edge ordering of \(\mathcal{G}\) \(\omega\) is an even (resp. odd) full cyclic permutation ordering if \(\pi_{\omega}\) is an even (resp. odd) full cyclic permutation.

1.4. Main results

The main results are as follows:

Theorem 1.8. Given a signed graph G, the following are equivalent.

• (i) G has an even (resp. odd) full cyclic permutation ordering.
• (ii) \(\bar{\mathcal{G}}\) has a full cyclic permutation ordering and \(|L_{\mathcal{G}}|\) is even (resp. odd).

Theorem 1.9. Given a signed graph G, the following are equivalent.

• (i) Any edge ordering of G is an even (resp. odd) full cyclic permutation ordering.
• (ii) \(\bar{\mathcal{G}}\) is a tree and \(|L_{\mathcal{G}}|\) is even (resp. odd), that is, \(\mathcal{G}\) is a signed tree with even (resp odd) loops.

Corollary 1.10.

• (A) The number of representations of an even n-cycle by means of a product of n-1 transpositions is \(n^{n-2}\).
• (B) The number of representations of an odd n-cycle by means of a product of n transpositions is \(n^n\).

More general results are known about Corollary 1.10. Let W be a well-generalized complex reflection group of rank n with Coxeter number h. Then the number of factorizations of a fixed Coxeter element \(c \in W\) into a product of n reflections is given by the following formula (see [3, n, Formula n):

\[\#\Big\{ (\tau_n,\ldots,\tau_1) \; \Big| \; \tau_i \text{ is a reflection in } W \text{, the product } \tau_n\cdots\tau_1 \text{ is equal to } c \; \Big\} = \frac{n!}{|W|}h^n.\]

For the hyperoctahedral group \(\mathfrak{H}_n\), since \(|\mathfrak{H}_n| = 2^n n!\) and h = 2n, the value of the above formula is \(n^n\). In this paper, we prove Corollary 1.10 by counting the number of sequences consisting of n-1 (resp. n) transpositions such that the product is an even (resp. odd) n-cycle.

Note that Chapuy and Stump [3, §1, Theorem 1.1] give the formula for the exponential generating function of factorizations of a fixed Coxeter element into a product of reflections.

The organization of this paper is as follows. In Section 2, we discuss the representation of \(\pi_{\omega}\) and prove Theorem 1.8. In Section 3, we prove Theorem 1.9 and Corollary 1.10.

2. Edge orderings

2.1. The representation of the product obtained from the edge ordering

In this subsection, we prove a key lemma about the representation of the permutation \(\pi_{\omega}\). Let \(\mathcal{G} = (V_{\mathcal{G}}, E_{\mathcal{G}}^+, E_{\mathcal{G}}^-, L_{\mathcal{G}})\) be a signed graph.

Definition 2.1. For an edge ordering \(\omega\) of \(\mathcal{G}\), define \(\varphi(\omega)\) as an edge ordering of \(\bar{\mathcal{G}}\) obtained by excluding loops from \(\omega\). For an edge ordering \(\bar{\omega}\) of \(\bar{\mathcal{G}}\), define \(\varphi^{-1}(\bar{\omega})\) as the set of edge orderings \(\omega\) of \(\mathcal{G}\) such that \(\varphi(\omega) = \bar{\omega}\).

Define the projection

\[\Phi: \mathfrak{H}_n \cong \mathfrak{S}_2^n \rtimes \mathfrak{S}_n \ni (\sigma_1, \sigma_2) \mapsto \sigma_2 \in \mathfrak{S}_n.\]

Let \(\omega\) be an edge ordering of \(\mathcal{G}\). Since

\[\Phi((i+j)) = \Phi((i-j)) = (i j), \quad \Phi((i-i)) = 1,\]

where i, j are distinct integers in [n] and 1 is the identity element of \(\mathfrak{S}_n\), the permutation \(\pi_{\varphi(\omega)}\) is equal to \(\Phi(\pi_{\omega})\).

Lemma 2.2. For a signed graph \(\mathcal{G}\), let \(\omega\) be an edge ordering of \(\mathcal{G}\). There exist some inversion transpositions \(\nu_1, \ldots, \nu_r \in \mathfrak{H}_n\) such that \(\pi_\omega = \nu_1 \cdots \nu_r \pi_{\varphi(\omega)}\) and \(r \equiv |L_{\mathcal{G}}| \pmod{2}\).

Proof. Let \(\omega = (e_1, \dots, e_m)\) denote an edge ordering of \(\mathcal{G}\). Since \(\pi_\omega \in \mathfrak{H}_n \cong \mathfrak{S}_2^n \rtimes \mathfrak{S}_n\), there exist \(\sigma_1 \in \mathfrak{S}_2^n\) and \(\sigma_2 \in \mathfrak{S}_n\) uniquely such that \(\pi_\omega = \sigma_1 \sigma_2\). We see that \(\sigma_2 = \varPhi(\pi_\omega) = \pi_{\varphi(\omega)}\). To show the latter of the statement, define the group homomorphism \(\Psi : \mathfrak{H}_n \to \{1, -1\}\) by

\[\Psi(\tau) = \begin{cases} -1, & \text{if } \tau \text{ is an inversion transposition,} \\ 1, & \text{otherwise,} \end{cases}\]

for a signed transposition \(\tau \in \mathfrak{H}_n\), where \(\{1, -1\}\) is a multiplicative group of order two in the natural way. Then we have

\[\Psi(\pi_{\omega}) = \Psi(\tau_{e_1}) \cdots \Psi(\tau_{e_m}) = (-1)^{|L_{\mathcal{G}}|},\]

where \(\omega=(e_1,\ldots,e_m)\). On the other hand, since \(\sigma_1\in\mathfrak{S}_2^n\), there exist inversion transpositions \(\nu_1,\ldots,\nu_r\) such that \(\sigma_1=\nu_1\cdots\nu_r\). Hence we get

\[\Psi(\pi_{\omega}) = \Psi(\sigma_1)\Psi(\sigma_2) = \Psi(\nu_1)\cdots\Psi(\nu_r) = (-1)^r.\]

Thus \(r \equiv |L_{\mathcal{G}}| \pmod{2}\).

Example 2.3. Assume that \(\pi_{\omega} = (1\ 2)(2\ -2)(2\ -3)(3\ -4)(5\ -5)(3\ 5)\), then \(\pi_{\varphi(\omega)} = (1\ 2)(2\ 3)(3\ 4)(3\ 5)\). The representation given by Lemma 2.2 is obtained in the following steps using Lemma 1.5:

Step 1. Move all inversion transpositions contained in \(\pi_{\omega}\) to the left by (T-2) or (T-3).

• Step 2. Change all negative transpositions contained in π^ω to the product of two inversion transpositions and one positive transposition by (T-1).
• Step 3. Move all inversion transpositions resulting from Step 2 to the left by (T-2) or (T-3).

Therefore, we obtain

\[\begin{split} \pi_{\omega} &= (1\ 2)(2\ -2)(2\ -3)(3\ -4)(5\ -5)(3\ 5) \\ &= (1\ -1)(5\ -5)\cdot (1\ 2)(2\ -3)(3\ -4)(3\ 5) \\ &= (1\ -1)(5\ -5)\cdot (1\ 2)\cdot (2\ -2)(3\ -3)(2\ 3)\cdot (3\ -3)(4\ -4)(3\ 4)\cdot (3\ 5) \\ &= (1\ -1)(5\ -5)(1\ -1)(3\ -3)(1\ -1)(4\ -4)\cdot (1\ 2)(2\ 3)(3\ 4)(3\ 5) \\ &= (1\ -1)(3\ -3)(4\ -4)(5\ -5)\cdot \pi_{\varphi(\omega)}. \end{split}\] (by Step 3)

2.2. The condition to have a full cyclic permutation ordering

Now, we prove one of the main theorems, the condition for a signed graph to have a full cyclic permutation ordering.

Theorem 2.4 (Restatement of Theorem 1.8). Given a signed graph G, the following are equivalent.

• (i) G has an even (resp. odd) full cyclic permutation ordering.
• (ii) G¯ has a full cyclic permutation ordering and |LG| is even (resp. odd).

We devise this theorem in two propositions.

Proposition 2.5. Let G be a signed graph. If ω is an even (resp. odd) full cyclic permutation ordering of G, then φ(ω) is a full cyclic permutation ordering of G¯ and |LG| is even (resp. odd).

Proof. Suppose that ω is an even (resp. odd) full cyclic permutation ordering. By Lemma 2.2, there exist inversion transpositions ν1, . . . , ν^r such that π^ω = ν¹ · · · νrπφ(ω) and r ≡ |LG| (mod 2). We know that φ(ω) is a full cyclic permutation ordering as follows by (2), (3) and Lemma 1.6:

\[\pi_{\varphi(\omega)} = \Phi(\pi_{\omega}) = \Phi((i_1 \ \varepsilon_1 i_2 \ \varepsilon_2 i_3 \ \cdots \ \varepsilon_{n-1} i_n)_{\varepsilon})\] \[= \Phi((i_1 \ \varepsilon i_1)(i_1 \ \epsilon_1 i_2)(i_2 \ \epsilon_2 i_3) \cdots (i_{n-1} \ \epsilon_{n-1} i_n))\] \[= (i_1 \ i_2)(i_2 \ i_3) \cdots (i_{n-1} \ i_n)\] \[= (i_1 \ i_2 \ \cdots \ i_n)_+,\]

where i1, . . . , iⁿ are distinct integers in [n], ϵ1, . . . , ϵn−¹ ∈ {+, −}, εⁱ = ϵ¹ · · ·ϵⁱ .

Moreover, we see that r is even (resp. odd) by Lemma 1.6. Thus |LG| is also even (resp. odd).

Proposition 2.6. Let G be a signed graph. If ω¯ is a full cyclic permutation ordering of G¯ and |LG| is even (resp. odd), then any edge ordering in φ −1 (¯ω) is an even (resp. odd) full cyclic permutation ordering of G.

Proof. Assume that \(|L_{\mathcal{G}}|\) is even (resp. odd) and let \(\bar{\omega}\) be a full cyclic permutation ordering of \(\bar{\mathcal{G}}\). For any edge ordering \(\omega'\) in \(\varphi^{-1}(\bar{\omega})\), there exist inversion transpositions \(\nu_1, \ldots, \nu_r\) such that

\[\pi_{\omega'} = \nu_1 \cdots \nu_r \pi_{\varphi(\omega')} = \nu_1 \cdots \nu_r \pi_{\bar{\omega}}\]

by Lemma 2.2, where r is even (resp. odd). Since \(\pi_{\bar{\omega}}\) is an even full cyclic permutation in \(\mathfrak{H}_n\), we know that \(\pi_{\omega'}\) is an even (resp. odd) full cyclic permutation by Lemma 1.6. Hence \(\omega'\) is an even (resp. odd) full cyclic permutation ordering of \(\mathcal{G}\).

Since an unsigned graph with a full cyclic permutation ordering is connected, we get the following corollary:

Corollary 2.7. If a signed graph \(\mathcal{G}\) has an odd full cyclic permutation ordering and \(|E_{\mathcal{G}}| = n\), then \(\bar{\mathcal{G}}\) is a tree and \(|L_{\mathcal{G}}| = 1\), that is, \(\mathcal{G}\) is a signed tree with one loop.

3. Signed trees and full cyclic permutations

Now, we prove the remaining main theorems.

3.1. The proof of Theorem 1.9

Theorem 3.1 (Restatement of Theorem 1.9). Given a signed graph \(\mathcal{G}\), the following are equivalent.

• (i) Any edge ordering of G is an even (resp. odd) full cyclic permutation ordering.
• (ii) \(\bar{\mathcal{G}}\) is a tree and \(|L_{\mathcal{G}}|\) is even (resp. odd), that is, \(\mathcal{G}\) is a signed tree with even (resp odd) loops.

First we show (i) \(\Rightarrow\) (ii). We know that if a signed graph \(\mathcal{G}\) has an even (resp. odd) full cyclic permutation ordering, then \(|L_{\mathcal{G}}|\) is even (resp. odd) by Proposition 2.5. Therefore we need to show the following.

Proposition 3.2. If any edge ordering of G is an even (resp. odd) full cyclic permutation ordering, then \(\overline{G}\) is a tree.

Proof. We prove the contraposition. Suppose that \(\bar{\mathcal{G}}\) is not a tree. Since a signed tree with a full cyclic permutation ordering is connected, we can assume that \(\bar{\mathcal{G}}\) has a cycle. Let \(\mathcal{C}=(V_{\mathcal{C}},E_{\mathcal{C}})\) denote the minimal cycle (minimal number of vertices) that \(\bar{\mathcal{G}}\) has, where

\[V_{\mathcal{C}} = \{v_1, \dots, v_l\}, \quad E_{\mathcal{C}} = \{c_1, \dots, c_l\},\]

with \(c_i \coloneqq \{v_i, v_{i+1}\}\) \((v_{l+1} = v_1)\). Let \(I_{\bar{\mathcal{G}} \setminus \mathcal{C}}(v_l)\) denote the set of edges of \(\bar{\mathcal{G}}\) that are incident to the vertex \(v_l\) but not contained in \(E_{\mathcal{C}}\). Then we see that there exists no edge in \(I_{\bar{\mathcal{G}} \setminus \mathcal{C}}(v_l)\) such that it is incident to \(v_1\). If \(b_0 \in I_{\bar{\mathcal{G}} \setminus \mathcal{C}}(v_l)\) is incident to \(v_1\), then \(\bar{\mathcal{G}}\) has a cycle of length 2 consisting of \(b_0\) and \(c_l\). We have l=2 by minimality of \(\mathcal{C}\). Thus there exist three edges between \(v_1\) and \(v_l\). It contradicts to the construction of \(\bar{\mathcal{G}}\).

Define an edge ordering of \(\bar{\mathcal{G}}\) \(\omega_0\) by

\[\omega_0 \coloneqq (c_1, \ldots, c_{l-1}, d_1, \ldots, d_t, c_l, b_1, \ldots, b_s),\]

where

\[\begin{split} I_{\bar{\mathcal{G}}\backslash\mathcal{C}}(v_l) &= \{b_1,\dots,b_s\}, \quad E_{\mathcal{G}}\backslash(I_{\bar{\mathcal{G}}\backslash\mathcal{C}}(v_l)\cup E_{\mathcal{C}}) = \{d_1,\dots,d_t\}. \end{split}\] Then \(E_{\mathcal{G}} = \{b_1,\dots,b_s,d_1,\dots,d_t,c_1,\dots,c_l\}.\) We obtain \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Hence ω⁰ is not a full cyclic permutation ordering. Therefore edge orderings in φ −1 (ω0) are neither even nor odd full cyclic permutation orderings of G.

Now, we show (ii) ⇒ (i) by induction on the number of vertices n. We can suppose that n ≥ 2. Suppose that G¯ is a tree and |LG| is even (resp. odd). Let ω = (e1, . . . , em) be an edge ordering of G. Assume that e¹ is a loop. Since G is a connected graph with at least two vertices, there exists an edge of G which is not a loop. Let ω ′ = (ek, . . . , em, e1, . . . , ek−1) denote an edge ordering of G such that e^k is not a loop. Since

\[\pi_{\omega'} = \tau_{e_{k-1}} \cdots \tau_{e_1} \tau_{e_m} \cdots \tau_{e_k} = (\tau_{e_{k-1}} \cdots \tau_{e_1}) \pi_{\omega} (\tau_{e_{k-1}} \cdots \tau_{e_1})^{-1},\]

that is, π^ω and πω′ are conjugate, ω is a full cyclic permutation ordering if and only if ω ′ is a full cyclic permutation ordering. Hence we can assume e¹ is not a loop.

Let e¹ = {i1, j1} and G\e¹ denote the graph excluding the edge e¹ from G. The graph G\e¹ has two connected components T¹ and T² which are signed trees with some loops. We assume that T¹ includes i¹ and T² includes j1. Let ω¹ = (c1, . . . , cp) and ω² = (d1, . . . , dq) denote the edge orderings of T¹ and T² which are obtained by restricting ω to E^T1 and E^T2 , where p + q = m − 1. Since ω¹ and ω² are full cyclic permutation orderings by induction hypothesis, we can write π^ω1 and π^ω2 as

\[\pi_{\omega_1} = \nu_1 \cdots \nu_s (i_1 \ i_2 \ \cdots \ i_l)_+,\]
\[\pi_{\omega_2} = \mu_1 \cdots \mu_t (j_1 \ j_2 \ \cdots \ j_k)_+,\]

where ν1, . . . , νs, µ1, . . . , µ^t are distinct inversion transpositions, i1, . . . , i^l , j1, . . . , j^k are distinct integers in [n], s + t ≡ |LG| (mod 2) and l + k = n by Lemma 2.2.

Since the signed transposition corresponding to an edge of T¹ and the signed transposition corresponding to an edge of T² are commutative, we obtain

\[\pi_{\omega} = \pi_{\omega_{1}} \pi_{\omega_{2}} \tau_{e_{1}}\] \[= \nu_{1} \cdots \nu_{s} \mu_{1} \cdots \mu_{t} (i_{1} i_{2} \cdots i_{l})_{+} (j_{1} j_{2} \cdots j_{k})_{+} (i_{1} \epsilon j_{1})\] \[= \nu'_{1} \cdots \nu'_{r} (i_{1} i_{2} \cdots i_{l})_{+} (j_{1} j_{2} \cdots j_{k})_{+} (i_{1} j_{1})\] \[= \nu'_{1} \cdots \nu'_{r} (i_{1} j_{2} \cdots j_{k} j_{1} i_{2} \cdots i_{l})_{+},\]

where ν ′ 1 , . . . , ν′ r are inversion transpositions and r ≡ |LG| (mod 2). Thus ω is an even (resp. odd) full cyclic permutation ordering if |LG| is even (resp. odd).

Now, Theorem 1.9 is completely proven.

3.2. The proof of Corollary 1.10

Corollary 3.3 (Restatement of Corollary 1.10).

• (A) The number of representations of an even n-cycle by means of a product of n-1 transpositions is \(n^{n-2}\).
• (B) The number of representations of an odd n-cycle by means of a product of n transpositions is \(n^n\).

We can obtain (A) as the corollary of Corollary 1.4. Now, we prove (B).

Let x be the number of representations of an odd full cyclic permutation by means of a product of n transpositions. Suppose that

\[X \coloneqq \Big\{ \left( \tau_n, \dots, \tau_1 \right) \; \Big| \; \tau_i \text{ is a signed transposition, the product } \tau_n \cdots \tau_1 \text{ is an odd full cyclic permutation } \Big\}.\]

Since the number of odd full cyclic permutations is \((n-1)! \cdot 2^{n-1}\), we know \(|X| = x \cdot (n-1)! \cdot 2^{n-1}\). Define the set consisting of signed graphs by

\[Y \coloneqq \left\{ \left. \mathcal{G} = (V_{\mathcal{G}}, E_{\mathcal{G}}^+, E_G^-, L_{\mathcal{G}}) \; \right| \; V_{\mathcal{G}} = [n], \; |E_{\mathcal{G}}| = n, \; \mathcal{G} \; \text{has an odd full cyclic permutation ordering} \; \right\}\]

and define the set consisting of pairs of graphs and edge orderings of them by

\[Z \coloneqq \Big\{ \left. (\mathcal{G}, \omega) \; \middle| \; \mathcal{G} \in Y, \; \omega \text{ is an odd full cyclic permutation ordering of } \mathcal{G} \; \Big\}.\]

Since we have

\[Y = \left\{ \left. \mathcal{G} = (V_{\mathcal{G}}, E_{\mathcal{G}}^+, E_{G}^-, L_{\mathcal{G}}) \, \right| \, V_{\mathcal{G}} = [n], \, |L_{\mathcal{G}}| = 1, \, \bar{\mathcal{G}} \text{ is a tree } \right\}\]

by Corollary 2.7, we obtain

\[Z = \Big\{ \left. (\mathcal{G}, \omega) \; \middle| \; \mathcal{G} \in Y, \; \omega \text{ is an edge ordering of } \mathcal{G} \; \Big\}.\]

Since \(|Y| = n^{n-2} \cdot n \cdot 2^{n-1}\) (Cayley's formula), we get \(|Z| = |Y| \cdot n! = n^{n-1} \cdot 2^{n-1} \cdot n!\). Also, since there exists a bijection between X and Z, we see |X| = |Z|. Hence \(x = n^n\).

Acknowledgment

The author wishes to thank everyone who advised for this paper by reading the archives and joining in the discussion.

References

• [1] A.V. Borovik and A. Borovik, Mirrors and Reflections, Springer New York, New York, NY, 2010.
• [2] R.W. Carter, Conjugacy classes in the Weyl group, Compositio Mathematica 25 (1972), 60.
• [3] G. Chapuy and C. Stump, Counting factorizations of Coxeter elements into products of reflections, Journal of the London Mathematical Society 90 (2014), no. 3, 919–939.
• [4] J. Denes, The representation of a Permutation as the product of a minimal number of transpositions, and its connection with the theory of graphs, Publications of the Mathematical Institute of the Hungarian Academy of Sciences 4 (1959), 63–70.
• [5] J.E. Humphreys, Reflection Groups and Coxeter Groups, 1 ed., Cambridge University Press, June 1990.
• [6] A. Kerber, Representations of Permutation Groups I: Representations of wreath products and applications to the representation theory of symmetric and alternating groups, Lecture Notes in Mathematics, vol. 240, Springer Berlin Heidelberg, 1971.
• [7] A. Kerber, Representations of Permutation Groups II, Lecture Notes in Mathematics, vol. 495, Springer Berlin Heidelberg, 1975.
• [8] P. Moszkowski, A Solution to a Problem of Denes: a Bijection Between Trees and Factorizations of Cyclic Permutations, European Journal of Combinatorics 10 (1989), no. 1, 13–16.
• [9] B. Pawlowski, Chromatic symmetric functions via the group algebra of Sn, Algebraic Comibinatorics 5 (2022), no. 1, 1–20.
• [10] S. Tsujie and R. Uchiumi, Upper Embeddability of Graphs and Products of Transpositions Associated with Edges, December 2022, arXiv:2211.05422 [math].
• [11] A. Young, On Quantitative Substitutional Analysis 5, Proceedings of the London Mathemathical Society s2-31 (1930), no. 1, 273–288.