guide:88e15c6edc

[math] \newcommand{\mathds}{\mathbb}[/math]

This article was automatically generated from a tex file and may contain conversion errors. If permitted, you may login and edit this article to improve the conversion.

As a final topic for this theoretical chapter, let us discuss as well the partial symmetries of graphs. To be more precise, we will associate to any graph [math]X[/math] having [math]N[/math] vertices its semigroup of partial permutations [math]\widetilde{G}(X)\subset\widetilde{S}_N[/math], which is a quite interesting object.

In order to discuss all this, let us start with something well-known, namely:

Definition

[math]\widetilde{S}_N[/math] is the semigroup of partial permutations of [math]\{1\,\ldots,N\}[/math],

[[math]] \widetilde{S}_N=\left\{\sigma:I\simeq J\Big|I,J\subset\{1,\ldots,N\}\right\} [[/math]]

with the usual composition operation for such partial permutations, namely

[[math]] \sigma'\sigma:\sigma^{-1}(I'\cap J)\simeq\sigma'(I'\cap J) [[/math]]

being the composition of [math]\sigma':I'\simeq J'[/math] and [math]\sigma:I\simeq J[/math].

Observe that [math]\widetilde{S}_N[/math] is not simplifiable, because the null permutation [math]\emptyset\in\widetilde{S}_N[/math], having the empty set as domain/range, satisfies the following formula, for any [math]\sigma\in\widetilde{S}_N[/math]:

[[math]] \emptyset\sigma=\sigma\emptyset=\emptyset [[/math]]

Observe also that our semigroup [math]\widetilde{S}_N[/math] has a kind of “subinverse” map, which is not a true inverse in the semigroup sense, sending a partial permutation [math]\sigma:I\to J[/math] to its usual inverse [math]\sigma^{-1}:J\to I[/math]. Many other algebraic things can be said, along these lines.

As a first interesting result now about [math]\widetilde{S}_N[/math], which shows that we are dealing here with some non-trivial combinatorics, not really present in the [math]S_N[/math] context, we have:

Theorem

The number of partial permutations is given by

[[math]] |\widetilde{S}_N|=\sum_{k=0}^Nk!\binom{N}{k}^2 [[/math]]

that is, [math]1,2,7,34,209,\ldots\,[/math], and we have the formula

[[math]] |\widetilde{S}_N|\simeq N!\sqrt{\frac{\exp(4\sqrt{N}-1)}{4\pi\sqrt{N}}} [[/math]]

in the [math]N\to\infty[/math] limit.

Show Proof

This is a mixture of trivial and non-trivial facts, as follows:

(1) The first assertion is clear, because in order to construct a partial permutation [math]\sigma:I\to J[/math] we must choose an integer [math]k=|I|=|J|[/math], then we must pick two subsets [math]I,J\subset\{1,\ldots,N\}[/math] having cardinality [math]k[/math], and there are [math]\binom{N}{k}[/math] choices for each, and finally we must construct a bijection [math]\sigma:I\to J[/math], and there are [math]k![/math] choices here.

(2) As for the estimate, which is non-trivial, this is something standard, and well-known, and exercise for you here to look that up, and read the proof.

■

Another result, which is trivial, but is quite fundamental, is as follows:

Proposition

We have a semigroup embedding [math]u:\widetilde{S}_N\subset M_N(0,1)[/math], given by

[[math]] u_{ij}(\sigma)= \begin{cases} 1&{\rm if}\ \sigma(j)=i\\ 0&{\rm otherwise} \end{cases} [[/math]]

whose image are the matrices having at most one nonzero entry, on each row and column.

Show Proof

This is something which is trivial from definitions, with the above embedding [math]u:\widetilde{S}_N\subset M_N(0,1)[/math] extending the standard embedding [math]u:S_N\subset M_N(0,1)[/math], given by the permutation matrices, that we have been heavily using, so far.

■

Also at the algebraic level, we have the following simple and useful fact:

Proposition

Any partial permutation [math]\sigma:I\simeq J[/math] can be factorized as

[[math]] \xymatrix@R=40pt@C=40pt {I\ar[r]^{\sigma}\ar[d]_\gamma&J\\\{1,\ldots,k\}\ar[r]_\beta&\{1,\ldots,k\}\ar[u]_\alpha} [[/math]]

with [math]\alpha,\beta,\gamma\in S_k[/math] being certain non-unique permutations, where [math]k=|Dom(\sigma)|[/math].

Show Proof

We can choose indeed any two bijections [math]I\simeq\{1,\ldots,k\}[/math] and [math]\{1,\ldots,k\}\simeq J[/math], and then complete them up to permutations [math]\gamma,\alpha\in S_N[/math]. The remaining permutation [math]\beta\in S_k[/math] is then uniquely determined by the formula [math]\sigma=\alpha\beta\gamma[/math].

■

The above result is quite interesting, theoretically speaking, allowing us to reduce in principle questions about [math]\widetilde{S}_N[/math] to questions about the usual symmetric groups [math]S_k[/math], via some sort of homogeneous space procedure. We will be back to this, later in this book.

In relation now with the graphs, we have the following notion:

Definition

Associated to any graph [math]X[/math] is its partial symmetry semigroup

[[math]] \widetilde{G}(X)\subset\widetilde{S}_N [[/math]]

consisting of the partial permutations [math]\sigma\in\widetilde{S}_N[/math] whose action preserves the edges.

As a first observation, we have the following result, which provides an alternative to the above definition of the partial symmetry semigroup [math]\widetilde{G}(X)[/math]:

Proposition

Given a graph [math]X[/math] with [math]N[/math] vertices, we have

[[math]] \widetilde{G}(X)=\left\{\sigma\in\widetilde{S}_N\Big|d_{ij}=d_{\sigma(i)\sigma(j)},\ \forall i,j\in Dom(\sigma)\right\} [[/math]]

with [math]d\in M_N(0,1)[/math] being as usual the adjacency matrix of [math]X[/math].

Show Proof

The construction of [math]\widetilde{G}(X)[/math] from Definition 9.37 reformulates as follows, in terms of the usual adjacency relation [math]i-j[/math] for the vertices:

[[math]] \widetilde{G}(X)=\left\{\sigma\in\widetilde{S}_N\Big|i-j,\exists\,\sigma(i),\exists\,\sigma(j)\implies \sigma(i)-\sigma(j)\right\} [[/math]]

But this leads to the formula in the statement, in terms of the adjacency matrix [math]d[/math].

■

In order to discuss now some examples, let us make the following convention:

Definition

In the context of the partial permutations [math]\sigma:I\to J[/math], with [math]I,J\subset\{1,\ldots,N\}[/math], we decompose the domain set [math]I[/math] as a disjoint union

[[math]] I=I_1\sqcup\ldots\sqcup I_p [[/math]]

with each [math]I_r[/math] being an interval consisting of consecutive numbers, and being maximal with this property, and with everything being taken cyclically.

In other words, we represent the domain set [math]I\subset\{1,\ldots,N\}[/math] on a circle, with [math]1[/math] following [math]1,\ldots,N[/math], and then we decompose it into intervals, in the obvious way. With this convention made, in the case of the oriented cycle, we have the following result:

Proposition

For the oriented cycle [math]C_N^o[/math] we have

[[math]] \widetilde{G}(C_N^o)=\widetilde{\mathbb Z}_N [[/math]]

with the semigroup on the right consisting of the partial permutations

[[math]] \sigma:I_1\sqcup\ldots\sqcup I_p\to J [[/math]]

which are cyclic on any [math]I_r[/math], given there by [math]i\to i+k_r[/math], for a certain [math]k_r\in\{1,\ldots,N\}[/math].

Show Proof

According to the definition of [math]\widetilde{G}(X)[/math], we have the following formula:

[[math]] \widetilde{G}(C_N^o)=\left\{\sigma\in\widetilde{S}_N\Big|d_{ij}=d_{\sigma(i)\sigma(j)},\ \forall i,j\in Dom(\sigma)\right\} [[/math]]

On the other hand, the adjacency matrix of [math]C_N^o[/math] is given by:

[[math]] d_{ij}=\begin{cases} 1&{\rm if}\ j=i+1\\ 0&{\rm otherwise} \end{cases} [[/math]]

Thus, the condition defining [math]\widetilde{G}(C_N^o)[/math] is as follows:

[[math]] j=i+1\iff\sigma(j)=\sigma(i)+1,\ \forall i,j\in Dom(\sigma) [[/math]]

But this leads to the conclusion in the statement.

■

In the case of the unoriented cycle, the result is as follows:

Proposition

For the unoriented cycle [math]C_N[/math] we have

[[math]] \widetilde{G}(C_N)=\widetilde{D}_N [[/math]]

with the semigroup on the right consisting of the partial permutations

[[math]] \sigma:I_1\sqcup\ldots\sqcup I_p\to J [[/math]]

which are dihedral on any [math]I_r[/math], given there by [math]i\to \pm_ri+ k_r[/math], for a certain [math]k_r\in\{1,\ldots,N\}[/math], and a certain choice of the sign [math]\pm_r\in\{-1,1\}[/math].

Show Proof

The proof here is similar to the proof of Proposition 9.40. Indeed, the adjacency matrix of [math]C_N[/math] is given by:

[[math]] d_{ij}=\begin{cases} 1&{\rm if}\ j=i\pm 1\\ 0&{\rm otherwise} \end{cases} [[/math]]

Thus, the condition defining [math]\widetilde{G}(C_N)[/math] is as follows:

[[math]] j=i\pm 1\iff\sigma(j)=\sigma(i)\pm 1,\ \forall i,j\in Dom(\sigma) [[/math]]

But this leads to the conclusion in the statement.

■

An interesting question is whether the semigroups [math]\widetilde{\mathbb Z}_N,\widetilde{D}_N[/math] are related by a formula similar to [math]D_N=\mathbb Z_N\rtimes\mathbb Z_2[/math]. This is not exactly the case, at least with the obvious definition for the [math]\rtimes[/math] operation, because at the level of cardinalities we have:

Theorem

The cardinalities of [math]\widetilde{\mathbb Z}_N,\widetilde{D}_N[/math] are given by the formulae

[[math]] |\widetilde{\mathbb Z}_N|=1+NK_1(N)+\sum_{p=2}^{[N/2]}N^pK_p(N) [[/math]]

[[math]] |\widetilde{D}_N|=1+NK_1(N)+\sum_{p=2}^{[N/2]}(2N)^pK_p(N) [[/math]]

where [math]K_p(N)[/math] counts the sets having [math]p[/math] cyclic components, [math]I=I_1\sqcup\ldots\sqcup I_p[/math].

Show Proof

The first formula is clear from the description of [math]\widetilde{\mathbb Z}_N[/math] from Proposition 9.40, because for any domain set [math]I=I_1\sqcup\ldots\sqcup I_p[/math], we have [math]N[/math] choices for each scalar [math]k_r[/math], producing a cyclic partial permutation [math]i\to i+k_r[/math] on the interval [math]I_r[/math]. Thus we have, as claimed:

[[math]] |\widetilde{\mathbb Z}_N|=\sum_{p=0}^{[N/2]}N^pK_p(N) [[/math]]

In the case of [math]\widetilde{D}_N[/math] the situation is similar, with Proposition 9.41 telling us that the [math]N[/math] choices at the level of each interval [math]I_r[/math] must be now replaced by [math]2N[/math] choices, as to have a dihedral permutation [math]i\to \pm_ri+ k_r[/math] there. However, this is true only up to a subtlety, coming from the fact that at [math]p=1[/math] the choice of the [math]\pm1[/math] sign is irrelevant. Thus, we are led to the formula in the statement, with [math]2N[/math] factors everywhere, except at [math]p=1[/math].

■

Summarizing, the partial symmetry group problematics leads to some interesting questions, even for simple graphs like [math]C_N^o[/math] and [math]C_N[/math]. We will be back to this.

General references

Banica, Teo (2024). "Graphs and their symmetries". arXiv:2406.03664 [math.CO].