![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
We define a dual of a graph, generalizing the definition of Goulden et al. (2002), which only applies to trees; then we reprove their main result using our new definition. We in fact give two characterizations of the dual: a graph-theoretic one and an algebraic one, showing that they are in fact the same, and are also the same (on trees) as the topological dual developed by Goulden and Yong. Goulden and Yong use their dual to define a bijection between the vertex labeled trees and the factorizations of the permutation into
transpositions, showing that their bijection has a particular structural property. We give a combinatorial, non-topological, proof of their result, using our dual.
1 Introduction
The basic objects we investigate are factorizations of permutations into transpositions. By we mean the symmetric group on the set
; for us, all multiplication is from left to right. To refer to “factorizations” precisely we introduce the notion of a transposition sequence: a transposition sequence (over
) is a sequence of transpositions in
.
Example 1.1
The sequence is a transposition sequence over
.
Dénes Citation[1] showed that there are exactly factorizations of
into
transpositions. Since it is well-known that there are also
vertex labeled trees on
vertices, Dénes suggested the project of finding interesting bijections between these factorizations and these trees. While interesting in its own right, the project posed by Dénes is further motivated by fitting it into a broader context suggested by Citation[2] and Citation[3]. A factorization of
into
transpositions is in fact what is called a minimal transitive factorization; any permutation of
can be factored into its minimal transitive factorizations. Minimal transitive factorizations are of interest because of their connection to topology (for example, see Citation[4] and Citation[5]); this work also has connections to more recent work in topology, for example Citation[6].
Definition 1.2
– | Let | ||||
– | Let |
Using this terminology, Dénes’ challenge is to find bijections between and
. Moszkowski Citation[7] found a bijection in 1989; then in 1993 Goulden and Pepper Citation[8] found a different bijection. However, arguably the nicest bijection is developed in 2002 by Goulden and Yong Citation[3]; in this bijection, various structural properties are preserved. An example of a structural property is this: if we consider a factorization and the tree it is mapped to, the number of transpositions which are consecutive pairs (i.e.
or of the form
) in the factorization is the same as the number of leaves in the tree. Further nice properties of this bijection, including enumerative consequences, are discussed in Citation[3]. Essential in the bijection of Citation[3] is their definition of the dual of a tree, defined topologically; a similar dual was defined in 1999 by Herando Martín Citation[9]. The main point of our work is an alternative definition of the dual and an alternative combinatorial proof of the Goulden and Yong result, which avoids topology; in fact we will give two equivalent definitions of our dual, which, on trees, are equivalent to the dual of Citation[3].
In Section 2 we give an algebraic definition of the dual. Section 3 describes a graph-theoretic interpretation of transposition sequences. In Section 4, in Theorem 4.7, we give one of our main results, an alternate proof of the main result from Citation[3] using our dual. Section 5 gives an equivalent graph-theoretic definition of the dual. In Section 6 we prove that our dual (when restricted to trees) is in fact the same as the topological dual of Citation[3]. In Section 7 we investigate a technical property related to the graph-theoretic dual. Our dual is interesting because it applies to all finite graphs, coincides with the dual of Citation[3] for trees, and allows us to give an alternate combinatorial proof of the main result from Citation[3].
2 Algebraic dual
For permutations and
, let
be the conjugate
.
Definition 2.1
The Algebraic Dual of is
.
We will often denote the Algebraic Dual of a transposition sequence by
.
Example 2.2
We calculate the Algebraic Dual of , the transposition sequence of Example 1.1.
Continuing, we see that the Algebraic Dual
is
.
We now prove three important properties of the Algebraic Dual, in Lemmas 2.3, 2.4, and 2.5.
Lemma 2.3
For any transposition sequence and its Algebraic Dual
, the product
is the inverse of the product
.
Proof
Basically we multiply out the transpositions and cancel appropriately, as shown in the following calculation.
Lemma 2.4
For any transposition sequence we have
.
Proof
Suppose and
. Consider any
, and we show that
.
Let be
, and let
be
.
Lemma 2.5
Proof
Using the definition of the Algebraic Dual and properties of conjugation, we can make the following calculation.
Note that Lemmas 2.3 and 2.4 would hold if we defined the Algebraic Dual of a transposition sequence to simply be its reverse
, but Lemma 2.5 would fail; Lemma 2.5 will be crucial to later developments.
The next lemma gives an interesting alternative way to view the Algebraic Dual.
Lemma 2.6
For a transposition sequence and its Algebraic Dual
,
where
and
.
Proof
We can see that the last equality is true by viewing as first mapping
to
, then
to
, then
to
. Similarly
is mapped to
, and furthermore, any other element (besides
and
) is mapped to itself.□
This lemma provides a visual way to understand the Algebraic Dual, which we illustrate via an example. Consider Example 2.2 where we have the transposition sequence and its Algebraic Dual
. The product of the transpositions in
yields the permutation
; this result can also be achieved by starting with
, the identity permutation written in inline notation, and successively swapping the bottom numbers according to
, i.e. to get
, then
, and so on till we get
. Lemma 2.6 tells us that if we want to get the same result by swapping the top elements of the inline notation, then the Algebraic Dual provides the required swaps; for example, if we use
from Example 2.2, then we start with the identity
, then get
, then get
, and continue till we get
, which is the permutation
.
3 Graph interpretation
We describe a standard way that transposition sequences are viewed as labeled graphs, using this interpretation in Section 4 in order to define the bijection, and in Section 5 in order to define the Graph Dual. For us, a graph will always mean a finite, loop-less graph, with multi-edges allowed. A labeled graph is a graph whose vertices are labeled by
(each vertex receiving a distinct label), and whose
edges are labeled by
(each edge receiving a distinct label). As is commonly done (for example, in Citation[3]) we view
, a transposition sequence over
, as a labeled graph with vertex set
, with
edges: For each transposition
we create a corresponding edge between
and
, labeled by
. displays the transposition sequence of Example 1.1 as a graph.
Following usual definitions, we define a trail to be a non-empty sequence such that each
is a vertex, each
is an edge, and no edge is repeated (vertices may be repeated). Notice that trails are ordered with a start vertex of
and end vertex of
. For us, the trails of fundamental interest are given in the next definition.
Definition 3.1
Consider a labeled graph and any vertex . The Minimal Increasing Greedy Trail (MIGT) starting at
is the trail
such that
is
, and each edge
is the edge incident to
with the smallest label which is larger than all the labels on edges
(
) which are incident to
. The trail ends when there is no such edge
. This (unique) trail is referred to by
.
Example 3.2
Referring to the graph in , is the following trail:
, where we write
to refer to the unique edge with label
.
4 Alternate proof for Goulden/Yong bijection
In this section we use our framework to describe a bijection between the vertex labeled trees and the factorizations of into
transpositions. Following Citation[3] we define the bijection as the composition of a relabeling function with our dual. We will show, in Section 6, that our dual is the same as that of Citation[3], so in fact, the bijection we are describing is the same as that of Citation[3]. We give an alternate proof, using our dual, that the bijection possesses the structural properties described in Citation[3].
4.1 The bijection
For the purposes of this paper, we define a Minimal Transitive Factorization over to be a transposition sequence of length
whose product is a single cycle involving all the elements of
. Immediate from Dénes Citation[1] we have the following theorem; the coherence of the subsequent definitions and discussion depends on this fact.
Theorem 4.1
Citation[1] A transposition sequence is a Minimal Transitive Factorization over if and only if it is a tree whose vertices are
In Definition 1.2 we defined ; we now define
to be the set of length
transposition sequences over
with product
. By Theorem 4.1,
and
consist of trees. For example, the left side of is the tree
, which is in
.
Definition 4.2
We define the functions ,
, and
.
– |
| ||||
– |
| ||||
– | Our desired bijection |
See for an example of the function. For an example of the entire bijection
, see Figure 2 of Citation[3]. Since
is a bijection (by Lemma 2.4), to show
is a bijection, it is enough to show that
is a bijection.
Lemma 4.3
is a bijection.
Proof
To see that is a bijection we define its inverse function. We begin with a vertex labeled tree. For every vertex
, except the vertex labeled “1”, let
be the edge incident to
that is closest to “1”. If vertex
is labeled by
, then label edge
by
. Erase all the vertex labels except “1”. Now label the vertices using the MIGTs, i.e. follow
from “1” to its final vertex, labeling it “2”, then follow
from “2” to determine which vertex to label “3”, and so on.□
As noted by other authors (e.g. Citation[3]), since it is known that , the bijection
shows that
.
4.2 The structural property of the bijection
Now we review a structural property of the bijection, defined in Citation[3], showing that the bijection has this property.
Definition 4.4
Supposing is a Minimal Transitive Factorization over
, for any
, we can write the product of
as
.
– | We let | ||||
– | We let |
Definition 4.5
Suppose that is some transposition in the Minimal Transitive Factorization
.
– |
| ||||
– |
|
For example, consider and let . Since removing edge
from the tree leads to the vertex partition
,
. In the corresponding permutation cycle
, the transposition
creates the partition
, so
. In Citation[3], they refer to
as the difference index and
as the edge-deletion index.
Now we show that the bijection has the desired structural property, by first proving a stronger property of the Algebraic Dual.
Theorem 4.6
Suppose is a Minimal Transitive Factorization over
, and suppose
is its Algebraic Dual. Then for
we have that
and
.
Proof
We show (
then follows using Lemma 2.4). We proceed by induction on the length of the transposition sequence, considering the inductive step. Consider
and suppose
. So
is two trees, say
and
, where
is the tree containing
and
is the tree containing
. The product of
is some permutation cycle
and the product of
is some permutation cycle
. Thus the product of
is
and so by Lemma 2.3, the product of
is
. We now demonstrate that
.
Consider the case in which . Then
, where we get the latter equality by noting that
and recalling the value of
.
Now we consider the case in which , and suppose, without loss of generality, that
is in
. We remark that for
and
we will keep the edge labels coming from the original tree
(so for example, edge
in
is labeled
, not
, and
in
is labeled
, not
); all the relevant definitions and facts work in the same manner for such edge labelings. Let the Algebraic Dual of
be
, whose product, by Lemma 2.3, is the permutation cycle
. Suppose the Algebraic Dual of
is
; note that since
consists of two disjoint graphs, for any
in
,
is indeed the same in
and
. Suppose
, where
(understanding
to be
). We can conclude that
, where the first equality holds by inductive hypothesis and second by definition, recalling the value of
. Now consider the entire tree
, consisting of
and
joined by edge
. When edge
is removed from
, all the vertices of
will be in the component with vertex
, so to get
we just add the vertices of
to the appropriate piece of the above partition, so
. We now show that
is the same partition. By Lemma 2.5 (the crucial use of this lemma),
. So if
, then
, and if
then
. In either case, recalling that
we see that
is the same as
.□
The bijection first takes a transposition sequence
to its Algebraic Dual
. By Theorem 4.6, for every
, the partitions
and
are the same, and so immediately,
. Then
just rearranges the labels, so any transposition
in
has a corresponding edge
in the tree
such that
; technically we defined
for transposition sequences, i.e. labeled trees, however the same basic definition works for a tree in
. Thus we have given an alternative proof of the following theorem, which was the main result of Citation[3].
Theorem 4.7
The function is a bijection with the following property: Suppose
is in
, and the tree
has edges
. Then the multi set
is the same as the multi-set
.
We can now revisit a point made in the introduction. From the last theorem we know that the number of 1’s in each multi-set is the same, which tells us that in the bijection which maps “factorizations” to trees, the number of consecutive pairs in the factorization is the same as the number of leaves in the tree. Furthermore, for each transposition in the factorization, where
and
are
steps apart in the cycle
, there is a corresponding edge in the tree whose removal creates a sub-tree with
vertices and a sub-tree with at least
vertices.
5 Graph Dual
We will now define the Graph Dual, which we will show is equivalent to the Algebraic Dual.
Lemma 5.1
For any transposition sequence , its product
maps
to
if and only if the MIGT (when viewing the transposition sequence as a graph) starting at
, ends at
.
For example, trail from starts at 3 and ends at 2, as the lemma requires, since the product of the transposition sequence pictured in is
.
Definition 5.2
Given a labeled graph , by
, the Graph Dual, we mean the following labeled graph:
– | The vertices of | ||||
– | The edges of |
For example, consider the graph of , with its MIGTs displayed. Since and
both use edge
, the Graph Dual will have an edge with label
between vertices 1 and 3; the full Graph Dual is shown in . Notice that the Algebraic Dual from Example 2.2 viewed as a graph is exactly the graph in . In the next theorem we point out that this is always true.
Theorem 5.3
For any transposition sequence, its Algebraic Dual is the same as its Graph Dual.
Proof
Suppose the transposition sequence is , with Algebraic Dual
, and Graph Dual
. We show that for any
,
. Supposing
and
, then by Lemma 2.6
, where
and
. Consider the MIGTs of the labeled graph
; by Lemma 5.1,
starts at
and ends at
, and
starts at
and ends at
. Thus when edge
is added to the graph,
is extended by moving along the edge labeled
to now end at
, while
is extended by moving along the edge labeled
to now end at
. So
, and we are done.□
Since the Algebraic Dual and the Graph Dual are the same, we may use the term dual to refer to either of the equivalent notions.
6 Goulden-Yong Dual
In Citation[3], they define a dual that applies only to trees, using topological methods. When restricted to trees, we show that their dual is the same as our dual, and thus our bijection is in fact the same as that of Citation[3].
Definition 6.1
Citation[3] Given a labeled tree on
vertices, its Circle Chord Diagram, is the following structure:
A circle, together with distinct points on the circle, labeled by the numbers
, in the clockwise direction, drawing a chord between
and
if there is an edge between
and
in
.
Consider the tree shown in (it is the same as the example in Citation[3]); its MIGTs are drawn in, but can be ignored for now. The Circle Chord Diagram for the tree of is shown in . Notice that the chords in are non-crossing, i.e. any two chords either do not meet, or only meet at a vertex on the circle. For a tree with vertices and non-crossing chords, its Circle Chord Diagram has the following properties:
– | The | ||||
– | The chords break up the region inside the circle into |
In Citation[3], multiplication in is from right-to-left, however their labeling of the transpositions in a transposition sequence increases from left-to-right. We wanted both the labeling and the multiplication to go in the same order. To make our work fit most smoothly with their work, notice that we have opted to keep their labeling from left-to-right, but have changed multiplication to also go from left-to-right. Thus in Citation[3], when they refer to factorizations of
into
transpositions, in our terminology, they are referring to exactly the set
from Definition 1.2. Recall that from Theorem 4.1 we know that the transpositions sequences in
are trees. Thus it makes sense to find the Circle Chord Diagram of a transposition sequence from
. In Citation[3] (see Theorem 2.2) the following theorem is proved.
Theorem 6.2
Citation[3] For any transposition sequence its Circle Chord Diagram has the following properties:
1. | The chords are non-crossing. | ||||
2. | At each of the |
The properties of the theorem can all be verified of the example in ; for example, at vertex 3, turning clockwise, we encounter decreasing labels: 4, then 3, then 1. We now give a definition that basically comes from Citation[3], calling it the Goulden–Yong Dual; the coherence of the definition depends on Theorem 6.2.
Definition 6.3
Citation[3] Given a tree from , its Goulden–Yong Dual is determined as follows:
– | Draw its Circle Chord Diagram, which divides the disk into | ||||
– | Place a new vertex in each region, labeling the vertex | ||||
– | Create an edge between two new vertices if their regions have a chord in common, labeling the edge by the label on the chord. |
For example, the Goulden–Yong Dual of the tree in is pictured in : The dashed edges and smaller vertices depict the original tree from the Circle Chord Diagram of , and the solid lines with larger vertices depict its Goulden–Yong Dual. Note that the Graph Dual of the tree in is exactly the Goulden–Yong Dual pictured in ; we will see that this is generally true in Theorem 6.5. As an example of the next lemma, note that the chords of region of are the ones labeled
,
, and
, exactly the same as the edges traversed by trail
.
Lemma 6.4
Suppose and
is its Circle Chord Diagram. Suppose
. Then the edges in
are exactly the edges on the boundary in region
of
.
Proof
Suppose the vertices of trail , in order, are
. Let
be the most clockwise edge at
(for example, in , edge
is the most clockwise edge at vertex
). By property 2. of Theorem 6.2,
moves along edge
from
to
. Then, again by property 2., the trail goes from
to
, along the edge that is one chord counter-clockwise from
, when turning at
(for example, in , at vertex
, the chord labeled by
is one chord counter-clockwise from the chord labeled
). As we continue we see that
traverses one of the
regions of
, moving along its boundary in a clockwise fashion, starting at
on the circle and ending at
(understanding vertex
to be the same as vertex
). That is,
consists of exactly the edges of region
.□
Theorem 6.5
For any tree from , its Goulden–Yong Dual is the same as its dual.
Proof
Consider some tree , and let
be its Circle Chord Diagram. Let
be its Graph Dual and
its Goulden–Yong Dual. Both
and
are labeled graphs with vertex set
, so it suffices to observe that for any distinct
, we have the following equivalences (where the second one follows by Lemma 6.4).
.
7 Realizability
One of the central ideas of this paper is to create a labeled graph from a transposition sequence, and then consider the relevant trails, namely the MIGTs. Thus a natural question in this context is to consider systems of trails on unlabeled graphs (formalized in Definition 7.1), and ask which ones arise as MIGTs. The main result of this section is Theorem 7.6, which exactly characterizes the systems of trails that arise as MIGTs. This section is not necessary for the alternate proof of the Goulden–Yong result; instead, it provides a further investigation of the tools used in this paper.
Definition 7.1
A Trail Double Cover of a graph is a set of trails such that:
– | A unique trail begins at each vertex, and | ||||
– | Every edge of the graph is used by exactly two trails. |
An example of a Trail Double Cover can be seen in . The next lemma shows that Definition 7.1 is interesting: it is a natural definition, which includes systems of trails that arise from MIGTs.
Lemma 7.2
The set of MIGTs of a labeled graph is a Trail Double Cover.
Proof
For the first requirement on being a Trail Double Cover, we note that there is only one MIGT trail that starts at a vertex, since there is at most one smallest edge at a vertex.
We proceed by induction on the number of edges to prove the second requirement: that each edge is used by exactly two trails. Let our graph be . For the inductive step, remove the edge
, i.e. the edge labeled by 1; call the resulting graph
. Suppose edge
in graph
consists of vertices
and
. By inductive hypothesis, in
, every edge is used by exactly two trails; the fact that the edge labels of
start at
instead of
, has no effect on the argument. Define
to be the trail
in
, and
to be
in
. Thus in
,
starts at
, follows edge
to
and then does exactly what
does in
. Likewise, in
,
goes from
to
and then follows
. The rest of the trails of
are the same as those of
. Thus
is used exactly twice, as are the rest of the edges.□
Definition 7.3
A Trail Double Cover is realizable if there is an edge labeling of the graph such that the resulting set of MIGT trails is
.
By definition, the Trail Double Cover pictured in is realizable. However the Trail Double Cover pictured in is not realizable; this point can be checked directly, however, we will see that this follows from Theorem 7.6. Though the Trail Double Cover of is not realizable, we can still see any Trail Double Cover as representing a permutation of its vertices: each trail maps its start vertex to its end vertex. We can view a Trail Double Cover in this way because a unique trail begins at each vertex, and as the next lemma shows, a unique trails ends at each vertex.
Lemma 7.4
In any Trail Double Cover, each vertex of the graph is the final vertex of a unique trail.
Proof
If the graph has vertices, then the Trail Double Cover has
trails that start at those
vertices. So it suffices to show that each vertex is the final vertex of some trail. Suppose, for contradiction, that there were a vertex
which was not the final vertex of any trail. Then the trail that starts at
contains an odd number of edges incident to
, and any other trail contains an even number of edges incident to
. This implies that in total, an odd number of edges incident to
are in use by some trail, however, this contradicts the property that in a Trail Double Cover, each edge incident to
is in use by exactly two trails.□
We give a characterization of realizability using an auxiliary digraph (i.e. directed graph). Edges in a digraph are called arcs; we will refer to the arc that starts at vertex and goes to vertex
by
. In a digraph, we refer to a directed trail as a trail that always moves in the direction of the arcs. From a Trail Double Cover we will create an auxiliary digraph by converting each one of the trails in the Trail Double Cover into a directed trail in a new digraph.
Definition 7.5
Given any Trail Double Cover on
, we define its Edge Digraph to be the following digraph:
– | Its vertices are the edges of | ||||
– | For each trail |
For example, is the Edge Digraph of the Trail Double Cover in , and 10 is the Edge Digraph of . The next theorem gives us a criterion for determining whether or not a Trail Double Cover is realizable. Applying the theorem to the Trail Double Cover of , we see that it is not realizable, since its Edge Digraph, drawn in Fig. 10, does have a directed cycle.
Theorem 7.6
A Trail Double Cover is realizable if and only if its Edge Digraph has no directed cycle.
Proof
Suppose is the graph and
is a Trail Double Cover on it. Let
be the Edge Digraph of
.
Forward Direction: Consider an edge labeling that yields . Any arc of
goes from
to
, where
and
are edges of
such that the label of
is less than the label of
. So
cannot have a directed cycle.
Backwards Direction: Supposing has no directed cycle, take any topological sort of
to arrive at an edge labeling of
. For example, the graph of has the edge digraph in , so one topological sort is 1, 2, 3, 4, 5, which corresponds to the original edge labeling of the graph in , while the other topological sort is 1, 2, 4, 3, 5, giving a different edge labeling of the graph in . Let
be
with its edges labeled according to the topological sort. We show that the set of MIGTs of
is exactly
. For any Trail Double Cover, at each vertex
we get the situation shown in Fig. 11 (left side): One trail, say
, starts at
by using edge
, one trail, say
, ends at
by using edge
, and the rest of the trails enter
by using one edge and leave by another. We let
refer to the trail that enters along
and leaves along
, for
. It is possible that some of the
trails
are not distinct, and any
and
might be multi-edges attaching the same two vertices. The related part of
is pictured in Fig. 11 (right side). In our topological sort we must have
. Now, consider any trail
in
; we show that in the topological ordering of the edges,
is an MIGT in
. Referring to Fig. 11 (left side), we can see that edge
of
, being its first edge corresponds to an edge like
of Fig. 11 (right side) and so it is the smallest edge incident to
, as required. Similarly, edge
of
corresponds to edge like
, and so it is the largest labeled edge at
, as required. Consider any intermediate edges
and
of
, both incident to vertex
; these edges correspond to some
and
in Fig. 11. We suppose the trail has been MIGT up to and including
, and show that it still is for
. The topological ordering of the edges pictured in Fig. 11 (right side) indicates that
is the next largest labeled edge, so this matches the MIGT. Thus we have shown that every trail of
is an MIGT in
. Also note that every MIGT of
is in
since being a Trail Double Cover,
used every edge twice, so there can be no more MIGTs. Thus
is exactly the set of MIGTs on
, so we have realized
.□
8 Conclusion and future work
In this paper we focused on minimal transitive factorizations of the permutation , investigating an interesting bijection. In Citation[2] a general formula is found for the number of minimal transitive factorizations of any permutation. Based on this result, they motivate the search for interesting bijections between such sets of factorizations and other sets of combinatorial interest. Making progress on this program, [Citation10] found a bijection for the minimal transitive factorizations of
, and [Citation11] found bijections for
and
; both papers used parking functions. Our hope is that our alternative definitions of the dual, which apply to any graph (not just trees), could be a useful tool for such research.
Acknowledgments
I acknowledge and thank Nikos Apostolakis for his role in this paper. We began working on this project together, but decided to publish our results separately, with different emphases. Thus, all of the results in this paper come out of discussion and work with Nikos Apostolakis. Furthermore, I thank him for having made all the figures that appear in this paper. His paper that came out of our joint work is submitted and under review, and can be found at the arXiv [Citation12]. His paper includes his interpretation and exposition of our joint work, as well as his individual contributions beyond that.
My work was supported by a PSC-CUNY Research Award (Traditional A).
References
- DénesJ., The representation of a permutation as the product of a minimal number of transpositions, and its connection with the theory of graphs Magyar Tud. Akad. Mat. Kutató Int. Közl. 41959 63–71
- GouldenI.P.JacksonD.M., Transitive factorisations into transpositions and holomorphic mappings on the sphere Proc. Amer. Math. Soc. 125 1 1997 51–60
- GouldenI.YongA., Tree-like properties of cycle factorizations J. Combin. Theory Ser. A 98 1 2002 106–117
- ArnoldV., Topological classification of trigonometric polynomials and combinatorics of graphs with an equal number of vertices and edges Funct. Anal. Appl. 30 1 1996 1–14
- GouldenI.P.JacksonD.M.VakilR., The Gromov-Witten potential of a point, Hurwitz numbers, and Hodge integrals Proc. Lond. Math. Soc. (3) 83 3 2001 563–581
- E. Duchi, D. Poulalhon, G. Schaeffer, Bijections for simple and double Hurwitz numbers,arXiv:1410.6521v1.
- MoszkowskiP., A solution to a problem of Dénes: a bijection between trees and factorizations of cyclic permutations European J. Combin. 10 1 1989 13–16
- GouldenI.P.PepperS., Labelled trees and factorizations of a cycle into transpositions Discrete Math. 113 1–3 1993 263–268
- MartínM.C.H., Complejidad de Estructuras Geométricas y Combinatorias(Ph.D. thesis)1999Universitat Politècnica de Catalunya
- KimD.SeoS., Transitive cycle factorizations and prime parking functions J. Combin. Theory Ser. A 104 1 2003 125–135
- RattanA., Permutation factorizations and prime parking functions Ann. Comb. 10 2 2006 237–254
- N. Apostolakis, A duality for labeled graphs and factorizations with applications to graph embeddings and Hurwitz enumeration, arXiv eprints:1804.01214v4 (April 2018).