Math 202C: Lecture 2

*** Problems in this lecture due April 10 at 23:59 ***

In this lecture, we remain in the setting of the symmetric group S=\mathrm{Aut}\{1,\dots,n\} but we will change the geometry on this group. More precisely, instead of identifying S with its Cayley graph as generated by the set of adjacent transpositions, we will identify the symmetric group with its Cayley graph as generated by the full conjugacy class of transpositions,

T = \{(s\ t) \in S \colon 1 \leq s < t \leq n\}.

Let \mathrm{d} denote the corresponding metric on S, so that \mathrm{d}(\rho,\sigma) is the minimal number r such that there exist transpositions \tau_1,\dots,\tau_r \in T with

\sigma = \rho\tau_1 \dots \tau_r.

As before, write |\pi|=\mathrm{d}(\iota,\pi) for the distance from the identity permutation \iota to a given permutation \pi.

Problem 2.1. Prove that |\pi|=n-\mathrm{cyc}(\pi), where \mathrm{cyc}(\pi) is the number of factors in the disjoint cycle decomposition of \pi.

Identifying S with \mathrm{Cay}(S,T), the symmetric group becomes a graded graph: it decomposes into a disjoint union

S = L_0 \sqcup L_1 \sqcup \dots \sqcup L_{n-1}

in which

L_r = \{\pi \in S \colon |\pi|=r\} = \{\pi \in S \colon \mathsf{cyc}(\pi)=n-r\}

is the sphere of radius r centered at \iota, and L_r is an independent set, meaning that no two of its points are adjacent vertices. Moreover, if \rho,\sigma \in S are adjacent vertices, then we have \rho \in L_r and \sigma \in L_s with |r-s|=1. The decomposition of a group into concentric spheres is a general thing that happens whenever one chooses a generating set; a special feature of this particular situation is that each sphere further decomposes into a disjoint union of conjugacy classes,

L_r = \bigsqcup\limits_{\substack{\alpha \vdash n \\ \ell(\alpha)=n-r}}C_\alpha.

Here, we are indexing the conjugacy classes of S by the set \Lambda of partitions of n. More precisely, the notation \alpha \vdash n means that \alpha is a decomposition of n into a sum of \ell(\alpha) positive integers, without regard to order of the terms. Every permutation \pi \in S gives a partition \mathsf{type}(\pi)\vdash n obtained from the lengths of the cycles in its disjoint cycle decomposition; conversely, for any partition \alpha \vdash n the corresponding fiber C_\alpha =\mathsf{type}^{-1}(\alpha) is a conjugacy class in S.

Let us now construct the analogue of Mallows measure corresponding to the all-transpositions geometry. This is called the Ewens measure on permutations: by definition, it is the Gibbs measure

\mathbb{P}(\sigma) = \frac{q^|\sigma|}{Z} = \frac{q^{n-\mathsf{cyc}(\sigma)}}{Z}

corresponding to a statistical mechanical system whose states \sigma are permutations of 1,\dots,n with the potential energy of \sigma being inversely proportional to its number of cycles. The partition function is

Z= \sum\limits_{\sigma \in S} q^{|\sigma|} = q^n\sum\limits_{\sigma \in S} q^{-\mathsf{cyc}(\sigma)},

or equivalently

Z=\sum\limits_{k=0}^n \begin{bmatrix} n \\ k \end{bmatrix} q^{-k},

where \begin{bmatrix} n \\ k \end{bmatrix} is the Stirling number of the first kind, which counts permutations in S=\mathrm{Aut}\{1,\dots,n\} whose disjoint cycle factorization has k components. This in turn gives

Z= (1+q)(1+2q) \dots (1+(n-1)q),

corresponding to the fact that Stirling Numbers of the first kind are the coefficients of the falling factorial polynomial.

Problem 2.2. Show that the expected number of cycles in a random permutation under Ewens measure is

1 + \sum\limits_{j=1}^{n-1} \frac{1}{1+jq}.

Deduce from this that the expected number of cycles in a uniformly random permutation of 1,\dots,n is the harmonic number

H_n=1+\frac{1}{2} + \dots + \frac{1}{n}.

The all-transpositions geometry on permutations has many features which make it easier to understand than the adjacent-transpositions geometry. Perhaps the most significant of these is that it is “Euclideanizable.” Right, that’s not a real word – here is what is meant more precisely.

Consider the full forward cycle \gamma=(1\ 2\ \dots\ n) in the symmetric group S. In the all-transpositions geometry, we have |\gamma|=n-1, and the number of geodesics \iota \to \gamma is \mathrm{Cay}_{n-1}, where

\mathrm{Cay}_n = (n+1)^{n-1}

is the nth Cayley number. Taking this formula for granted, we can calculate the number of geodesics from the identity to any permutation (hence the number of geodesics between any two permutations) as follows.

Problem 2.3. Let \pi be any permutation in the conjugacy class C_\alpha of S. Show that the number of geodesics \iota \to \pi is

{n \choose \alpha_1-1,\dots,\alpha_\ell-1} \prod\limits_{k=1}^\ell \mathrm{Cay}_{\alpha_k-1},

where \ell=\ell(\alpha).

To Euclideanize the all-transpositions geometry on the symmetric group, we give a rule which allows one to systematically select a distinguished geodesic between every pair of points. To do so, let us label the edges of \mathrm{Cay}(S,T) as follows: we mark each edge corresponding to the transposition (s\ t) with t, the larger of the two numbers swapped. Thus, emanating from every vertex of the graph we have one 2-edge, two 3-edges, three 4-edges, etc. Call a walk on the Cayley graph strictly monotone if the labels of the edges it traverses form a strictly increasing sequence. Thus, an r-step strictly monotone walk \rho \to \sigma corresponds to an equation of the form

\sigma=\rho(s_1\ t_1) \dots (s_r\ t_r), \quad 2\leq t_1 < \dots < t_r \leq n

in S.

Problem 2.4. Prove that for any \pi \in S, there exists a unique strictly monotone walk \iota \to \pi, and that the length of this walk is |\pi|. Conclude that there exists a unique strictly monotone walk between every pair of points in S, and that this walk is a geodesic.

This more or less marks the end of my efforts to get you thinking about the combinatorics of permutations; after this we will move on to the algebraic aspects of the symmetric group and its representations. The campaign for the elementary beauty and unexpected subtlety of permutations met with mixed success: there were interesting follow-up discussions with some students, whereas other pairs of eyes glazed over as the minds behind them fell into the “I already know this stuff” trap, which is one the of the more pernicious lies you can tell yourself.

Here is one final push. Our ever-curious Lani was recently asking about posets, and whether there is any active research being conducted on them these days. The answer is definitely “yes,” and though I don’t really work in the area I do have one burning question about posets which keeps me up at night. The question is about finding a partial order on permutations of a fixed genus.

From our Euclideanized perspective, genus is a metric invariant which measures “flatness” of triangles S as generated by the full conjugacy class of transpositions. More precisely, let \pi,\rho,\sigma be three distinct permutations in S=\mathrm{Aut}\{1,\dots,n\}. There are two oriented strictly monotone triangles formed by these three points, namely \rho \to \pi \to \sigma \to \rho and \sigma \to \pi \to \rho \to \sigma. It may happen \pi lies on a geodesic \rho \to \sigma, in which case both of these triangles are flat, and have perimeter

|\pi^{-1}\rho| + |\rho^{-1}\sigma| + |\sigma^{-1}\pi| = 2|\rho^{-1}\sigma|.

In general, the oriented triangle \rho \to \pi \to \sigma \to \rho is a cycle in a bipartite graph, so necessarily has even perimeter: we have

|\pi^{-1}\rho| + |\rho^{-1}\sigma| + |\sigma^{-1}\pi| = 2|\rho^{-1}\sigma| + 2g(\rho,\pi,\sigma)

for some nonnegative integer g(\rho,\pi,\sigma) which we call the genus of the triple (\rho,\pi,\sigma). At the other extreme from flatness, it may be that \pi,\rho,\sigma are pairwise antipodal points, i.e. the distance between each pair of them is the diameter of S, in which case the above equation becomes

3(n-1)=2(n-1)+2g(\rho,\pi,\sigma),

giving a maximal genus of

g(\pi,\rho,\sigma) = \lfloor \frac{n-1}{2} \rfloor.

Problem 2.5. Show that a triple of pairwise antipodal points in S exists if and only if n is odd.

Since

g(\rho,\pi,\sigma)=g(\iota,\rho^{-1}\pi,\rho^{-1}\sigma),

it is natural to view genus as a function g(\pi,\sigma):=g(\iota,\pi,\sigma) on pairs of permutations. Going even further, let us fix the second argument to be \sigma=\gamma, where \gamma=(1\ 2\ \dots\ n) is the full forward cycle, and define the genus of a permutation by g(\pi):=g(\pi,\gamma). Then, we obtain a corresponding decomposition of the symmetric group

S = \bigsqcup\limits_{k=0}^{\lfloor \frac{n-1}{2} \rfloor} S_g

in which S_g is the set of permutations of genus g. The set S_0 of “planar” permutations consists precisely of those \pi which lie on a geodesic \iota \to \gamma, and these permutations have a special feature: the disjoint cycle decomposition of any \pi \in S_0 is a noncrossing partition of \{1,\dots,n\}, and in fact this map from genus zero permutations into noncrossing permutations is bijective. There is also a very natural partial order on S_0 which can be described as follows: we have \pi \leq \sigma if and only if \pi and \sigma lie on a common geodesic \iota \to \gamma, and a particle emanating from \iota and traveling along this geodesic passes through \pi before passing through \sigma. This is a special case of the geodesic partial order which can be defined relative to any two vertices of a connected graph, and in this case it coincides exactly with the reverse refinement order on noncrossing partitions.

Now the question is: what is the higher genus analogue of this partial order? How can we define a poset structure by some uniform recipe which feels good for all values of g, subject to the condition that our recipe reverts to the above at g=0? This is an open question. The most natural thing that I can think of is the following: given two permutations \pi,\sigma \in S_g, we declare \pi \leq \sigma if and only if they lie on a common genus g triangle two of whose vertices are \iota and \gamma, and a particle emanating from \iota and traveling along the perimeter of this triangle encounters \pi before encountering \sigma. Whether or not this actually defines a partial order on S_g is not clear to me, but my fluid intelligence is declining from its peak while yours is cresting. So, if you want to discuss further please feel free to get in touch.

Published by Jonathan Novak

Mathematician at UC San Diego.

Leave a Reply