\documentclass[ALCO,Unicode,published]{cedram} % -----packages------ \usepackage{amssymb,latexsym,amsthm,amsmath,amsfonts,mathrsfs} \usepackage{caption,color,graphicx} %\usepackage[numbers,comma,square,sort&compress]{natbib} \usepackage{hyperref} \usepackage{bbm} \usepackage{verbatim} \usepackage{stackengine} \usepackage{xcolor} \usepackage{braket} \usepackage[normalem]{ulem} % -----new commands------ \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\id}{\mathrm{id}} \newcommand{\A}{\mathbf{A}} \newcommand{\x}{\mathbf{x}} \newcommand{\y}{\mathbf{y}} \newcommand{\e}{\varepsilon} \newcommand{\Crop}{\mathrm{Crop}} \newcommand{\FF}{\mathcal{F}} \newcommand{\ZZ}{\mathcal{Z}} \newcommand{\Bin}{\mathrm{Bin}} \newcommand{\YD}{\mathrm{YD}} \newcommand{\len}{\mathrm{len}} \newcommand{\hgt}{\mathrm{ht}} \newcommand{\LL}{\mathbf{L}} \newcommand{\II}{\mathbf{I}} \newcommand{\is}{\mathrm{lis}} \newcommand{\BB}{\mathcal{B}} \newcommand{\Hom}{\mathrm{Hom}} \newcommand{\M}{\mathcal{M}} %\renewcommand{\d}{\mathrm{d}} \newcommand{\supp}{\mathrm{supp}} \newcommand{\ii}{\mathbf{i}} \newcommand{\jj}{\mathbf{j}} \newcommand{\calM}{\mathcal{M}} \newcommand{\calN}{\mathcal{N}} \newcommand{\gen}[1]{\langle{#1}\rangle^+} \DeclarePairedDelimiter{\ceil}{\lceil}{\rceil} % ------large binomial fraction------ \xof{a}{b} \newcommand{\scb}{\scalebox} \newcommand\xof[3][1ex]{\ensurestackMath{% \setbox0=\hbox{$#2$}% \setbox2=\hbox{$#3$}% \kern\wd0\kern-\dimexpr#1\relax% \stackinset{r}{#1}{b}{\dimexpr#1-1ex}{\mathrlap{#3}}{% \stackinset{l}{#1}{t}{\dimexpr#1-1ex}{\mathllap{#2}}{\bigg/}% }% \kern-\dimexpr#1\relax\kern\wd2% }} \fboxsep=.1pt % ------Title------ \title[Binomial Cayley graphs and applications to dynamics on finite spaces]{Binomial Cayley graphs and applications to dynamics on finite spaces} % ------Authors------ \author[\initial{B.} \lastname{Bassols Cornudella}]{\firstname{Bernat} \lastname{Bassols Cornudella}} \address{ Department of Mathematics\\ Imperial College London\\ SW7 2AZ\\ London\\ UK} \email{bernat.bassols-cornudella20@imperial.ac.uk} \author[\initial{F.} \lastname{Viganò}]{\firstname{Francesco} \lastname{Viganò}} \address{ Department of Mathematics\\ Imperial College London\\ SW7 2AZ\\ London\\ UK} \email{f.vigano21@imperial.ac.uk} \keywords{Cayley graphs, spectral graph theory, representation theory, symmetric group, cyclic group, dynamics on finite spaces} \subjclass{05C25, 05E15} % \datepublished{} \datepublished{2024-09-03} \begin{document} \begin{abstract} \emph{Binomial Cayley graphs} are obtained by considering the binomial coefficient of the weight function of a given Cayley graph and a natural number. We introduce these objects and study two families: one associated with symmetric groups and the other with powers of cyclic groups. We determine various combinatorial properties of these graphs through the spectral analysis of their adjacency matrices. In the case of symmetric groups, we establish a relation between the multiplicity of the null eigenvalue and longest increasing sub-sequences of permutations by means of the RSK correspondence. Finally, we consider dynamical arrangements of finitely many elements in finite spaces, which we refer to as \emph{particle-box systems}. We apply the results obtained on binomial Cayley graphs in order to describe their degeneracy. \end{abstract} \maketitle \section{Introduction}\label{section.introduction} Let us consider a set of $m$ different boxes and a collection of $n$ labelled particles. On this setup, we play a game against a bot that repeatedly arranges all particles across the different boxes. In general, these particles can be laid out in $m^n$ different configurations, allowing several of them in the same box, or leaving some boxes empty. Before the game begins, the bot fixes once and for all a probability distribution $p$ on the set of all possible $m^n$ configurations and an integer $k\le n$. \\ We play as an external observer interested in the disposition of the $n$ particles. However, on every round the bot only allows us to observe where $k$ particles of our choice have been allocated. That is, the game unfolds over infinitely many independent rounds consisting of: \begin{enumerate} \item We select $k$ of the $n$ particles. \item The bot samples an arrangement from $p$ and lays out the $n$ particles as such. \item We are given the location of the $k$ selected particles. \end{enumerate} \begin{figure}[htb] \centering \includegraphics[scale=.45]{figures/game_all_modified.pdf} \caption{A round of the game: after sampling an arrangement (selected in blue) from $p$, the bot places the particles and reveals the location of those chosen by the player. In this case, $k=3, n=5, m=3$. The player chooses to see particles $2, 4,$ and $5$, that are placed in boxes $C, A$, and $C$, respectively.} \label{fig:game_all} \end{figure} The round then finishes and a new one begins. We refer to this game as a \emph{particle-box system}. After infinitely many rounds and all different choices of observable particles, by the law of large numbers we know the probability distributions of the bot's moves when arranging any $k$-subset of the $n$ particles, \ie the $k$-marginal distributions of $p$. We refer to this family of $\binom{n}{k}$ probability distributions as the \emph{$k$-restriction} of $p$ and denote it by $p_{|k}$.\\ We win the game if we are able to recover the original distribution $p$ from its $k$-restriction $p_{|k}$. But is this possible? And if it isn't, how far are we from determining $p$?\\ The work presented herein explores these questions, providing a negative answer to the first: it turns out that we generally cannot win the game. For the second, we note that reducing the number of observed particles from $n$ to $k$ gives rise, in general, to a \emph{degeneracy}: a positive-dimension space of probability distributions on the set of all $m^n$ arrangements resemble $p$ when $k$-restricted to $p_{|k}$. Studying this degeneracy amounts to determining the kernel of the $\left( \binom{n}{k} \cdot m^k \right) \times m^n$ restriction matrix $M$, defined as \begin{equation}\label{equation.restriction_matrix_Zm^n} M_{(\ii, \jj), f} = \begin{cases} 1 &\text{if } f(i_1, \dots, i_k) = (j_1, \dots, j_k),\\ 0 &\text{otherwise,} \end{cases} \end{equation} where we identify the set of boxes with the group $\Z_m = \{0, \dots, m-1\}$ and the possible arrangements of $n$ particles with the maps $f \colon \calN = \{1, \dots, n\} \to \Z_m$.\\ The kernel of $M$ conveniently coincides with the kernel of the $m^n \times m^n$ matrix $A = M^T M$, with entries \begin{equation*} A_{fg} = \binom{\ZZ(g - f)}{k}, \end{equation*} where $\ZZ(g-f)$ denotes the number of zeros of the map $g-f \colon \calN \to \Z_m$. To our advantage, this matrix can be interpreted as the adjacency matrix of a weighted Cayley graph on the group of maps $\calN \to \Z_m$, isomorphic to $(\Z_m)^n$. Letting $k$ vary, we obtain a family of weighted Cayley graphs.\\ Spectra of (the adjacency matrices of) weighted normal Cayley graphs are completely described in terms of the irreducible characters of their underlying groups (see Theorem \ref{theorem.spectra_weighted_normal_Cayley_graphs}). Using this technique, in Theorem \ref{theorem.eigenvalues_binomial_Cayley_graph_Zm^n} we provide an explicit description of the spectra of weighted Cayley graphs associated with this particle-box system. In particular, the dimension of the kernel of $A$, and equivalently of $M$, is (Corollary \ref{corollary.rank_binomial_Cayley_graphs_Zm^n}) \begin{equation*} \sum_{t < n-k} \binom{n}{t} \cdot (m-1)^{n-t}. \end{equation*} This provides a closed expression to the recursive formula given in \cite[Theorem 27]{daCosta2022}.\\ We pay particular attention to the case $n = m$, when the system takes the form of the so-called $k$-point motion on finite spaces introduced in \cite{daCosta2022}. In fact, the degeneracy of a particle-box system is linked to the notion of stochastic $n$-point D-bifurcations, whose complexity decreases as more particles $k$ are allowed to be observed. Originally, the study of the $k$-point motion on finite spaces arose from previous results on stochastic flows and particularly on Brownian flows of diffeomorphisms on $\R^d$ given by Baxendale in \cite{Baxendale1984}. In this continuous setting, the analogous of the restriction $p_{|2}$ is sufficient to fully characterise the analogous of $p$ (see \eg \cite[Chapter 4]{Kunita1990}, and in particular Theorems 4.2.4 and 4.2.5 therein).\\ The jump from $\R^d$ into a discrete state space $\{1, \dots, m\}$ conceptually brings Brownian flows of diffeomorphisms into bijective maps from the space of particles $\calN$ to the space of boxes $\calM$. In fact, since $n = m$, $\calN$ and $\calM$ coincide, and the set of admissible transformations corresponds to the symmetric group $S_m$. Specifically, $p$ is now a probability distribution on $S_m$. In this setting, the 2-point motion no longer uniquely characterises higher order point motions, suggesting a thorough study of the $k$-restriction from $p$ to $p_{|k}$ in the bijective framework. \begin{figure}[hbt] \centering \includegraphics[scale=.45]{figures/game_bij_modified.pdf} \caption{A round of the game in the bijective case: after sampling an arrangement (selected in blue) from $p$, the bot places the particles and reveals reveals the location of those chosen by the player. In this case, $k=3, n=m=5$. The player chooses to see particles $1, 3,$ and $4$, that are placed in boxes $D, E$, and $C$, respectively.} \label{fig:game_bij} \end{figure} In the bijective case, the restriction matrix $M$ takes the same form as in Equation \eqref{equation.restriction_matrix_Zm^n}. Its size can be reduced to $\left(\binom{m}{k} \cdot \frac{m!}{(m-k)!} \right) \times \binom{m}{k}$, and is indexed as $M_{(\ii, \jj), \sigma}$, where $\sigma \in S_m$. Again, the kernel of $M$ coincides with the kernel of the $m! \times m!$ matrix $A = M^T M$, with entries \begin{equation*} A_{\sigma\tau} = \binom{\FF(\tau\sigma^{-1})}{k}, \end{equation*} where $\FF(\tau\sigma^{-1})$ denotes the number of fixed points of the permutation $\tau\sigma^{-1} \in S_m$. Analogously, this matrix is the adjacency matrix of a weighted Cayley graph on $S_m$. In Theorem \ref{theorem.eigenvalues_binomial_Cayley_graph_Sm} we determine the spectrum of this graph. As a consequence, the dimension of the kernel of $A$, and equivalently of $M$, is (Corollary \ref{corollary.rank_binomial_Cayley_graphs_Sm}) \begin{equation*} \sum_{\substack{\mu \vdash m \\ \mu_1 < m-k}} \chi^\mu(\id)^2, \end{equation*} where $\chi^\mu(\id)$ is the degree of the irreducible character associated with $\mu$. The value $\chi^\mu(\id)$ coincides with the number of standard Young tableaux of shape $\mu$. By means of the RSK correspondence, we can rephrase this result as: the dimension of the kernel of $A$ is the number of permutations in $S_m$ with no increasing sub-sequences of length $m-k$ (Corollary \ref{corollary.increasing_sequences}). This also proves the formula for the degeneracy of the $k$-point motion conjectured in \cite[Section 3.3.2]{daCosta2022}.\\ The two families of Cayley graphs presented above are instances of graphs arising from a more general construction. In this work we refer to them as \emph{binomial Cayley graphs}, for which the weight function is obtained by taking the binomial coefficient of an original weight function and a natural number $k$.\\ {\bf Outline.} In Section \ref{section.weighted_normal_Cayley_graphs_and_binomial_Cayley_graphs}, we recall the definition of weighted normal Cayley graphs, state a result on their eigenvalues (Theorem \ref{theorem.spectra_weighted_normal_Cayley_graphs}), and introduce binomial Cayley graphs. In Section \ref{section.binomial_Cayley_graphs_on_Sm}, we study a family of binomial Cayley graphs on symmetric groups and describe their spectrum (Theorem \ref{theorem.eigenvalues_binomial_Cayley_graph_Sm}). We also obtain a link between the dimension of the null eigenvalue to increasing sub-sequences through the RSK correspondence (Corollary \ref{corollary.increasing_sequences}). Section \ref{section.binomial_Cayley_graphs_on_Zm^n} is structured analogously to Section \ref{section.binomial_Cayley_graphs_on_Sm}. We analyse a family of binomial Cayley graphs on powers of cyclic groups and determine their spectrum (Theorem \ref{theorem.eigenvalues_binomial_Cayley_graph_Zm^n}). In Section \ref{section.degeneracies}, we consider particle-box systems and describe their degeneracy (Theorem \ref{thm.degeneracy-k-hom}). As an application of our results on binomial Cayley graphs, we determine the degeneracy of particle-box systems for specific choices of admissible functions, related to powers of cyclic groups (Corollary \ref{cor.degeneracy_random_maps}) and symmetric groups (Corollary \ref{cor.degeneracy_random_bijections}). We conclude the paper with some final remarks in Section \ref{sec.final}. \section{Weighted normal Cayley graphs and binomial Cayley graphs}\label{section.weighted_normal_Cayley_graphs_and_binomial_Cayley_graphs} In this section we introduce weighted normal Cayley graphs and binomial Cayley graphs. We refer to \cite[Section 2]{Babai1979} and \cite[Section 3.7]{Godsil2001} for a general discussion on Cayley graphs.\\ Let $G$ be a finite group and $\omega \colon G \to \C$. The (directed) \emph{weighted Cayley graph} $\Gamma(G, \omega)$ has as set of vertices the elements of $G$ and, for $g, h \in G$, the edge joining $g$ to $h$ has complex weight $\omega(hg^{-1})$ (see Figure \ref{fig:weighted_cayley_graph_1}). Its adjacency matrix $\A(G, \omega)$ is a $|G| \times |G|$ matrix whose $(g, h)$ entry is $\omega(hg^{-1})$. Self-loops are admitted. \begin{figure}[htb] \centering \includegraphics[scale=0.38]{figures/weighted_cayley_graph_1.pdf} \caption{Example of weighted Cayley graph on the cyclic group $\Z_6$. The weight function takes values $\omega(\pm g) = g$ for $g = 0, 1, 2, 3$. The symmetry of $\omega$ makes the graph undirected.} \label{fig:weighted_cayley_graph_1} \end{figure} The group $G$ acts transitively on the set of nodes of $\Gamma(G, \omega)$ by right multiplication. Each of these node permutations is in fact a graph automorphism since the weight of the edge joining $g$ to $h$ only depends on $hg^{-1}$. It follows that every weighted Cayley graph is regular (that is, each node has the same weighted degree). In particular, the weighted degree $d(G, \omega)$ of each node is \begin{equation*} d(G, \omega) = \sum_{g \in G} \omega(g). \end{equation*} This paper makes essential use of weight functions. However, we remark that \emph{non-weighted} Cayley graphs can be recovered as particular weighted Cayley graphs. Non-weighted Cayley graphs are defined through a subset $S \subseteq G$. Usually one also assumes that $S$ is invariant under inversion ($S^{-1}=S)$ and that $\id \notin S$ (no self-loops). An edge connects $g$ to $sg$ for every $g \in G$, $s \in S$ (see Figure \ref{fig:simple_cayley_graphs}). This is equivalent to saying that $g$ is connected to $h$ if and only if $hg^{-1} \in S$. A non-weighted Cayley graph can therefore be described by the weight (characteristic) function \begin{equation*} \omega(g) = \begin{cases} 1 & \text{if } g \in S, \\ 0 & \text{if } g \notin S. \end{cases} \end{equation*} \begin{figure}[htb] \centering \includegraphics[scale=0.38]{figures/simple_cayley_graphs.pdf} \caption{Examples of undirected non-weighted Cayley graphs: the weight function evaluates $1$ on a subset $S \subseteq G$. In this case, $G$ is the cyclic group $\Z_{10}$. From left to right, $S=\{ \pm 2 \}$, $S=\{ \pm 2 , \pm 5 \}$, and $S=\{ \pm 3 \}$. The left graph is not connected, as $\{ \pm 2 \}$ is not a set of generator of $\Z_{10}$. The middle and right graphs are connected, as $\{ \pm 2 , \pm 5 \}$ and $\{ \pm 3 \}$ both generate $\Z_{10}$.} \label{fig:simple_cayley_graphs} \end{figure} Given a weighted Cayley graph $\Gamma(G, \omega)$ and a $k \in \N$, we define the \emph{binomial Cayley graph} $\Gamma_\Bin(G, \omega, k)$ as $\Gamma(G, \omega_k)$, where $\omega_k$ is defined through the (generalised) binomial coefficient \begin{equation*}\label{equation.omega_k} \omega_k(g) = \binom{\omega(g)}{k} = \frac{\omega(g) \cdot \left(\omega(g) - 1\right) \cdots \left( \omega(g) - k + 1 \right)}{k!}. \end{equation*} In particular, for $k=1$ we recover the original Cayley graph $\Gamma_\Bin(G, \omega, 1) = \Gamma(G, \omega)$. For $k=0$, $\Gamma_\Bin(G, \omega, 0)$ is the complete graph with self-loops (all edges have equal weight $1$). The graph becomes sparser as $k$ increases, up until no edges are left when $k$ exceeds the maximal value of $\omega$ (see Figure \ref{fig.weighted_cayley_graphs}). \begin{figure}[htb] \centering \includegraphics[scale=0.38]{figures/weighted_cayley_graphs.pdf} \caption{Examples of binomial Cayley graphs obtained from the weighted Cayley graph in Figure \ref{fig:weighted_cayley_graph_1}. Colour encircling nodes represents self-loops. On each edge, the change in colour from left to right follows the binomial coefficient.} \label{fig.weighted_cayley_graphs} \end{figure} Despite the generality of this construction, in this paper we assume that: \begin{enumerate} \item $\omega$ takes values in $\N = \{0, 1, \dots\}$, so that $\A(G, \omega)$ has non-negative integer entries. In particular, $\omega$ is real-valued, or equivalently invariant under complex conjugation. \item For all $g \in G$, $\omega(g^{-1}) = \omega(g)$, that is, $\omega$ is \emph{invariant under inversion}. This implies that $\A(G, \omega)$ is symmetric and that $\Gamma(G, \omega)$ is an undirected graph. \item For all $g, h \in G$, $\omega(h^{-1}gh) = \omega(g)$, that is, $\omega$ is a \emph{class function}, or equivalently $\omega$ is invariant under group conjugation. \end{enumerate} Under these conditions, we refer to $\Gamma(G, \omega)$ as a weighted \emph{normal} Cayley graph. For instance, the graph in Figure \ref{fig:weighted_cayley_graph_1} is normal. It is worth mentioning that hypothesis (3) implies that the action of $G$ by left multiplication on the nodes of $\Gamma(G, \omega)$ induces graph automorphisms as well.\\ Given a weighted normal Cayley graph $\Gamma(G, \omega)$ and a $k \in \N$, the binomial Cayley graph $\Gamma_\Bin(G, \omega, k)$ is itself a weighted normal Cayley graph. We underline that, by hypothesis (1), the generalised binomial $\binom{\omega(g)}{k}$ is in fact a standard binomial. In particular, $\binom{\omega(g)}{k} = 0$ if $\omega(g) < k$. We also denote by $\A_\Bin(G, \omega, k)$ the adjacency matrix of the binomial Cayley graph $\Gamma_\Bin(G, \omega, k)$. Similarly, we denote by $d_\Bin(G, \omega, k)$ the weighted degree of each of the nodes of $\Gamma_\Bin(G, \omega, k)$. \\ We state here an elegant theorem, fundamental to our discussion, describing the spectra of weighted normal Cayley graphs in terms of the irreducible characters of the group $G$. The theorem descends as a corollary from a more involved result, where the hypothesis of normality is dropped, and which appeared for the first time in \cite[Theorem 3.1]{Babai1979} (see also \cite[Theorem 3]{Diaconis1981}). For completeness, in Section \ref{sec.eigenvectors_binomial} we discuss eigenvectors of weighted normal Cayley graphs, for which we refer to \cite[Section 1]{Rockmore2002} and \cite[Section 4]{Roichman1999}. \\ We recall the standard inner product on the space $\mathscr{F}(G, \C)$ of $\C$-valued functions on $G$. Given $\alpha, \beta \colon G \to \C$, we define \begin{equation*}\label{equation.inner_product} \langle \alpha, \beta \rangle = \frac{1}{|G|} \sum_{g \in G} \alpha(g) \overline{\beta(g)}. \end{equation*} \begin{theorem}\label{theorem.spectra_weighted_normal_Cayley_graphs} Assume that $\Gamma(G, \omega)$ is a weighted normal Cayley graph. Then, for every irreducible character $\chi$ of $G$, the value \begin{equation*}\label{equation.weighted_normal_Cayley_eigenvalue} \lambda_\chi = \frac{1}{\chi(\id)} \sum_{g \in G} \omega(g) \chi(g) = \frac{|G|}{\chi(\id)} \langle \omega, \overline{\chi} \rangle \end{equation*} is an eigenvalue of $\A(G, \omega)$. Its contribute in multiplicity is $\chi(\id)^2$. \end{theorem} \begin{remark}\label{remark.multiplicity_eigenvalue} Different characters $\chi$ may induce the same eigenvalue $\lambda_\chi$. More explicitly, given a real number $\lambda$, the multiplicity of $\lambda$ as an eigenvalue of $\A(G, \omega)$ is $\sum_{\chi \colon \lambda_\chi = \lambda} \chi(\id)^2$. \end{remark} Having introduced the binomial construction of $\omega_k$, a natural question to investigate is whether there exists a formula that relates the spectrum of $\Gamma_\Bin(G, \omega, k)$ to that of $\Gamma(G, \omega)$. We present this in Section \ref{sec.ugly_formula_general_eigenvalues_binomial}, and already point out that this expression does not seem to be easily tractable in general. This supports the specialised analysis of two families of binomial Cayley graphs, which we expose in Sections \ref{section.binomial_Cayley_graphs_on_Sm} and \ref{section.binomial_Cayley_graphs_on_Zm^n}. \section{Binomial Cayley graphs on symmetric groups}\label{section.binomial_Cayley_graphs_on_Sm} Let $S_m$ be the symmetric group on $m$ elements $\{1, \dots, m\}$ and consider the weight function $\FF \colon S_m \to \N$, which gives the number of fixed points of a permutation (see Figure \ref{fig:sym_cayley_graph_1}). This induces, for every $k \in \N$, the weight function $\FF_k \colon S_m \to \N$, defined as \begin{equation*}\label{equation.omega_k_Sm} \FF_k(\sigma) = \binom{\FF(\sigma)}{k}. \end{equation*} As the weight function $\FF$ takes values in $\N$, is invariant under inversion and is a class function, we obtain a family of associated weighted normal binomial Cayley graphs $\Gamma_\Bin(S_m, \FF, k)$, for $k \in \N$ (see Figure \ref{fig:sym_cayley_graphs}). \begin{figure}[htb] \centering \includegraphics[scale=0.45]{figures/sym_cayley_graph_1_short_edges.pdf} \caption{The neighbourhood of the identity of the weighted Cayley graph on the symmetric group $S_5$, induced by the weight function $\FF$. Colour encircling nodes represents self-loops.} \label{fig:sym_cayley_graph_1} \end{figure} \begin{figure}[htb] \centering \includegraphics[scale=0.45]{figures/sym_cayley_graphs_short_edges.pdf} \caption{The neighbourhood of the identity of the binomial Cayley graphs on $S_5$, induced by the weight function $\FF$. Colour encircling nodes represents self-loops.} \label{fig:sym_cayley_graphs} \end{figure} \subsection{Young diagrams, characters of symmetric groups and Crop}\label{section.characters_Sm} In this section, we recall some facts on the characters of the symmetric group $S_m$ and define $\Crop(\mu, k)$ for a partition $\mu$ of $m$. For a discussion on Young diagrams and characters of symmetric groups, we refer the reader to \cite{Roichman1999}.\\ A \emph{partition} $\mu$ of $m$, denoted by $\mu \vdash m$, is an $\ell$-uple $(\mu_1, \dots, \mu_\ell)$ formed by positive integers satisfying $\mu_1 \ge \dots \ge \mu_\ell$ and $\mu_1 + \dots \mu_\ell = m$. Given a {partition} $\mu \vdash m$, we can consider its {associated} \emph{Young diagram}, namely \begin{equation*}\label{equation.Young_diagram} \YD(\mu) = \Set{(i, j) \in \Z \times \Z \ |\ 1 \le i \le \ell \text{ and } 1 \le j \le \mu_i}. \end{equation*} We can think of $\YD(\mu)$ as a shape made by $\ell$ left-justified rows of squares of length $\mu_1, \dots, \mu_\ell$, respectively. We refer to the partition $\mu = (\mu_1, \dots, \mu_\ell)$ as the \emph{shape} of the Young diagram.\\ The \emph{boundary} of a Young diagram is the set of squares $(i, j)$ for which $(i+1, j+1)$ does not belong to the Young diagram. A \emph{rim hook} $\tau$ is a connected part of the boundary of a Young diagram which can be removed to leave either a proper Young diagram, or the empty Young diagram (see Figure \ref{fig:young}). The \emph{length} $\len(\tau)$ of a rim hook is the number of squares included in the rim hook. The \emph{height} $\hgt(\tau)$ of a rim hook is one less of the number of rows involved in the rim hook (so that $0 \le \hgt(\tau) \le \ell - 1$ holds for $\mu \vdash m$, $\mu = (\mu_1, \dots, \mu_\ell)$). \begin{figure}[htb] \centering \includegraphics[scale=0.2]{figures/young.pdf} \caption{The Young diagram associated with the partition $\mu=(5, 4, 2)$ of $m=11$. From the left: the boundary of the diagram, three rim hooks (of length $5, 4,$ and $1$, and heights $1, 1,$ and $0$, respectively), and two examples of non-rim hooks.} \label{fig:young} \end{figure} Each partition $\mu$ induces a distinct irreducible character $\chi^\mu$. Moreover, this association is a bijection between the set of partitions of $m$ and the irreducible characters of $S_m$. The value of $\chi^\mu$ on a permutation $\sigma \in S_m$ can be computed using the recursive version of the Murnaghan-Nakayama rule \cite[Section 7.17]{Stanley1999}: \begin{theorem}\label{theorem.MNrule} Assume that $\sigma \in S_m$ is the disjoint product $\sigma = \gamma\pi$ of a cycle $\gamma$ permuting $d$ elements and a permutation $\pi$ fixing the same $d$ elements. Then, \begin{equation*}\label{equation.murnaghan-nakayama} \chi^\mu(\sigma) = \sum_{\substack{\tau \text{ rim hook of } \YD(\mu) \\ \text{ with } \len(\tau) = d}} (-1)^{\hgt(\tau)} \chi^{\mu \setminus \tau} (\pi). \end{equation*} Here $\mu \setminus \tau$ denotes the Young diagram obtained by removing $\tau$ from $\mu$. \end{theorem} \begin{definition} Given $\mu \vdash m$, and for an integer $k$ satisfying $0 \le k \le m$, we define $\Crop(\mu, k)$ to be the number of ways in which the Young diagram of $\mu$ can be reduced to a single-row Young diagram of length $m-k$ through the progressive removal of $k$ rim hooks of length $1$. \end{definition} Notice that the single-row Young diagram of length $m-k$ is the Young diagram of the trivial partition $(m-k)$ of $m-k$. \begin{example} If $m=5$ and $\mu = (2, 2, 1)$, then: \begin{enumerate}[label = \roman*)] \item $\Crop(\mu, k) = 0$ for $k=0, 1, 2$, \item $\Crop(\mu, k) = 2$ for $k=3$, \item $\Crop(\mu, k) = 5$ for $k = 4, 5$. \end{enumerate} \end{example} \begin{lemma}\label{lemma.crop_0} $\Crop(\mu, k) = 0$ if and only if all the rows of $\YD(\mu)$ have length lower than $m-k$, or equivalently the first row of $\YD(\mu)$ has length lower than $m-k$. Moreover, $\Crop(\mu, k) \le \Crop(\mu, m) = \chi^\mu(\id)$. \end{lemma} \begin{proof} For the first statement, we notice that if $\mu_1 \ge m-k$, there is at least one way to reduce $\YD(\mu)$ to a single-row Young diagram of length $m-k$ (for instance, by always removing the right-most square of the {lowest} row available). Conversely, a single-row Young diagram of length $m-k$ is not reachable if $\mu_1 < m-k$. For the second statement, $\Crop(\mu, k) \le \Crop(\mu, m)$ as every way of reducing $\mu$ to a single-row Young diagram of length $m-k$ extends uniquely to a different way of reducing $\mu$ to the empty Young diagram. Finally, $\Crop(\mu, m) = \chi^\mu(\id)$ follows directly from the iterative application of the Murnaghan-Nakayama rule (Theorem \ref{theorem.MNrule}). \end{proof} We also recall the notion of \emph{Young tableau} (see Figure \ref{fig:young_tableau}). A Young tableau is a filling of a Young diagram of shape $\mu \vdash m$ by the numbers $\{ 1, \dots, m \}$, each appearing exactly once. We say that a Young tableau is \emph{standard} if all rows and all columns present numbers in increasing order. \begin{figure}[htb] \centering \includegraphics[scale=0.3]{figures/young_tableau.pdf} \caption{Examples of Young tableaux for the partition $\mu=(5, 4, 2)$ of $m=11$. On the left, a non-standard Young tableau. In the centre and on the right, two standard Young tableaux.} \label{fig:young_tableau} \end{figure} A consequence of the Murnaghan-Nakayama rule (Theorem \ref{theorem.MNrule}) is the following well-known fact on the number of standard Young tableaux (see for example \cite[Fact 7.6, ii]{Macdonald1995}). \begin{proposition}\label{proposition.number_standard_young_tableaux} Let $\mu \vdash m$ and consider its associated character $\chi^\mu$. Then, the number of standard Young tableaux with shape $\mu$ is $\chi^\mu(\id)$. \end{proposition} \begin{remark}\label{remark.Crop_in_literature} $\Crop(\mu, k)$ coincides in fact with known quantities in the literature. It equals both: \begin{enumerate}[label = \roman*)] \item the number of standard Young tableaux of skew-shape $\mu/(m-k)$ \cite{Sagan1990}, {and} \item the Kostka number $K_{\mu, (m-k,1, \dots, 1)}$, where $1$ appears $k$ times \cite[Chapter I, Section 6]{Macdonald1995}. \end{enumerate} \end{remark} \subsection{Spectra of binomial Cayley graphs on symmetric groups}\label{section.spectra_binomial_cayley_graphs_Sm} In this section we provide a description of the spectrum of the binomial Cayley graph $\Gamma_\Bin(S_m, \FF, k)$. \begin{lemma}\label{lemma.change_the_binomial} For every character $\chi$ of $S_m$ and every $f$ such that $k \le f \le m$, \begin{equation*}\label{equation.swap_binomials_Sm} \sum_{\substack{\sigma \in S_m \\ \sigma \textrm{ fixes exactly } f \\ \textrm{ elements in } \{1, \dots, m\} }} \chi(\sigma) = \sum_{\substack{\sigma \in S_{m - k} \\ \sigma \textrm{ fixes exactly } f-k \\ \textrm{ elements in } \{1, \dots, m-k\} }} \chi(\sigma) \cdot \ \xof{\scb{1.2}{\(\binom{m}{k}\)}}{\scb{1.2}{\(\binom{f}{k}\)}} . \end{equation*} Here, $S_{m-k}$ is seen as the subgroup of $S_m$ fixing the $k$ points $\{m-k+1, \dots, m\}$. \end{lemma} \begin{proof} The character $\chi$ is conjugation-invariant. Therefore, for a {given} type of permutation fixing $f$ points in $\{1, \dots, m\}$, the proof reduces to counting how many permutations of {that} type exist in $S_m$, and how many of these belong to $S_{m-k}$. Consider the type \begin{equation*}\label{equation.type_of_sigma} (d_{11}, \dots, d_{1t_1},\dots, d_{r1}, \dots, d_{r t_r}, \underbrace{1, \dots, 1}_{f \textrm{ times}}). \end{equation*} Here, all the $d_{ij}$ are strictly greater than $1$. Moreover, $d_{ij} = d_i$ for all $j=1, \dots , t_i$, for all $i=1, \dots, r$, and different values of $i$ index different values of $d_i$. The sum of the values $d_{ij}$ is $m-f$ and $1$ is repeated $f$ times. The number of permutations of this type in $S_m$ is \begin{equation*} \binom{m}{d_{11}, \dots, d_{rt_r}, \underbrace{1, \dots, 1}_{f \textrm{ times}}} \cdot \frac{(d_{11} - 1)! \cdots (d_{rt_r} - 1)!}{t_1! \cdots t_r! \cdot f!}. \end{equation*} Similarly, the number of permutations of this type belonging to $S_{m-k}$ is \begin{equation*} \binom{m - k}{d_{11}, \dots, d_{rt_r}, \underbrace{1, \dots, 1}_{f-k \textrm{ times}}} \cdot \frac{(d_{11} - 1)! \cdots (d_{rt_r} - 1)!}{t_1! \cdots t_r! \cdot (f - k)!}. \end{equation*} The ratio of these numbers is \begin{equation*} \frac{m! \cdot (f-k)!}{f! \cdot (m-k)!} = \xof{\scb{1.2}{\(\binom{m}{k}\)}}{\scb{1.2}{\(\binom{f}{k}\)}} . \end{equation*} As this value is independent of the considered permutation type (as soon as it fixes exactly $f$ points in $\{1, \dots, m\}$), the claim follows. \end{proof} \begin{lemma}\label{lemma.sum_characters_Sm-k_crop} Let $\mu \vdash m$ and $k$ such that $0 \le k \le m$. Then, \begin{equation*} \sum_{\sigma \in S_{m-k}} \chi^\mu(\sigma) = (m-k)! \cdot \Crop(\mu, k). \end{equation*} Here, $S_{m-k}$ is seen as the subgroup of $S_m$ fixing the $k$ points $\{m-k+1, \dots, m\}$. \end{lemma} \begin{proof} We compute $\chi^\mu(\sigma)$ by iterative application of Theorem \ref{theorem.MNrule}. To do so, we apply the Murnagham-Nakayama rule $k$ times, removing one single square from $\YD(\mu)$ at each step. Assume we end up with a partition $\nu$ of $m-k$. If this partition is not the trivial partition $(m-k)$, corresponding to a single-row Young diagram of length $m-k$, then $\sum_{\sigma \in S_{m-k}} \chi^{\nu}(\sigma) = 0$. This follows from the general fact that $\sum_{g \in G} \chi(g) = 0$ for every finite group $G$ and every non-trivial irreducible character $\chi$ of $G$. Therefore, we only need to consider the successive removals of $k$ squares that transform $\YD(\mu)$ into a single-row Young diagram of length $m-k$. By definition, there are $\Crop(\mu, k)$ ways to perform this operation. Finally, if $\nu$ is the trivial partition $(m-k)$ of $m-k$, then $\sum_{\sigma \in S_{m-k}} \chi^{\nu}(\sigma) = (m-k)!$, which proves the claim. \end{proof} \begin{theorem}\label{theorem.eigenvalues_binomial_Cayley_graph_Sm} Let $\mu \vdash m$ and $\chi^\mu$ the associated irreducible character of $S_m$. Then: \begin{enumerate} \item The value \begin{equation*}\label{equation.binomial_Cayley_Sm_graph_eigenvalue} \lambda_\mu = \frac{\binom{m}{k} \cdot (m-k)! \cdot \Crop(\mu, k)}{\chi^\mu(\id)} = \xof[0.2ex]{\scb{.9}{\(\dfrac{\Crop(\mu, k)}{k!}\)\hspace{1pt}}}{\scb{.9}{\hspace{0.5pt}\(\dfrac{\Crop(\mu, m)}{m!}\)}} \end{equation*} is an eigenvalue of $\A_\Bin(S_m, \FF, k)$. \item Its contribute in multiplicity is $\chi^\mu(\id)^2$. \item $\lambda_\mu$ is an integer number. \item $\lambda_\mu$ satisfies \begin{equation}\label{equation.bound_lambda_mu_Sm} 0 \le \lambda_\mu \le \binom{m}{k} \cdot (m-k)! \end{equation} \end{enumerate} \end{theorem} \begin{remark}\label{remark.inequalities_saturated_Sm} The latter inequality in Equation \eqref{equation.bound_lambda_mu_Sm} is always saturated. {To see} this, choose the trivial partition $\mu = (m)$, for which $\Crop(\mu, k) = 1 = \chi^\mu(\id)$. On the other hand, the former inequality in Equation \eqref{equation.bound_lambda_mu_Sm} is saturated if and only if $k < m - 1$. To see this, choose the partition $\mu = (1, \dots, 1)$, for which $\Crop(\mu, k) = 0$ unless $k = m-1$ or $k=m$, and conversely $\Crop(\mu, m-1) = \Crop(\mu, m) > 0$ for any partition $\mu$. \end{remark} \begin{proof} By Theorem \ref{theorem.spectra_weighted_normal_Cayley_graphs}, Lemma \ref{lemma.change_the_binomial}, and Lemma \ref{lemma.sum_characters_Sm-k_crop}, we know that the eigenvalue associated with $\mu$ is \begin{equation*} \begin{split} \lambda_\mu &= \frac{1}{\chi^\mu(\id)} \sum_{\sigma \in S_m} \binom{\FF(\sigma)}{k} \cdot \chi^\mu(\sigma) \\ &= \frac{1}{\chi^\mu(\id)} \sum_{f=k}^m \sum_{\substack{\sigma \in S_m \\ \sigma \textrm{ fixes exactly } f \\ \textrm{ elements in } \{1, \dots, m\} }} \binom{f}{k} \cdot \chi^\mu(\sigma) \\ &= \frac{1}{\chi^\mu(\id)} \sum_{f=k}^m \sum_{\substack{\sigma \in S_{m-k} \\ \sigma \textrm{ fixes exactly } f-k \\ \textrm{ elements in } \{1, \dots, m-k\} }} \binom{m}{k} \cdot \chi^\mu(\sigma) \\ &= \frac{\binom{m}{k}}{\chi^\mu(\id)} \sum_{\sigma \in S_{m-k}} \chi^\mu(\sigma) \\ &= \frac{\binom{m}{k} \cdot (m-k)! \cdot \Crop(\mu, k)}{\chi^\mu(\id)}. \end{split} \end{equation*} This proves the first equality in (1), while the second equality follows from Lemma \ref{lemma.crop_0}. (2) follows from Theorem \ref{theorem.spectra_weighted_normal_Cayley_graphs}. For (3), it follows from (1) that $\lambda_\mu \in \Q$. Moreover, as $\A_\Bin(S_m, \FF, k)$ has integer entries, $\lambda_\mu$ is an algebraic integer and therefore it belongs to $\Z$. Finally, we prove (4). From (1), it follows that $\lambda_\mu \ge 0$. From lemma \ref{lemma.crop_0}, $\Crop(\mu, k) \le \chi^\mu(\id)$, which implies the other side of the inequality. \end{proof} \begin{remark}\label{remark.laplacian_Sm} An alternative way to prove that $\lambda_\mu \le \binom{m}{k} \cdot (m-k)!$ is through the Laplacian of $\Gamma_\Bin(S_m, \FF, k)$, that is, the matrix \begin{equation*} \LL_\Bin(S_m, \FF, k) = d_\Bin(S_m, \FF, k) \cdot \II - \A_\Bin(S_m, \FF, k). \end{equation*} As we are assuming that $\omega$ takes non-negative values, $\LL_\Bin(S_m, \FF, k)$ is positive semi-definite and therefore every eigenvalue $\lambda_\mu$ of $\A_\Bin(S_m, \FF, k)$ satisfies $\lambda_\mu \le d_\Bin(S_m, \FF, k)$. On the other hand, following the same argument of Lemma \ref{lemma.change_the_binomial}, \begin{equation*} \begin{split} d_\Bin(S_m, \FF, k) &= \sum_{\sigma \in S_m} \binom{\FF(\sigma)}{k} \\ &= \sum_{f=k}^m \binom{f}{k} \cdot \big| \{\sigma \in S_m \text{ fixing exactly $f$ elements in $S_m$}\} \big| \\ &= \sum_{f=k}^m \binom{m}{k} \cdot \big| \{\sigma \in S_{m-k} \text{ fixing exactly $f-k$ elements in $S_{m-k}$}\} \big| \\ &= \binom{m}{k} \cdot (m-k)! \end{split} \end{equation*} which proves the desired inequality. \end{remark} \begin{corollary}\label{corollary.rank_binomial_Cayley_graphs_Sm} The kernel of $\A_\Bin(S_m, \FF, k)$ has dimension \begin{equation*}\label{equation.dimension_kernel_Sm} \sum_{\substack{\mu \vdash m \\ \mu_1 < m-k}} \chi^\mu(\id)^2. \end{equation*} Equivalently, the rank of $\A_\Bin(S_m, \FF, k)$ is \begin{equation*}\label{equation.rank_Sm} \sum_{\substack{\mu \vdash m \\ \mu_1 \ge m-k}} \chi^\mu(\id)^2. \end{equation*} \end{corollary} \begin{proof} The proof directly follows from Theorem \ref{theorem.eigenvalues_binomial_Cayley_graph_Sm} and Lemma \ref{lemma.crop_0}. \end{proof} We now link Corollary \ref{corollary.rank_binomial_Cayley_graphs_Sm} with combinatorial quantities related to increasing sub-sequences and the celebrated RSK correspondence \cite{Robinson1938,Schensted1961,Knuth1970} (although, technically, we are only using the RS version of the RSK correspondence). The RSK correspondence provides a bijection between permutations $\sigma \in S_m$ and pairs $(P, Q)$ of standard Young tableaux of the same shape on $m$. Given a permutation $\sigma \in S_m$, we say that $\sigma$ admits a $k$-\emph{increasing sub-sequence} if there exist $k$ indices $i_1 < \dots < i_k$ in $\{1, \dots, m\}$ such that $\sigma(i_1) < \dots < \sigma(i_k)$. We denote by $\is(\sigma)$ the length of the longest increasing sub-sequence in $\sigma$. The following result (see \cite[Theorem 3]{Schensted1961}) establishes a relation between the longest increasing sub-sequence in $\sigma$ and its associated standard Young tableaux: \begin{theorem}\label{theorem.RSK_is} Consider $\sigma \in S_m$ and let $(P, Q)$ be the standard Young tableaux associated with $\sigma$ via the RSK correspondence. Denote by $\mu = (\mu_1, \dots, \mu_\ell)$ the shape of $P$ and $Q$. Then $\is(\sigma) = \mu_1$. \end{theorem} Considering all the possible pairs of standard Young tableaux $(P, Q)$ of the same shape, it follows from Theorem \ref{theorem.RSK_is} and Proposition \ref{proposition.number_standard_young_tableaux} that: \begin{corollary}\label{corollary.result_cited_on_increasing_sequences} For every $t$ {such that} $0 \le t \le m$, \begin{equation*} \big| \Set{ \sigma \in S_m | \is(\sigma) = t } \big| = \sum_{\substack{\mu \vdash m \\ \mu_1 = t}} \chi^\mu(\id)^2. \end{equation*} \end{corollary} Finally, from Corollary \ref{corollary.rank_binomial_Cayley_graphs_Sm} and Corollary \ref{corollary.result_cited_on_increasing_sequences}: \begin{corollary}\label{corollary.increasing_sequences} The dimension of the kernel of $\A_\Bin(S_m, \FF, k)$ coincides with the number of permutations in $S_m$ with no increasing sub-sequences of length $m-k$. Equivalently, the rank of the matrix $\A_\Bin(S_m, \FF, k)$ coincides with the number of permutations in $S_m$ admitting an $(m-k)$-increasing sub-sequence. \end{corollary} \subsection{Binomial weight functions of symmetric groups in terms of representations}\label{section.binomial_weight_function_Sm_representation} In this section, we express the weight function $\FF_k(\sigma) = \binom{\FF(\sigma)}{k}$ in terms of a specific representation of $S_m$.\\ Let $V$ be the vector space over $\C$ with basis $\{e_1, \dots, e_m\}$. $S_m$ acts on $V$ in a natural way: $\sigma \cdot e_i = e_{\sigma(i)}$. A basis for its $k$-th tensor power $V^{\otimes k}$ is $\{e_{i_1} \otimes \cdots \otimes e_{i_k}\}$, for all possible choices of indices $1 \le i_1, \dots, i_k \le m$. The action of $S_m$ extends to $V^{\otimes k}$ by acting on all indices: $\sigma \cdot e_{i_1} \otimes \cdots \otimes e_{i_k} = e_{\sigma(i_1)} \otimes \cdots \otimes e_{\sigma(i_k)}$. Let $W$ be the subspace of $V^{\otimes k}$ generated by the basis elements corresponding to choices of $i_1, \dots, i_k$ all distinct. Let us denote by $\BB$ this basis of $W$. The subspace $W$ has dimension $\binom{m}{k} \cdot k!$, and is in fact an $S_m$-sub-module of $V^{\otimes k}$.\\ Let $\chi_k$ be the character associated with this representation. Since $\sigma \in S_m$ permutes the elements of $\BB$, $\chi_k(\sigma)$ coincides with the number of elements of $\BB$ that are fixed by $\sigma$, that is, \begin{equation*} \chi_k(\sigma) = \binom{\FF(\sigma)}{k} \cdot k! = \FF_k(\sigma) \cdot k! \end{equation*} As this holds for any $\sigma \in S_m$, \begin{equation*} \FF_k = \frac{1}{k!} \cdot \chi_k. \end{equation*} From this description, we can deduce in an alternative way that every eigenvalue $\lambda_\mu$ of $\A_\Bin(S_m, \FF, k)$ is non-negative. Indeed, from Theorem \ref{theorem.spectra_weighted_normal_Cayley_graphs}, \begin{equation*} \lambda_\mu = \frac{m!}{\chi^\mu(\id)} \langle \FF_k, \overline{\chi^\mu} \rangle = \frac{m!}{\chi^\mu(\id) \cdot k!} \langle \chi_k, \overline{\chi^\mu} \rangle \ge 0, \end{equation*} as the inner product of two characters is always non-negative. Furthermore, with this interpretation, we can also deduce that $\lambda_\mu$ is an integer, independently of Theorem \ref{theorem.eigenvalues_binomial_Cayley_graph_Sm}. Indeed, $\lambda_\mu \in \Q$ as the inner product of two characters is always an integer number, and the rest follows as before. \section{Binomial Cayley graphs on powers of cyclic groups}\label{section.binomial_Cayley_graphs_on_Zm^n} Let $\Z_m$ be the cyclic group of $m$ elements $\{0, \dots, m-1\}$. For a positive integer $n$, we consider its $n$-th power $(\Z_m)^n$ and the weight function $\ZZ \colon (\Z_m)^n \to \N$, {which gives} number of zero coordinates of an $n$-dimensional vector (see Figure \ref{fig:cyclic_cayley_graph_1}). This induces, for every $k \in \N$, the weight function {$\ZZ_k \colon (\Z_m)^n \to \N$ defined as} \begin{equation*}\label{eq:cyclic_group_weight} {\ZZ_k(\x) = \binom{\ZZ(\x)}{k}.} \end{equation*} Clearly, $\ZZ(-\x) = \ZZ(\x)$ and, as $(\Z_m)^n$ is abelian, $\ZZ$ is a class function. Therefore, we obtain a family of associated weighted normal binomial Cayley graphs $\Gamma_\Bin((\Z_m)^n, \ZZ, k)$ (see Figure \ref{fig:cyclic_cayley_graphs}). \begin{figure}[htb] \centering \includegraphics[scale=0.45]{figures/cyclic_cayley_graph_1.pdf} \caption{The weighted Cayley graph on the hypercube group $(\Z_2)^3$, induced by the weight function $\ZZ$. Colour encircling nodes represents self-loops.} \label{fig:cyclic_cayley_graph_1} \end{figure} \begin{figure}[htb] \centering \includegraphics[scale=0.45]{figures/cyclic_cayley_graphs.pdf} \caption{The binomial Cayley graphs on $(\Z_2)^3$, induced by the weight function $\ZZ$. Colour encircling nodes represents self-loops.} \label{fig:cyclic_cayley_graphs} \end{figure} \begin{remark} The discussion carried out in this chapter does not strictly require the group $G$ to be a power of a cyclic group. All consequent results can be extended to groups $G = G_1 \times \dots \times G_n$, where the factors $G_i$ are groups of the same order $m$. For clarity of notation and exposition, we set $G=(\Z_m)^n$. \end{remark} \subsection{Characters of powers of cyclic groups}\label{section.characters_Zm^n} {Given} an abelian group $G$, its \emph{dual group} $G^\dag = \Hom(G, \C^*)$ consists of the irreducible characters of $G$. {Let us} fix a primitive $m$-th root of unity $\zeta \in \C$. For the cyclic group $\Z_m$, this choice induces an isomorphism of groups between $\Z_m$ and its dual group $(\Z_m)^\dag = \Hom(\Z_m, \C^*)$, mapping $y \in \Z_m$ to the irreducible character $\chi^y$, defined for $x \in \Z_m$ as \begin{equation*}\label{equation.irr_chars_Zm} \chi^y(x) = \zeta^{y \cdot x}. \end{equation*} \begin{lemma}\label{lemma.sum_chi_only_one_Zm^n} Let $y \in \Z_m$ and {denote by} $\chi^y$ its associated character. Then, \begin{equation*} \sum_{x \in \Z_m \setminus \{0\}} \chi^y(x) = \begin{cases} m-1 & \text{if $y=0$,} \\ -1 & \text{if $y\neq0$.} \end{cases} \end{equation*} \end{lemma} \begin{proof} This follows from properties of roots of unity or from the theory of irreducible characters. \end{proof} As irreducible characters of product of groups are products of irreducible characters of their factors, the isomorphism above extends to an isomorphism between $(\Z_m)^n$ and $((\Z_m)^n)^\dag \simeq ((\Z_m)^\dag)^n$, sending $\y \in (\Z_m)^n$ to the irreducible character $\chi^\y$, defined for $\x \in (\Z_m)^n$ as \begin{equation*}\label{equation.irr_chars_Zm^n} \chi^\y(\x) = \prod_{i=1}^{n} \zeta^{y_i \cdot x_i} = \zeta^{\sum_{i=1}^n y_i \cdot x_i} = \zeta^{\y \cdot \x}. \end{equation*} \subsection{Spectra of binomial Cayley graphs on powers of cyclic groups}\label{section.spectra_binomial_cayley_graphs_Zm^n} In this section, we provide a description of the spectrum of the binomial Cayley graph $\Gamma_\Bin((\Z_m)^n, \ZZ, k)$. \begin{lemma}\label{lemma.generating_functions} Let $M, N, k$ be non-negative integers such that $M+k \ge N$. Then, \begin{equation}\label{equation.binomial_generating_equation} \sum_{p=0}^M (-1)^p \cdot \binom{N}{p} \cdot \binom{k + M - p}{M-p} = \binom{k - N + M}{M}. \end{equation} \end{lemma} \begin{proof} This proof relies on generating functions. By defining \begin{equation*} a_p = (-1)^p \cdot \binom{N}{p}, \quad b_p = \binom{k + p}{p}, \end{equation*} we see that the left-hand side of Equation \eqref{equation.binomial_generating_equation} is the Cauchy product of the sequences $a_p$ and $b_p$. In other words, if we set \begin{equation*} A(X) = \sum_{p\ge0} a_p X^p, \quad B(X) = \sum_{p\ge0} b_p X^p, \end{equation*} then the left-hand side is the $M$-th coefficient of $C(X) = A(X) \cdot B(X)$. The functions $A(X)$ and $B(X)$ are well-known expansions of \begin{equation*} A(X) = (1-X)^N, \quad B(X) = (1-X)^{-(k+1)}. \end{equation*} Thus, $C(X) = (1-X)^{N-k-1}$. We distinguish two cases: \begin{enumerate}[label = \roman*)] \item Assume first that $N-k-1 \ge 0$. Then, the $M$-th term in the expansion of $C(X)$ is $(-1)^{M} \cdot \binom{N-k-1}{M} = 0$, as $N-k-1 < N-k \le M$ by hypothesis. On the other hand, $M + k - N < M + k - N + 1 \le M$, so that the right-hand side of Equation \eqref{equation.binomial_generating_equation} is $0$ as well. \item Suppose instead that $N-k-1 < 0$. Then, the $M$-th term of the expansion of $C(X) = (1-x)^{-(k-N+1)}$ is $\binom{k - N + M}{M}$, and the proof is concluded. \qedhere \end{enumerate} \end{proof} \begin{lemma}\label{lemma.chi_y_sum_x_m-1_-1} Let $\y \in (\Z_m)^n$ and consider its associated irreducible character $\chi^\y$ of $(\Z_m)^n$. Also, let $t=\ZZ(\y)$ and $z$ such that $0 \le z \le n$. Then, \begin{equation*} \sum_{\substack{\x \in (\Z_m)^n \\ \ZZ(\x) = z}} \chi^\y(\x) = \sum_{\ell=0}^{n-z} (m-1)^\ell \cdot (-1)^{n-z-\ell} \cdot \binom{t}{\ell} \cdot \binom{n-t}{n-z-\ell}. \end{equation*} \end{lemma} \begin{proof} We see the character $\chi^\y$ as the product of characters $\chi^{y_i}$ on $\Z_m$, for $i=1, \dots, n$. Then, by Lemma \ref{lemma.sum_chi_only_one_Zm^n}, \begin{align*} \sum_{\substack{\x \in (\Z_m)^n \\ \ZZ(\x) = z}} \chi^\y(\x) &= \sum_{\substack{Z \subseteq \{1, \dots, n\} \\ |Z| = z} }\sum_{\substack{\x \in (\Z_m)^n \ \text{s.t.} \\ \text{the set of zeros of $\x$ is $Z$}}} \chi^\y(\x) \\ &= \sum_{\ell=0}^{n-z} \sum_{\substack{Z \subseteq \{1, \dots, n\}, \ |Z| = z \ \text{s.t.} \\ \text{the complement of $Z$ contains} \\ \text{$\ell$ elements of the $t$ zeros of $\y$}}} \quad \sum_{\substack{\x \in (\Z_m)^n \ \text{s.t.} \\ \text{the set of zeros of $\x$ is $Z$}}} \chi^\y(\x) \\ &=\sum_{\ell=0}^{n-z} \sum_{\substack{Z \subseteq \{1, \dots, n\}, \ |Z| = z \ \text{s.t.} \\ \text{the complement of $Z$ contains} \\ \text{$\ell$ elements of the $t$ zeros of $\y$}}} (m-1)^\ell \cdot (-1)^{n-z-\ell} \\ &=\sum_{\ell=0}^{n-z} (m-1)^\ell \cdot (-1)^{n-z-\ell} \cdot \text{ \footnotesize $\left| \ \left\{ \begin{array}{c} Z \subseteq \{1, \dots, n\}, \ |Z| = z \ \text{s.t.} \\ \text{the complement of $Z$ contains} \\ \text{$\ell$ elements of the $t$ zeros of $\y$} \end{array} \right\} \ \right|$}. \end{align*} Now, a choice for $Z$ as described above is equivalent to a choice of its complement. This is a set of $n-z$ elements: $\ell$ of these belong to the subset $\ZZ(\y)$, of cardinality $t$; the remaining $n - z - \ell$ belong to the complement of $\ZZ(\y)$, of cardinality $n - t$. The number of such choices is $\binom{t}{\ell} \cdot \binom{n-t}{n-z-\ell}$, and the claim is proven. \end{proof} \begin{theorem}\label{theorem.eigenvalues_binomial_Cayley_graph_Zm^n} Let $\y$ be an element of $(\Z_m)^n$ and {denote by} $\chi^\y$ its associated irreducible character of $(\Z_m)^n$. Then: \begin{enumerate} \item The value \begin{equation*}\label{equation.binomial_Cayley_Zm^n_graph_eigenvalue} \lambda_\y = m^{n-k} \cdot \binom{\ZZ(\y)}{n-k} \end{equation*} is an eigenvalue of $\A_\Bin((\Z_m)^n, \ZZ, k)$. \item Its contribute in multiplicity is $1$. \item $\lambda_\y$ is an integer number. \item $\lambda_\y$ satisfies \begin{equation}\label{equation.bound_lambda_mu_Zm^n} 0 \le \lambda_\y \le m^{n-k} \cdot \binom{n}{k}. \end{equation} \end{enumerate} \end{theorem} \begin{remark}\label{remark.inequalities_saturated_Zm^n} The latter inequality in Equation \eqref{equation.bound_lambda_mu_Zm^n} is always saturated. {To see} this, choose $\y = \mathbf{0}$. On the other hand, the former inequality in Equation \eqref{equation.bound_lambda_mu_Zm^n} is saturated if and only if $k < n$. To see this, choose $\y = \textbf{1}$, for which $\binom{\ZZ(\y)}{n-k} = 0$ if $k < n$, and conversely $\lambda_\y = 1$ for all $\y$ if $k=n$. \end{remark} \begin{proof} The theorem is stated in the same form as of Theorem \ref{theorem.eigenvalues_binomial_Cayley_graph_Sm}, although (3) and (4) trivially follow from (1) in this case. Again, (2) follows from Theorem \ref{theorem.spectra_weighted_normal_Cayley_graphs}, and the fact that all irreducible characters $\chi$ of abelian groups have degree $\chi(\id)$ equal to $1$. It remains to prove (1). Following Theorem \ref{theorem.spectra_weighted_normal_Cayley_graphs} and Lemma \ref{lemma.chi_y_sum_x_m-1_-1}, writing $t=\ZZ(\y)$, we know the eigenvalue associated with $\y$ is \begin{equation*} \begin{split} \lambda_\y &= \sum_{\x \in (\Z_m)^n} \binom{\ZZ(\x)}{k} \cdot \chi^\y(\x) \\ &= \sum_{z=k}^n \ \binom{z}{k} \cdot \sum_{\substack{\x \in (\Z_m)^n \\ \ZZ(\x) = z}} \chi^\y(\x) \\ &= \sum_{z=k}^n \binom{z}{k} \cdot \sum_{\ell=0}^{n-z} (m-1)^\ell \cdot (-1)^{n-z-\ell} \cdot \binom{t}{\ell} \cdot \binom{n-t}{n-z-\ell} \\ &= \sum_{\ell=0}^{n-k} (m-1)^\ell \cdot \binom{t}{\ell} \cdot \sum_{z=k}^{n-\ell} (-1)^{n-z-\ell} \cdot \binom{n-t}{n-z-\ell} \cdot \binom{z}{k}. \end{split} \end{equation*} For a fixed $\ell$, we set $p=n-z-\ell$, $M=n-\ell-k$, $N=n-t$, and $k=k$. If $M+k \ge N$, that is, $\ell \le t$, we can apply Lemma \ref{lemma.generating_functions} and rewrite the inner sum as $\binom{t-\ell}{n-\ell-k}$. If instead $M+k < N$, that is, $t < \ell$, the inner sum is multiplied by $\binom{t}{\ell}=0$, so that we can rewrite is as $\binom{t-\ell}{n-\ell-k}$ also in this case. We can then continue the chain of equalities as \begin{equation*} \begin{split} \lambda_\y &= \sum_{\ell=0}^{n-k} (m-1)^\ell \cdot \binom{t}{\ell} \cdot \binom{t-\ell}{n-\ell-k}\\ &= \sum_{\ell=0}^{n-k} (m-1)^\ell \cdot \binom{n-k}{\ell} \cdot \binom{t}{n-k} \\ &= m^{n-k} \cdot \binom{t}{n-k}. \end{split} \end{equation*} As $t=\ZZ(\y)$, the thesis follows. \end{proof} \begin{remark} {Any time} a binomial with negative entries appears in the argument of the above proof, it is effectively multiplied by a factor $0$. We thus avoid specifying the definition of binomial coefficients with negative entries. \end{remark} \begin{remark}\label{remark.laplacian_Zm^n} As one may expect, {we} can prove the inequality $\lambda_\y \le m^{n-k} \cdot \binom{n}{k}$, also in this context, without relying on the explicit form of the eigenvalues $\lambda_\y$. As done in Remark \ref{remark.laplacian_Sm}, we consider the Laplacian matrix \begin{equation*} \LL_\Bin((\Z_m)^n, \ZZ, k) = d_\Bin((\Z_m)^n, \ZZ, k) \cdot \II - \A_\Bin((\Z_m)^n, \ZZ, k). \end{equation*} An eigenvalue $\lambda_\y$ of $\A_\Bin((\Z_m)^n, \ZZ, k)$ satisfies $\lambda_\y \le d_\Bin((\Z_m)^n, \ZZ, k)$, as the Laplacian matrix is positive semi-definite (since we assume that $\omega$ takes non-negative values). Moreover, setting $r=n-z$, \begin{equation*} \begin{split} d_\Bin((\Z_m)^n, \ZZ, k) &= \sum_{\x \in (\Z_m)^n} \binom{\ZZ(\x)}{k} \\ &= \sum_{z=k}^n \binom{z}{k} \cdot \big| \{ \x \in (\Z_m)^n \text{ such that } \ZZ(\x) = z \} \big| \\ &= \sum_{z=k}^n \binom{z}{k} \cdot \binom{n}{z} \cdot (m-1)^{n-z} \\ &= \sum_{r=0}^{n-k} \binom{n-r}{k} \cdot \binom{n}{r} \cdot (m-1)^r \\ &= \sum_{r=0}^{n-k} \binom{n}{k} \cdot \binom{n-k}{r} \cdot (m-1)^r \\ &= m^{n-k} \cdot \binom{n}{k}. \end{split} \end{equation*} \end{remark} \begin{corollary}\label{corollary.rank_binomial_Cayley_graphs_Zm^n} The spectrum of $\A_\Bin((\Z_m)^n, \ZZ, k)$ is formed by: \begin{enumerate}[label = \roman*)] \item The eigenvalue $0$, with multiplicity $\sum_{t