3 Random permutation graphs

3.1 Permutation graphs

Let \(V\) be a finite set and \(\mathfrak {S}_{V} = \{ \pi : V \rightarrow V \text{ bijective}\} \) the set of permutations of \(V\).

We define a graph associated to a family of permutations.

Definition 3.1.1

Let \(r \geq 1\) be an integer. To a family \(\vec{\pi } = (\pi _1, \ldots , \pi _r) \in \mathfrak {S}_{V}^r\) we associate a dart-like structure on \(V\) by taking:

\(D = V \times \{ 1, \ldots , r\} \times \{ -1,+1\} \)
for \((x,i,\epsilon ) \in D\), we let \(\mathrm{start}(x,i,\epsilon ) = x\), \(\mathrm{end}(x,i,\epsilon ) = \pi _i^\epsilon (x)\) and \(\mathrm{rev}(x,i,\epsilon ) = (\pi _i^\epsilon (x),i,-\epsilon )\).

Proof ▶

We check that

\begin{equation*} \mathrm{start}(\mathrm{rev}(x,i,\epsilon )) = \mathrm{start}(\pi _i^\epsilon (x),i,-\epsilon ) = \pi _i^\epsilon (x) = \mathrm{end}(x,i,\epsilon ) \end{equation*}

and

\begin{equation*} \mathrm{end}(\mathrm{rev}(x,i,\epsilon )) = \mathrm{end}(\pi _i^\epsilon (x),i,-\epsilon ) = \pi _i^{-\epsilon }(\pi _i^\epsilon (x)) = x = \mathrm{start}(x,i,\epsilon ) \end{equation*}

and

\begin{equation*} \mathrm{rev}(\mathrm{rev}(x,i,\epsilon )) = \mathrm{rev}((\pi _i^\epsilon (x),i,-\epsilon )) = (\pi _i^{-\epsilon }(\pi _i^\epsilon (x)),i,–\epsilon ) = (x,i,\epsilon ). \end{equation*}

Definition 3.1.2

Let \(r \geq 1\) be an integer. To a family \(\vec{\pi } \in \mathfrak {S}_{V}^r\) we associate a graph \(G_{\vec{\pi }}\) on \(V\) by taring the graph associated to the dart-like structure associated to \(\vec{\pi }\).

Lemma 3.1.3

Let \(r \geq 1\) be an integer and take \(\vec{\pi } = (\pi _1, \ldots , \pi _r) \in \mathfrak {S}_{V}^r\). Then, for any \(x, y \in V\),

\begin{equation*} \mathrm{dartSet}(x,y) = \{ (x,i,\epsilon ): y = \pi _i^\epsilon (x)\} . \end{equation*}

Lemma 3.1.4

Let \(r \geq 1\) be an integer and take \(\vec{\pi } = (\pi _1, \ldots , \pi _r) \in \mathfrak {S}_{V}^r\). Then, for any \(x \in V\),

\begin{equation*} \mathrm{dartSet}(x) = \{ (x,i,\epsilon ): 1 \leq i \leq r, \epsilon = \pm 1\} . \end{equation*}

Lemma 3.1.5

The graph \(G_{\vec{\pi }}\) is regular of degree \(2r\).

[I need to decide the conventions about the side of the actions below]

Definition 3.1.6

For \(\pi \in \mathfrak {S}_{V}\), we define an operator \(u_\pi : V^{\mathbb {C}} \rightarrow V^{\mathbb {C}}\) by letting, for \(f : V \rightarrow \mathbb {C}\),

\begin{equation*} \forall x \in V, u_\pi f(x) = f(\pi ^{-1}(x)) \end{equation*}

Lemma 3.1.7

For \(\pi \in \mathfrak {S}_{V}\), the operator \(u_\pi \) is a unitary operator on \(\ell ^2(V)\) and \(u_\pi ^*=u_\pi ^{-1}=u_{\pi ^{-1}}\).

Lemma 3.1.8

Let \(r \geq 1\) be an integer. For any family \(\vec{\pi } = (\pi _1, \ldots , \pi _r) \in \mathfrak {S}_{V}^r\), the adjacency operator \(a_{\vec{\pi }}\) of \(G_{\vec{\pi }}\) can be written as

\begin{equation*} a_{\vec{\pi }} = \sum _{i=1}^r (u_{\pi _i} + u_{\pi _i}^*). \end{equation*}

Proof ▶

We have by definition of the adjacency operator for a function \(f : V \rightarrow \mathbb {C}\) and \(x \in V\),

\begin{equation*} af(x) = \sum _{d \in \mathrm{dartSet}(x)} f(\mathrm{end}(d)) = \sum _{i=1}^r \sum _{\epsilon = \pm 1} f(\pi _i^\epsilon (x)) = \sum _{i=1}^r (f(\pi _i^{-1}(x)) + f(\pi _i(x))) \end{equation*}

which leads to the conclusion as we recognise \(u_{\pi _i}\) and \(u_{\pi _i^{-1}} = u_{\pi _i}^*\).

3.2 Random permutations

Let \(r, N \geq 1\) be integers. In what follows, we write \(\mathfrak {S}_{N}\) for the set of permutations of \([N]\) and \(\mathfrak {S}_{N}^r\) the product space of \(r\)-tuples of elements of \(\mathfrak {S}_{N}\).

Definition 3.2.1

We equip \(\mathfrak {S}_{N}^r\) with the uniform probability measure which we denote as \(\mathrm{Prob}_{N,r}\). We denote the corresponding expectation by \(\mathbb {E}_{N,r}\).

Lemma 3.2.2

For any function \(F : \mathfrak {S}_{N}^r \rightarrow \mathbb {C}\),

\begin{equation*} \mathbb {E}_{N,r}[F(\vec{\pi })] = \frac{1}{N!^r} \sum _{\vec{\pi } \in \mathfrak {S}_{N}^r} F(\vec{\pi }). \end{equation*}

Proof ▶

This is the expectation for a uniform measure, noting that the cardinal of \(\mathfrak {S}_{N}\) is \(N!^r\).

Definition 3.2.3

Denote \(\mathfrak {d}= 2r\). Let \(\mathcal{G}_{\mathfrak {d},N}\) be the set of \(\mathfrak {d}\)-regular graphs with \(V(G) = [N]\), equiped with the power-set \(\sigma \)-algebra. We define a probability measure \(\mathrm{Prob}_{N,\mathfrak {d}}^{G}\) on \(\mathcal{G}_{\mathfrak {d},N}\) by pushing forward \(\mathrm{Prob}_{N,r}\) with the function \(\mathfrak {S}_{N}^r \rightarrow \mathcal{G}_{\mathfrak {d},N}\) defined in Definition 3.1.2.

3.3 Words in random permutation matrices

The aim of this section is to prove [ , a formula for the expectation of traces of words in random permutation matrices.

3.3.1 Statement of the result and notations

We fix an integer \(r \geq 1\).

Definition 3.3.1

Let \(G\) be a group with neutral element \(\mathbf{1}\). To a family \((x_1, \ldots , x_r) \in G^r\) we associate a family \((x_0, \ldots , x_{2r}) \in G^{2r+1}\) by letting \(x_0= \mathbf{1}\) and for \(1 \leq i \leq r\), \(x_{r+i} := x_i^{-1}\).

Definition 3.3.2

We denote as \(\mathbf{W}_r\) the set of finite words \(w = w_1 \ldots w_q\) in the letters \(\{ 0, \ldots 2r\} \). The length \(|w| = q\) of a word \(w\) is its number of letters.

Definition 3.3.3

Let \(w = w_1 \ldots w_q \in \mathbf{W}_r\) and \(G\) be a group with neutral element \(\mathbf{1}\). The word map \(w : G^r \rightarrow G\) is defined by letting, for each \((x_1, \ldots , x_r) \in G^r\), \(w(x_1, \ldots , x_r) = x_{w_1} \ldots x_{w_q}\) with the numbering convention from Definition 3.3.1.

Let \(N \geq 1\). In what follows, we denote as \(\mathcal{M}_N(\mathbb {C})\) the set of \(N \times N\) matrices with complex coefficients. If \(M \in \mathcal{M}_N(\mathbb {C})\), we denote as \(M_{i,j}\) its coefficient \((i,j)\). We denote as \(\mathrm{Tr_N}M = \sum _{i=1}^N M_{i,i}\) the usual trace on \(\mathcal{M}_N(\mathbb {C})\).

Definition 3.3.4

The normalised trace \(\mathrm{tr}_N: \mathcal{M}_N(\mathbb {C})\rightarrow \mathbb {C}\) is defined by \(\mathrm{tr}_N:= \frac{1}{N} \mathrm{Tr_N}\).

Definition 3.3.5

Let \(q \geq 1\) be an integer. For \(1 \leq j \leq q-1\), we define \(r_{r,q,j} := \min (r, \lfloor q/(j+1) \rfloor )\) and we define the polynomial \(g_{r,q}(x) = \prod _{j=1}^{q-1} (1-j x)^{r_{r,q,j}}\).

Lemma 3.3.6

For any \(q \geq 1\), the degree of \(g_{r,q}\) is at most \(q(1+\log r)-1\).

Proof ▶

By comparaison with an integral, we have

\begin{align*} \deg g_{r,q} = \sum _{j=1}^{q-1} r_{r,q,j} \leq \int _1^q \min (r, q/x) \d x \leq q(1+\log r) - \min (r,q). \end{align*}

We are now ready to state the main result of this section.

Theorem 3.3.7

Let \(q \geq 1\). Let \(w \in \mathbf{W}_r\) be a word of length at most \(q\). There exists a polynomial \(f_w\), of degree at most \(q(1+\log r)\), such that for any \(N \geq q\),

\begin{equation*} \mathbb {E}_{N,r}[\mathrm{tr}_Nw(\vec\pi )] = \frac{f_w(1/N)}{g_q(1/N)}. \end{equation*}