\documentclass[ALCO]{cedram} \usepackage{tikz} \usetikzlibrary{decorations.markings} \usetikzlibrary{cd} \usetikzlibrary{patterns} \usetikzlibrary{shapes} \tikzset{anchorbase/.style={baseline={([yshift=-0.5ex]current bounding box.center)}}} \tikzset{wipe/.style={white,line width=4pt}} \usepackage{ctable} \usepackage{stackengine} \usepackage{hyperref} \usepackage{latexsym,amsfonts,amssymb,amsmath,amscd,graphics,epic} \usepackage[all]{xy} \usepackage{amssymb,amsbsy,amsthm,amsxtra} \usepackage{amsthm} \usepackage{mathrsfs} \usepackage{url} \usepackage{bbm} \usepackage{wasysym} \usepackage{enumitem} \usepackage{framed} \newcommand\xrowht[2][0]{\addstackgap[0.5\dimexpr#2\relax]{\vphantom{#1}}} \newcommand{\Tr}{\operatorname{Tr}} \newcommand{\Gcd}{\mathbf{gcd}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\Rep}{\operatorname{Rep}} \newcommand{\Iso}{\operatorname{Iso}} \newcommand{\diag}{\operatorname{diag}} \newcommand{\triv}{{\mathbbm 1}} \newcommand{\stab}{\operatorname{Stab}} \newcommand{\Ind}{\operatorname{Ind}} \newcommand{\Coind}{\operatorname{Coind}} \newcommand{\id}{\operatorname{Id}} \newcommand{\re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\Ker}{\operatorname{Ker}} \newcommand{\Ext}{\operatorname{Ext}} \newcommand{\F}{{\mathbb F}} \newcommand{\Log}{{\operatorname{Log}}} \newcommand{\pr}{{\operatorname{pr}}} \newcommand{\Graph}{{\operatorname{Graph}}} \newcommand{\Tor}{{\operatorname{Tor}}} \newcommand{\const}{{\operatorname{const}}} \newcommand{\Arc}{{\operatorname{Arc}}} \newcommand{\Span}{{\operatorname{Span}}} \newcommand{\Aut}{{\operatorname{Aut}}} \newcommand{\Int}{{\operatorname{Int}}} \newcommand{\Aff}{{\operatorname{Aff}}} \newcommand{\Area}{{\operatorname{Area}}} \newcommand{\val}{{\operatorname{Val}}} \newcommand{\conv}{{\operatorname{conv}}} \newcommand{\rk}{{\operatorname{rk}}} \newcommand{\End}{\operatorname{End}} \newcommand{\C}{{\mathbb C}} \newcommand{\Z}{{\mathbb Z}} \newcommand{\g}{{\mathfrak g}} \newcommand{\tet}{{\theta}} \newcommand{\Del}{{\Delta}} \newcommand{\bet}{{\beta}} \newcommand{\fm}{{\mathfrak m}} \newcommand{\kap}{{\kappa}} \newcommand{\del}{{\delta}} \newcommand{\eps}{{\varepsilon}} \newcommand{\sig}{{\sigma}} \newcommand{\alp}{{\alpha}} \newcommand{\Sig}{{\Sigma}} \newcommand{\Gam}{{\Gamma}} \newcommand{\gam}{{\gamma}} \newcommand{\Lam}{{\Lambda}} \newcommand{\lam}{{\lambda}} \newcommand{\om}{{\omega}} \newcommand{\T}{{\mathcal{T}}} \newcommand{\fh}{{\mathfrak{h}}} \newcommand{\fn}{{\mathfrak{n}}} \newcommand{\gl}{{\mathfrak{gl}}} \newcommand{\Lie}{\operatorname{Lie}} \newcommand{\ad}{\operatorname{ad}} \newcommand{\Ad}{\operatorname{Ad}} \newcommand{\sign}{\operatorname{sign}} \newcommand{\abs}[1]{\left|{#1}\right|} \newcommand{\norm}[1]{\lVert#1\rVert} \newcommand{\p}{\mathfrak{p}} \newcommand{\cV}{\mathcal{V}} \newcommand{\bV}{\mathbf{V}} \newcommand{\bT}{\mathbf{T}} \newcommand{\ex}{\mathit{ex}} \newcommand{\faith}{\mathit{faith}} \newcommand{\Fun}{\mathrm{Fun}} \newcommand{\Map}{\operatorname{Map}} \newcommand{\Mod}{\operatorname{Mod}} \newcommand{\sVect}{\mathtt{sVect}} \newcommand{\PP}{{\mathfrak P}} \newcommand{\urep}{Rep(\underline{P})} \newcommand{\urepk}[1]{Rep^{#1}(\underline{P})} \newcommand{\s}{\mathtt{s}} \newcommand{\bdel}{\pmb{\Delta}} \newcommand{\bnab}{\pmb{\nabla}} \renewcommand{\L}{\pmb{L}} \newcommand{\Alg}{\mathrm{Alg}_{\T}} \newcommand{\Grps}{\mathrm{Grps}} \newcommand{\sgn}{\mathtt{sgn}} \def\quotient#1#2{ \raise1ex\hbox{$#1$}\Big/\lower1ex\hbox{$#2$} } \newcommand*\circled[1]{\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=0.5pt] (char) {#1};}} \title{McKay trees} \author[\initial{A.} Aizenbud]{\firstname{Avraham} \lastname{Aizenbud}} \address{Department of Mathematics,\\ Weizmann Institute of Science,\\ Rehovot,\\ Israel} \email{aizenr@gmail.com} \author[\initial{I.} Entova-Aizenbud]{\firstname{Inna} \lastname{Entova-Aizenbud}} \address{Department of Mathematics,\\ Ben Gurion University of the Negev,\\ Beer-Sheva,\\ Israel} \email{entova@bgu.ac.il} \thanks{The authors would like to thank David Speyer and the anonymous referee for the helpful comments. A. A. was partially supported by ISF grant 249/17 and a Minerva foundation grant. I. E.-A. was supported by the ISF grant 711/18.} \subjclass{20C15} \keywords{Representation theory, groups, McKay graphs} \begin{DefTralics} \newcommand{\Hom}{\operatorname{Hom}} \end{DefTralics} \begin{document} \newtheorem{introtheorem}[cdrthm]{Theorem} \newtheorem{problem}[cdrthm]{Problem} \begin{abstract} Given a finite group $G$ and its representation $\rho$, the corresponding McKay graph is a graph $\Gamma(G,\rho)$ whose vertices are the irreducible representations of $G$; the number of edges between two vertices $\pi,\tau$ of $\Gamma(G,\rho)$ is $dim \Hom_G(\pi\otimes \rho, \tau) $. The collection of all McKay graphs for a given group $G$ encodes, in a sense, its character table. Such graphs were also used by McKay to provide a bijection between the finite subgroups of $SU(2)$ and the affine Dynkin diagrams of types $A, D, E$, the bijection given by considering the appropriate McKay graphs. In this paper, we classify all (undirected) trees which are McKay graphs of finite groups and describe the corresponding pairs $(G,\rho)$; this classification turns out to be very concise. Moreover, we give a partial classification of McKay graphs which are forests, and construct some non-trivial examples of such forests. \end{abstract} \maketitle \section{Introduction} \subsection{Definition of the McKay graph} For a finite group $G$ and its complex representation $\rho$, we consider the McKay graph $\Gamma(G, \rho)$: its vertices are given by the set $\mathrm{Irr}(G)$ of irreducible complex representations of $G$, and the number of edges $N_{\pi,\tau}$ between two vertices $\pi,\tau \in \mathrm{Irr}(G)$ of $\Gamma(G,\rho)$ is $\dim \Hom_G (\pi\otimes \rho, \tau) $. In general, this is a directed graph. We will consider undirected graphs as a special case of directed graphs. If $\rho$ is self-dual then $N_{\pi,\tau}=N_{\tau,\pi}$ and the adjacency matrix of the graph $\Gamma(G,\rho)$ is symmetric. In this case we will consider the McKay graph as an undirected graph, with an undirected edge corresponding to a pair of directed edges of opposite directions. \subsection{Main results} We work over the base field $\C$. In this paper we consider McKay graphs which are \textup{(}undirected\textup{)} forests: these are undirected graphs without closed paths \textup{(}in a path, no repetitions of edges are allowed\textup{)}. In particular, in such a graph there is at most one edge between each $2$ vertices, and no edges from a vertex to itself. \begin{introtheorem}[See {Proposition \ref{prop:forest},} Theorem \ref{thrm:forest}]\label{introthm:forests} Let $G$ be a finite group and $\rho$ its representation. Assume that the McKay graph $\Gamma(G,\rho)$ is a forest. Then we have: \begin{enumerate} \item $\rho$ is irreducible and self-dual. \item Each of these components is isomorphic to one of the following: \begin{enumerate} \item An affine Dynkin diagram of type $\tilde{D}_{n}$, $n\geq 4$. \item An affine Dynkin diagram of type $\tilde{E}_n$ \textup{(}for $n=6,7,8$\textup{)}. \item A ``hedgehog'': a tree with $4^n$ leaves and one vertex connected to all of these leaves\footnote{For $n=0$, we obtain a graph with $2$ vertices and an unoriented edge between them.}, where $n\geq 0$. \end{enumerate} Furthermore, if one of the components is a ``hedgehog'' with $4^n$ leaves, $n\neq 1$, then all the remaining components are hedgehogs with the same number of leaves, $4^n$. \end{enumerate} \end{introtheorem} Our second result concerns McKay graphs which are trees (i.e. connected forest graphs): \begin{introtheorem}[See Theorem \ref{thrm:main}]\label{introthm:trees} Assume $\Gamma(G,\rho)$ is a tree. Then the pair $(G,\rho)$ is isomorphic to one of the following pairs: \begin{enumerate} \item $G$ is a dihedral group of order divisible by $4$, and $\rho$ is the complexification of its natural $2$-dimensional real representation. \item $G \subset SU(2)$ is a binary polyhedral group of type $D$ or $E$ and $\rho$ is the natural $2$-dimensional representation of $G$. \item $G$ is an extra special group of order $2^{1+2n}$ for some $n\geq 0$, i.e. a central extension of $(\Z/2\Z)^{2n}$ by $\Z/2\Z$. In that case, $\rho$ is the unique irreducible representation of $G$ of dimension~$2^n$. \end{enumerate} \end{introtheorem} \begin{rema}\label{intrormk:principal_comp} The connected component of the McKay graph $\Gamma(G,\rho)$ containing the trivial representation is called the principal component of $\Gamma(G,\rho)$ and it is itself a McKay graph for the group $G/\Ker(\rho)$ and its faithful representation $\rho$. If $\Gamma(G,\rho)$ is a forest, our second result describes the pair $(G/\Ker(\rho), \rho)$ up to isomorphism. \end{rema} { Finally, we construct some examples of McKay graphs which are forests with non-isomorphic connected components. Constructing such forests where all the connected components are isomorphic to a given tree from the list above is very easy: for $n\geq 2$, let $(G, \rho)$ be as in Theorem~\ref{introthm:trees}, and consider the McKay graph $\Gamma(G\times \Z/n\Z, \rho \boxtimes \triv)$; this graph is the union of $n$ copies of the tree~$\Gamma(G, \rho)$. Constructing and classifying forests whose connected components have different sizes seems to be a much more challenging problem. We give several examples of such forests in Section \ref{ssec:forest_examples}. } \subsection{Background and motivation} Let $G$ be a finite group. Then one can reconstruct the isomorphism class of $G$ from the monoidal category of representations of~$G$. Therefore, while classifying such monoidal categories is a central and interesting problem, in full generality it is as {complex} as the problem of classifying finite groups. A numerical shadow of the monoidal category of representations of $G$ is the character table of $G$. It is well-known that this shadow is not enough to reconstruct the group $G$ (for instance, the dihedral group $Dih_4$ and the quaternion group $Q_8$ have the same character table). Yet even the question of describing all {possible} character tables still looks very difficult in general. The McKay graph is a combinatorial way to describe a piece of this character table. In fact, the data in the character table of a group $G$ is equivalent to the data of all the McKay graphs $\Gamma(G, \rho)$ where $\rho$ runs over the irreducible representations of $G$ and the labeling of the vertices in the graphs is fixed. Another motivation to consider McKay graphs is the fact that they are spectral analogues of the Cayley graphs. So the starting point for this paper is the following: \pagebreak \begin{problem} \mbox{} \begin{enumerate} \item Which (directed) graphs $\Gamma$ are McKay graphs for some finite group $G$ and some representation $\rho$ of $G$? \item Given a finite (directed) graph $\Gamma$ which is a McKay graph, what are the different pairs $(G,\rho)$ such that $\Gamma=\Gamma(G,\rho)$? \end{enumerate} \end{problem} It is not clear whether any of these questions can be answered in full generality. We do not expect a comprehensive answer to both of them, since this is equivalent to describing all finite groups and their representations. However, we believe that studying special cases of this problem is illuminating. In the present paper, we {give a partial} answer {to} the first question in the case when $\Gamma$ is an (undirected) forest and {answer both questions} in the case when $\Gamma$ is an (undirected) tree. \subsection{Related works}\label{ssec:intro_rel_works} In \cite{McKay}, McKay classified {connected} McKay graphs with spectral radius $2$; this leads to the ADE classification of the finite subgroups of $SU(2)$, and can be adapted to the classification of pairs $(G,\rho)$ where $\rho$ is a $2$-dimensional self-dual faithful representation of $G$ (see Proposition \ref{prop:McKay_classification}). {This result was preceded by a classification of all connected simple graphs with spectral radius $2$, due to Smith (see \cite{Smith}), which were shown to be affine Dynkin diagrams of type $A, D$ or $E$.} \subsection{Sketch of the proof} \subsubsection{The case of a tree graph} One of the main methods to study a McKay graph $\Gamma(G,\rho)$ is to observe that if we consider its adjacency matrix as an operator from the linear span of $\mathrm{Irr}(G)$ to itself, then this operator can be realized as the multiplication by $\chi_\rho$ when we identify the linear span of $\mathrm{Irr}(G)$ with the space of class functions on~$G$. Recall that a graph $\Gamma$ is a tree if and only if the following holds: \begin{enumerate}[label=(\alph*)] \item it is undirected, \item it is connected, \item the number of its vertices exceeds by 1 the number of its (undirected) edges. \end{enumerate} If $\Gamma=\Gamma(G,\rho)$ is a McKay graph, then the first condition is equivalent to the fact that $\rho$ is self-dual, and the second condition is equivalent to the fact that $\rho$ is faithful. So it is left to exploit the third condition. In order to do this, we prove (in Corollary~\ref{cor:trace}) the following formula for a general undirected McKay graph $\Gamma = \Gamma(G, \rho)$: \begin{equation}\label{eq:dim.formula} 2\abs{\{\text{undirected edges in } \Gamma\}}=tr(A_\Gamma^2)= \hspace{-0.4cm} \sum_{[x]\in G//G} \hspace{-0.35cm} \chi_\rho(x)^2 = \hspace{-0.35cm} \sum_{[x]\in G//G} \hspace{-0.35cm} \dim \End_{C(x)}\left( \rho\downarrow_{C(x)}\right), \end{equation} Here \begin{itemize} \item $A_\Gamma$ is the adjacency matrix of the graph $\Gamma$. \item $x$ ranges over (a set of representatives of) the conjugacy classes of $G$. \item $C(x)$ denotes the centralizer of $x$. \end{itemize} We use this formula in order to deduce that if $\Gamma$ is a forest then $\rho$ is irreducible and for any non-central $x \in G$, we have (see the proof of Proposition \ref{prop:forest}): \begin{equation}\label{eq:dim2} \dim(\End(\rho\downarrow_{C(x)}))=2. \end{equation} We finish the argument in the proof of Theorem \ref{introthm:trees} by considering the following cases: \begin{enumerate}[label=(\alph*)] \item {\it $C(x)$ is abelian for some $x\in G$.} In this case it is easy to see that $\rho$ is 2-dimensional, so we can use McKay's classification (see Section \ref{ssec:intro_rel_works}). \item {\it $C(x)$ is non-abelian for any $x\in G$.} In this case we prove that $G$ is an extra special $2$-group (i.e. a $2$-group of unipotent depth $2$ and center of order $2$). Since such groups are classified (see \cite{Aschbacher, Diaconis}), this completes the argument behind the proof of Theorem \ref{introthm:trees}. \end{enumerate} \subsubsection{The case of forests} {We give below an overview of the main ingredients in the proof of Theorem \ref{introthm:forests}.} { \begin{enumerate}[label=(\alph*)] \item Let $N=\Ker(\rho)$ and consider the action of $G$ on $\mathrm{Irr}(N)$ induced by the conjugation action of $G$ on $N$. It is well-known that the set of connected components of a McKay graph $\Gamma(G,\rho)$ is naturally indexed by the set of $G$-orbits $\mathrm{Irr}(N)//G$. The indexing is obtained by restricting a representation $\mu\in \Gamma(G,\rho)$ to $N$ (see Lemma \ref{lem:connected_comp_Browne}). \item Let $\tau\in \mathrm{Irr}(N)$ and let $T\in \mathrm{Irr}(N)//G$ be the $G$-orbit of $\tau$. Let $\Gamma_T(G,\rho)$ be the connected component of $\Gamma(G,\rho)$ corresponding to $T$. Then we have (see Lemma \ref{lem:conn_comp_sum_of_sq}): \begin{equation}\label{eq:intro_sum_of_sq} \sum_{\mu\in \Gamma_T(G,\rho)} (\dim \mu)^2=|G/N||T|(\dim\tau)^2. \end{equation} \item Using Remark \ref{intrormk:principal_comp}, we conclude that the principal component $\Gamma_\triv$ is either an affine Dynkin diagram of types $D$ or $E$ (in that case, $\dim(\rho)=2$), or a hedgehog with $4^n$ spines (in that case, $\dim(\rho)=2^n$). \item If $\dim(\rho)=2$, we use {Smith's} classification of graphs with spectral radius $2$ (see \cite{Smith}) to state that all the connected components will be affine Dynkin diagrams of types $D$ or $E$. \item If the principal component is a hedgehog, we use \eqref{eq:intro_sum_of_sq} to show that $|T|=1$ for any $T\in \mathrm{Irr}(N)//G$, and conclude that all the connected components in this case are isomorphic to the principal one. \end{enumerate} } We then give some examples of McKay graphs which are forests with non-isomorphic connected components. {It would be interesting to understand which combinations of affine Dynkin diagrams of types $\tilde{D}, \tilde{E}$ may occur, and for which groups $G$ the disjoint unions of hedgehogs may appear.} In a follow-up paper, we plan to investigate this question further. \subsection{Structure of the paper} In Section \ref{sec:prelim} we give the required preliminaries on groups and McKay graphs, including the definition of the extraspecial groups (see Section \ref{ssec:extra_special}) and the McKay correspondence between affine Dynkin diagrams and finite subgroups of $SU(2)$ (see Section \ref{ssec:mckay_class}). In Section \ref{sec:Aux} we prove some auxiliary results, such as a criterion for a McKay graph {to be connected bipartite} and the formula $$\forall k\geq 1, \;\; \dim \Hom_G(\rho^{\otimes k}, \C[G]^{adj}) = \abs{\{\text{circuits of length } k \text{ in } \Gamma \}}, $$ which we use later on. In Section \ref{sec:trees} we prove Theorem \ref{introthm:trees}. In Section \ref{sec:forests} we prove Theorem \ref{introthm:forests} and construct some non-trivial examples of forests in Subsection \ref{ssec:forest_examples}. \section{Preliminaries and notation}\label{sec:prelim} The base field throughout the paper is $\C$. \subsection{Notation} \begin{nota} Let $G$ be a finite group. \begin{itemize} \item We denote by $1_G$ its unit element, by $Z(G)$ its center, by $G//G$ the set of conjugacy classes of $G$, and by $C(g)$ the centralizer of $g\in G$. \item We denote by $\mathrm{Irr}(G)$ the set of its irreducible representations and by $\triv$ its trivial representation. \item We denote by $\C[G]^{adj}$ the conjugation representation of $G$ on its group algebra. \item For any representation $\rho$ of $G$, we denote by $\chi_\rho: G\to \C$ its character, where $\chi_\rho(g)\coloneqq tr (\rho(g))$. By abuse of notation, we use the same notation for the corresponding function $\chi_\rho: G//G \to \C$. \item We say that a group $G$ is $p$-torsion, where $p$ is prime, if $g^p = 1_G$ for each $g \in G$. \item Given a subgroup $H < G$, a $G$-representation $\rho$ and an $H$-representation $\tau$, we denote by $\rho \downarrow_H$ the restriction of $\rho$ to $H$ and by $\tau \uparrow^G_H$ the induction of $\tau$ to $G$. \end{itemize} \end{nota} \begin{nota} {For $n\geq 2$, we will denote by $C_n$ the cyclic group of order $n$. For prime $p$, the elementary abelian group $p$-group $C_p^{\times k}$ will sometimes be denoted $\mathbb{F}_p^k$.} \end{nota} \begin{nota} {For $n\geq 3$,} we will denote by $\mathrm{Dih}_n$ the dihedral group of order $2n$ (group of symmetries of the regular $n$-gon). {We will also denote by $\mathrm{Dih}_2$ the group $C_2 \times C_2$ (considered as the group of symmetries of a digon).} \end{nota} \begin{nota} Let $\Gamma$ be a directed graph. \begin{itemize} \item We denote by $X(\Gamma)$ the set of vertices of $\Gamma$. \item We denote by $\mathtt{N}(x)$ the multiset of neighbors of a vertex $x$ in $\Gamma$: those are $y\in X(\Gamma)$ with an edge $x\to y$ in $\Gamma$ (if there are several edges $x \to y$, then $y$ appears with appropriate multiplicity in $\mathtt{N}(x)$. \item A loop is an edge connecting a vertex to itself). \item A graph $\Gamma$ is called {\it simply-laced} if for each $x, y \in X(\Gamma)$ it contains at most one edge $x \to y$. \item A {\it walk} in $\Gamma$ is a sequence of edges $(e_0, \ldots, e_s)$ such that the end of $e_i$ is the beginning of $e_{i+1}$ for each $i2$. \item For $p=2$ the above examples coincide: we have $\mathrm{Heis}(2)\cong C_4 \rtimes C_2 \cong \mathrm{Dih}_4$. Another (non-isomorphic) extra special group of order $8$ is the quaternion group $Q_8$. \item Given a finite-dimensional vector space $V$ over the field $\F_p$, we can define the generalized Heisenberg group $\mathrm{Heis}(V)$ as follows: the underlying set is $V \times V^* \times \F_p$ and the multiplication is given by $$(\vec{a}, \vec{b}, c)(\vec{a'}, \vec{b'}, c') = (\vec{a} +\vec{a}, \vec{b}+\vec{b'}, c + c' + \vec{b'}\cdot\vec{a})$$ where $-\cdot -$ denotes the obvious pairing $V^* \times V \to \F_p$. This group $\mathrm{Heis}(V)$ is an extra special $p$-group of order $p^{1+2\dim V}$. \end{itemize} \end{exam} It turns out that such groups exist only if $N$ is even, i.e. $N=2n$ for some $n\geq 0$; moreover, for each power $p^{1+2n}$ ($n\geq 1$) there exist precisely two isomorphism classes of extra special $p$-groups of order $p^{1+2n}$. For $p>2$, any extra special $p$-group of order at least $p^3$ is a central product of several copies of the two groups of order $p^3$ appearing in Example \ref{ex:extra_special_groups}. If all of the $n$ factors appearing in the central product are isomorphic to $\mathrm{Heis}(p)$ then the obtained group is generalized Heisenberg group $\mathrm{Heis}(\F_p^n)$ and it is $p$-torsion. If at least one of the $n$ factors is of the form $C_{p^2} \rtimes C_p$ then we obtain another, non-isomorphic extra special group of order $p^{1+2n}$, but now having some elements of order~$p^2$. For $p=2$, a similar situation occurs: any extra special $2$-group of order at least $8$ is a central product of several copies of $\mathrm{Dih}_4$ and $Q_8$. If all of the $n$ factors appearing in the central product are isomorphic to $\mathrm{Dih}_4$ then the obtained group is the generalized Heisenberg group $\mathrm{Heis}(\F_2^n)$. If at least one of the $n$ factors is of the form $Q_8$ then we obtain another, non-isomorphic extra special group of order $2^{1+2n}$. An extra special $p$-group $G$ of order $p^{1+2n}$ has precisely $p^{2n}$ representations of dimension $1$ on which the center $Z(G)$ acts trivially, and $p-1$ representations of dimension $p^n$ on which the center $Z(G)$ acts by a non-trivial character. \subsection{Preliminaries on McKay graphs} The definitions and statements of this subsection are taken from \cite{McKay}. \begin{defi}[McKay graph] Let $G$ be a finite group, $\rho$ a complex representation of~$G$. The {\it McKay graph} $\Gamma(G, \rho)$ (sometimes called ``McKay quiver'') for the pair $(G, \rho)$ has vertex set $\mathrm{Irr}(G)$; the number of edges $\mu \to \lam$, where $\mu,\lam \in \mathrm{Irr}(G)$, is $$\dim \Hom_G(\mu \otimes \rho,\lam) = [\mu\otimes \rho:\lam]_G$$ where the latter denotes the multiplicity of $\lam$ in the $G$-representation $\mu\otimes \rho$. \end{defi} When drawing a McKay graph, we will usually mark by a $\bigstar$ symbol the vertex corresponding to the trivial representation. The other vertices are each marked by the dimension of the corresponding irreducible representation. \begin{exam} \mbox{} \begin{enumerate} \item Let $G= C_2$ and $\sgn$ be the non-trivial irreducible representation of $C_2$ (``sign representation''). Then $\Gamma(C_2, \sgn)$ is an undirected loop-less graph on $2$ vertices: $$ \begin{tikzcd}[arrows=-] \bigstar\arrow[r] & \circled{1} \end{tikzcd} $$ \item Let $G= \Z/n\Z$ and $\tau$ be its non-trivial irreducible representation. Then $\Gamma(\Z/n\Z, \tau)$ is a directed cycle graph on $n$ vertices, without double edges nor loops. \item {Let $n\geq 1$ and let $G = \mathbb{F}_2^n = C_2^{\times n}$ be the corresponding elementary abelian $2$-group}. Let $\rho = \bigoplus_{0 \leq s \leq n-1} \triv^{\boxtimes s} \boxtimes \sgn \boxtimes \triv^{\boxtimes n-s-1} $. The McKay graph $\Gamma(\mathbb{F}_2^n, \rho)$ is then the $n$-dimensional cube $\{0, 1\}^n$ with undirected edges $\xymatrix{x \ar@{-}[r]&y}$ whenever $x,y \in \{0, 1\}^n$ differ by precisely one coordinate. \item Let $G = S_3 = \mathrm{Dih}_3$ be the symmetric group on $3$ letters. We denote its irreducible representations by $\triv, \sgn, \mathtt{ref}$ where $\sgn$ is the $1$-dimensional sign representation and $\mathtt{ref}$ is the two-dimensional reflection representation $\{(x_1, x_2, x_3) \in \C^3, \sum x_i =0\}$. The McKay graph $\Gamma(S_3, \mathtt{ref})$ is $$ \begin{tikzcd}[arrows=-] \bigstar\arrow[r] & \circled{2} \arrow[ld] \arrow[loop right]{r}\\ \circled{1} \end{tikzcd} $$ This is an undirected graph on $3$ vertices, with a single loop. \item Consider the dihedral group $\mathrm{Dih}_{4}$ and let $\tau$ be its tautological $2$-dimensional (irreducible) representation. The McKay graph of $(\mathrm{Dih}_{4}, \tau)$ looks as follows: $$ \begin{tikzcd}[arrows=-] \bigstar&& \circled{1} \\ &\ \circled{2} \arrow[ru]\arrow[lu]\arrow[ld]\arrow[rd]\\ \circled{1} && \circled{1} \end{tikzcd} $$ Here the vertex in the center corresponds to $\tau$. This graph coincides with the McKay graph for $(Q_8, \mu)$ where $Q_{8}$ is the quaternion group and $\mu$ is the obvious $2$-dimensional (irreducible) representation given by $\mathbb{H} \cong \C^2$. This coincidence is not surprising, given that the character tables of $\mathrm{Dih}_{4}$, $Q_8$ coincide. \end{enumerate} \end{exam} \begin{exam}\label{ex:extra_special} Consider an extra-special $2$-group $G$ of order $2^{1+2n}$, $n\geq 0$ as described in Section~\ref{ssec:extra_special} (for $n=0$, the corresponding extra special group is unique, and it is just $C_2$). Then $G$ has $2^{2n}+1$ irreducible representations: $2^{2n}$ irreducible representations of dimension $1$ coming from $G/Z(G) \cong \mathbb{F}_2^{2n}$ and one irreducible representation $\rho$ of dimension $2^n$. The McKay graph for $(G, \rho)$ is an unoriented connected graph of th following form: it has one vertex $\rho$ with ${4}^n$ unoriented edges coming out, and ${4}^n$ vertices connected only to $\rho$ by a single unoriented edge. {We will call such a graph {\it a hedgehog with $4^n$ spines}.} Below is an example for $n=2$: $$ \begin{tikzcd}[arrows=-] \bigstar& \circled{1}& \circled{1}& \circled{1}& \circled{1}\\ \circled{1} &&&& \circled{1} \\ \circled{1} & & \circled{\normalsize $2^n$} \arrow[rr]\arrow[rru]\arrow[rruu]\arrow[ruu]\arrow[uu]\arrow[ll] \arrow[llu]\arrow[lluu]\arrow[luu]\arrow[rrd]\arrow[rrdd]\arrow[rdd]\arrow[dd] \arrow[lld]\arrow[lldd]\arrow[ldd]&& \circled{1} \\ \circled{1} &&&& \circled{1} \\ \circled{1}& \circled{1}& \circled{1}& \circled{1}& \circled{1}\\ \end{tikzcd} $$ \end{exam} The following statement is well-known (see \cite[Proposition 2]{McKay}): \begin{lemma}\label{lem:undirected} Let $\rho$ be a representation of the group $G$. Then $\Gamma(G, \rho^*)$ is obtained from $\Gamma(G, \rho)$ by a reversal of arrows (i.e. $A_{\Gamma(G, \rho^*)} = A_{\Gamma(G, \rho)}^T$). In particular, $\rho\cong \rho^*$ if and only if $\Gamma(G, \rho)$ is undirected (i.e. $A_{\Gamma(G, \rho)}$ is a symmetric matrix). \end{lemma} The spectrum of the adjacency matrix of a McKay graph has an explicit description, see \cite[Proposition 6]{McKay}, \cite[Proposition 2.3]{Browne}, and \cite{Steinberg}: \begin{prop}\label{prop:spectra_adj_matrix} The eigenvalues of $A_{\Gamma(G, \rho)}$ form the multiset $$\{\chi_{\rho}(g) |g\in G//G\}.$$ A corresponding eigenvector for the eigenvalue $\chi_{\rho}(g) $ is $\chi(g):\mathrm{Irr}(G) \to \C, \, \mu \mapsto \chi_{\mu}(g)$ (a column of the character table). \end{prop} Since $\chi_{\rho}(g), g\in G$ is the sum of eigenvalues of $\rho(g)$, all of which are roots of unity, we have: \begin{coro}\label{cor:spectral_radius_adj_matrix} The eigenvalue of $A_{\Gamma(G, \rho)}$ with the maximal absolute value (the {\it spectral radius} of $A_{\Gamma(G, \rho)}$) is $\chi_\rho(1_G) = \dim \rho$. A corresponding eigenvector is then $$\dim:\mathrm{Irr}(G) \to \C, \, \mu \mapsto \dim(\mu).$$ \end{coro} The spectral radius of a real matrix $A$ with non-negative entries has an important property given by the Frobenius-Perron theorem: the corresponding eigenspace of $A$ contains a vector all of whose entries are non-negative. In fact, if $A$ is an ``irreducible'' matrix (one which cannot be presented as a block matrix with non-trivial blocks), the spectral radius has multiplicity $1$ as an eigenvalue of $A$, and it is the only eigenvalue of $A$ for which an eigenvector with positive entries exists. For example, the adjacency matrix of a {\it strongly connected} graph $\Gamma$ (one where there is a directed walk from each vertex to any other vertex) is always irreducible, and hence its spectral radius has multiplicity $1$. \subsection{Shapes of McKay graphs} Let us give some basic examples of graphs which can or cannot appear as McKay graphs $\Gamma(G, \rho)$ for some $G, \rho$. \begin{exam} \begin{enumerate} \item Given a group $G$ and a representation $\rho$ of $G$, the representation $\rho$ is $1$-dimensional if and only if the McKay graph $\Gamma(G, \rho)$ is a disjoint union of directed cycles (some of the cycles might consist of $1$ vertex only, with a single loop). Any disjoint union of directed cycles of equal size can appear as a McKay graph: if we have $k$ disjoint directed cycles of size $n$, this is the McKay graph for $(\Z/n\Z \times G, \tau\boxtimes \triv)$ where $\tau$ is an irreducible representation of $\Z/n\Z$, and $G$ is any finite group with precisely $k$ irreducible representations (e.g. $G=\Z/k\Z$). \item A McKay graph $\Gamma(G, \rho)$ cannot be a directed tree or a disjoint union of such: indeed, one cannot have ``leaves'' (i.e. vertices with only one edge coming in or going out) in a directed McKay graph. \item Considering the opposite extreme situation, a complete (undirected, loop-less) graph on $n$ vertices - such a graph can be obtained as $\Gamma(\Z/n\Z, \rho)$. Here $\rho$ is the representation of $\Z/n\Z$ on $\C^n/\Span\{(1,\ldots, 1)\}$, where $\Z/n\Z$ acts on $\C^n$ by shifting cyclically the coordinates. \item A complete graph on $n$ vertices ($n>2$) cannot be obtained as a McKay graph $\Gamma(G, \rho)$ if we require $\rho \in \mathrm{Irr}(G)$. This is due to the fact that in any McKay graph $\Gamma(G, \rho)$ with $\rho \in \mathrm{Irr}(G)$, the vertex $\triv$ has only one neighbor: the vertex~$\rho$. Yet a given a complete (undirected, loop-less) graph on $n$ vertices, we can always find a McKay graph $\Gamma(G, \rho)$ containing our complete graph as a sub-graph: for instance, take $G = S_N$ (the symmetric group) for $N>>n$ and $\rho$ to be the reflection representation. \end{enumerate} \end{exam} \subsection{Connected components in McKay graphs} Given two vertices $\mu, \lam$ in a McKay graph, we can ask whether there is a directed walk from $\mu$ to $\lam$, or whether there is a walk from $\mu$ to $\lam$ if we forget about the directions of the edges in our graph. Although for general graphs these relations do not coincide, it turns out that in McKay graphs they do (see \cite[Section 3]{Browne}), so the notion of a connected component in a McKay graph is intuitive; each such component is ``strongly connected''. Given a McKay graph $\Gamma(G, \rho)$, the connected component $\Gamma_{\triv}$ containing the vertex $\triv$ is called the {\it principal component}. The following statement is well-known, see for example \cite[Proposition 1]{McKay}, \cite[Proposition 3.3]{Browne}: \begin{lemma}\label{lem:connectivity} Let $\rho$ be a representation of the group $G$. Then $\rho$ is faithful if and only if $\Gamma(G, \rho)$ is connected (that is, for any $\mu, \lam \in \mathrm{Irr}(G)$ there exists a walk from $\mu$ to $\lam$ in $\Gamma(G, \rho)$). \end{lemma} In fact, given any representation $\rho$ of $G$ with kernel $N = \Ker(\rho)$, the principal component $\Gamma_{\triv}$ is isomorphic to $\Gamma(G/N, \rho)$. The connected components of $\Gamma(G, \rho)$ correspond to blocks in the adjacency matrix $A_{\Gamma(G, \rho)}$; the number of such blocks is then the multiplicity of the largest eigenvalue, implying the following lemma (see also \cite[Proposition 3.10, Lemma 4.1]{Browne}): \begin{lemma}\label{lem:connected_comp_Browne} \mbox{} \begin{enumerate} \item The number of connected components of $\Gamma(G, \rho)$ is precisely the number of $G$-conjugacy classes of $N$; the latter equals the number of $G$-orbits in $\mathrm{Irr}({N})$ ($G$ acts on $\mathrm{Irr}(N)$ twisting the action of $N$ on the representations). In fact, there is a bijection $$\{\text{ connected components of } \Gamma(G, \rho)\} \longrightarrow \mathrm{Irr}(N)//G$$ given as follows: to every connected component $\Gamma'$ of $\Gamma(G, \rho)$ corresponds a unique $G$-orbit $T \subset \mathrm{Irr}(N)$ such that $[\mu \downarrow^G_N: \tau] \neq 0$ for some $\mu \in X(\Gamma_T) \subset \mathrm{Irr}(G)$ and some $\tau \in T \subset N$. \item The group $\widehat{G}$ of characters $G \to \C^{\times}$ acts on the graph $\Gamma(G, \rho)$ by tensoring each vertex with the appropriate $1$-dimensional representation. \end{enumerate} \end{lemma} \begin{coro}\label{cor:conn_comp_isomorphic} Let $\Gamma'$ be a connected component of $\Gamma(G, \rho)$ with a vertex $\mu$ such that $\dim \mu=1$. Then the graph $\Gamma'$ is isomorphic to the principal component $\Gamma_{\triv}$. \end{coro} In fact, we have the following useful identity: \begin{lemma}\label{lem:conn_comp_sum_of_sq} Let $T \in \mathrm{Irr}(N)//G$ and $\Gamma_T$ the corresponding connected component in $\Gamma(G, \rho)$. Let $\tau \in T$. We have: $$\sum_{\mu \in X(\Gamma_T)}(\dim \mu)^2 = \abs{G/N}\cdot (\dim\tau)^2 \cdot \abs{T}. $$ \end{lemma} \begin{proof} Given $\mu\in \mathrm{Irr}(G)$, the multiplicity $[\mu \downarrow^G_N: \tau]$ does not depend on choice of $\tau\in T$ by Clifford's theorem, and $[\mu \downarrow^G_N: \tau']=0$ for all $\tau'\notin T$. Hence, we have: $ \dim \mu = \dim \tau \cdot \abs{T} \cdot [\mu \downarrow^G_N: \tau] $ for $\mu \in X(\Gamma_T)$. In other words, $${[\tau\uparrow^G_N: \mu]}=[\mu \downarrow^G_N: \tau] = \frac{\dim \mu }{\dim \tau \cdot \abs{T}}.$$ Consider $\tau\uparrow^G_N$; by Lemma \ref{lem:connected_comp_Browne}, all its irreducible direct summands are in $X(\Gamma_T)$. We have: \begin{align*} \abs{G/N}\cdot\dim \tau = \dim (\tau\uparrow^G_N) = \sum_{\mu \in X(\Gamma_T)}[\tau\uparrow^G_N: \mu]\dim \mu = \sum_{\mu \in X(\Gamma_T)}\frac{(\dim \mu )^2}{\dim \tau \cdot \abs{T}} \end{align*} The required statement is proved. \end{proof} \section{Auxiliary results}\label{sec:Aux} \subsection{McKay classification}\label{ssec:mckay_class} In this paper, the term {\it binary polyhedral group} (denoted by appending $\mathrm{B}$ to the notation of the group) stands for a group $G$ which is a double cover of the polyhedral group of given type. {The polyhedral groups we consider are finite subgroups of $SO(3, \mathbb{R})$: these the rotational symmetry groups of the regular polyhedra, denoted by $\mathbf{T}$ (tetrahedral group), $\mathbf{O}$ (octahedral group) and $\mathbf{I}$ (icosahedral group), as well as the dihedral groups $\mathrm{Dih}_n$, $n\geq 2$. The latter are embedded naturally into $SO(3, \mathbb{R})$ by considering them as symmetries of ``degenerate" polyhedra: polygons which lie in the plane $XY$ of $\mathbb{R}^3$. \begin{exam}\label{ex:Dih_2} The subgroup of $SO(3, \mathbb{R})$ corresponding to $\mathrm{Dih}_2 \cong C_2 \times C_2$ consists of matrices $ \begin{bmatrix} \pm 1 &0\\ 0 &\pm 1 \end{bmatrix}$. These are precisely the rotations around the coordinate axes by multiples of $\pi$ radians. \end{exam}} \begin{exam} The {\it binary dihedral group} (also known as ``dicyclic group'') $\mathrm{B}\mathrm{Dih}_{n}$ ($n\geq 2$) has presentation $$\langle a, x | a^{2n} = 1, x^2=a^n, x^{-1}ax = a^{-1}\rangle.$$ It has center $Z =\{1, a^n\}\cong C_2$ and the quotient $\mathrm{B}\mathrm{Dih}_{n}/Z$ is the dihedral group $\mathrm{Dih}_{n}$. For $n=2$, we have $\mathrm{Dih}_{2} \cong C_2 \times C_2$ and we obtain an isomorphism $\mathrm{B}\mathrm{Dih}_{2} \cong Q_8$ (the quaternion group). \end{exam} The following theorem is the most celebrated use of McKay graphs (see \cite[Proposition 4]{McKay} and~\cite{Steinberg}): \begin{theorem}[McKay's theorem]\label{thrm:mckay_class} The following list describes all McKay graphs for pairs $(G, \rho)$ where $G\subset SU(2)$ is a finite group and $\rho$ is the respective $2$-dimensional representation of $G$. \end{theorem} \begin{center} \begin{tabular}{ !{\color{blue}\vrule width 2pt} c|c !{\color{blue}\vrule width 2pt} } \specialrule{.2em}{.0em}{.0em} \xrowht{20pt} Affine Dynkin diagram & Group $G$ \\ \specialrule{.2em}{.0em}{.0em} & \\$\tilde A_n$, $n\geq 0$ &cyclic\\ $$ \begin{tikzcd}[arrows=-] &&\bigstar\arrow[drr]&&\\ \circled{1}\arrow[rru]\arrow[r] & \circled{1}\arrow[r] &\cdots \arrow[r] & \circled{1} \arrow[r] & \circled{1} \end{tikzcd} $$ &$\Z/(n+1)\Z$ \\ & size: $n+1$\\ \hline &\\ $\tilde D_n$ , $n\geq 4$ & binary dihedral \\ $$ \begin{tikzcd}[arrows=-] \bigstar\arrow[rd]&&&& \circled{1}\\ & \circled{2}\arrow[r] &\cdots \arrow[r] & \circled{2} \arrow[ru]\arrow[rd] & \\ \circled{1}\arrow[ru]&&&&\circled{1} \end{tikzcd} $$ & $\mathrm{B}\mathrm{Dih}_{n-2}$ \\ & size: $4(n-2)$ \\ \hline &\\ $\tilde E_6$ & binary tetrahedral \\ $$ \begin{tikzcd}[arrows=-] &&\bigstar\arrow[d]&&\\ && \circled{2}\arrow[d]&&\\ \circled{1}\arrow[r] & \circled{2}\arrow[r] &\circled{3} \arrow[r] & \circled{2} \arrow[r] & \circled{1} \end{tikzcd} $$ &$\mathrm{B}{\bf T}$ \\ & size: $24$ \\ \hline & \\ $\tilde E_7$ & binary octahedral\\ $$ \begin{tikzcd}[sep=small,arrows=-] &&& \circled{2}\arrow[d]&&&\\ \bigstar\arrow[r] & \circled{2}\arrow[r] & \circled{3}\arrow[r] &\circled{4} \arrow[r] & \circled{3} \arrow[r] & \circled{2}\arrow[r] & \circled{1} \end{tikzcd} $$ & $\mathrm{B}{\bf O}$ \\ & size: $48$ \\ \hline &\\ $\tilde E_8$ & binary icosahedral\\ $$ \begin{tikzcd}[sep=small,arrows=-] &&&&& \circled{3}\arrow[d]&&\\ \bigstar\arrow[r]&\circled{2}\arrow[r]&\circled{3}\arrow[r]&\circled{4}\arrow[r] & \circled{5}\arrow[r] & \circled{6}\arrow[r] & \circled{4} \arrow[r] & \circled{2} \end{tikzcd} $$ & $\mathrm{B}{\bf I}$ \\ & size: $120$ \\ \specialrule{.2em}{.0em}{.0em} \end{tabular} \end{center} The proof of Theorem \ref{thrm:mckay_class} relies on the classification of all finite undirected connected simply-laced graphs $\Gamma$ with spectral radius $2$. The classification of such graphs states that they must be affine Dynkin diagrams of types $A$, $D$ or $E$, {which was proved by Smith in \cite{Smith} (cf. \cite[Proposition~4]{McKay})}. \begin{prop}\label{prop:McKay_classification} Let $G$ be a finite group and $\rho$ be its self-dual faithful representation (so $\Gamma(G, \rho)$ is connected and undirected). Assume $\dim \rho = 2$. Then either $G\subset SU(2)$ (hence $G$ appears in the list of Theorem \ref{thrm:mckay_class} and $\Gamma(G, \rho)$ is of the form above), or $G=\mathrm{Dih}_n$ and $\rho$ is the complexification of the tautological $2$-dimensional representation of $\mathrm{Dih}_n$. In the latter case, $\Gamma(G, \rho)$ is drawn below. \end{prop} \begin{center} \begin{tabular}{ !{\color{blue}\vrule width 2pt} c|c|c !{\color{blue}\vrule width 2pt} } \specialrule{.2em}{.0em}{.0em} \xrowht{20pt} parity of $n$ & {\small McKay graph for $\mathrm{Dih}_n$, tautological $\rho$, $\dim(\rho)=2$} & number of vertices\\ \specialrule{.2em}{.0em}{.0em} $n$ even & $$ \begin{tikzcd}[arrows=-] \bigstar\arrow[rd]&&&&\circled{1}\\ & \circled{2}\arrow[r] &\cdots \arrow[r] & \circled{2}\arrow[ru]\arrow[rd] & \\ \circled{1}\arrow[ru]&&&&\circled{1} \end{tikzcd} $$ &$\frac{n}{2}+3$ \\ \hline $n$ odd & $$ \begin{tikzcd}[arrows=-] \bigstar\arrow[rd]&&&&{}\\ & \circled{2}\arrow[r] &\cdots \arrow[r] & \circled{2} \arrow[loop right]{r} & \\ \circled{1}\arrow[ru]&&&&{} \end{tikzcd} $$ &$\frac{n+3}{2}$\\ \specialrule{.2em}{.0em}{.0em} \end{tabular} \end{center} \begin{proof} Since $\rho$ is self dual, it either has a symplectic $G$-invariant form (i.e. $\rho$ is of quaternionic type) or a symmetric $G$-invariant form (i.e. $\rho$ is of real type). In the former case, $G \subset SL(2)\cap U(2) =SU(2)$ and we are in the situation of Theorem~\ref{thrm:mckay_class}. In the latter case, the representation $(\rho, V)$ is of real type, the corresponding $2$-dimensional real representation $(\rho_{\mathbb R}, V_{\mathbb R})$ satisfies: $\rho \cong \C\otimes_{\mathbb R}\rho_{\mathbb R}$, where $\rho_{\mathbb R}$ is a faithful $2$-dimensional representation of $G$ over $\mathbb R$. Hence $G\subset {\rm Dih}_n$ for some $n\geq 1$. But in that case $G$ it either cyclic (and then we are again in the situation of Theorem \ref{thrm:mckay_class}) or $G$ is dihedral. This completes the proof of the proposition. \end{proof} \subsection{McKay graphs and characters} Let $\Gamma \coloneqq \Gamma(G, \rho)$ be the McKay graph for a finite group $G$ and a representation $\rho$ of $G$. \begin{lemma}\label{lem:trace} Let $k\geq 1$. We have: $$ \dim \Hom_G(\rho^{\otimes k}, \C[G]^{adj}) = \sum_{g \in G//G} \chi_\rho(g)^k = tr(A^k_{\Gamma}) = \abs{\{\text{circuits of length } k \text{ in } \Gamma \}}. $$ \end{lemma} \begin{proof} The eigenvalues of the matrix $A_{\Gamma}$ are precisely $\chi_\rho(g)$ for $g \in G//G$ (see Proposition \ref{prop:spectra_adj_matrix}), so the sum of eigenvalues of $A^k_{\Gamma}$ is $\sum_{g \in G//G} \chi_\rho(g)^k $, which proves the middle equality. The right equality holds for any graph $\Gamma$ and is obvious. It remains to prove that $\dim \Hom_G(\rho^{\otimes k}, \C[G]^{adj}) = tr(A^k_{\Gamma})$. Indeed, we have: \begin{align*} \dim \Hom_G(\rho^{\otimes k}, \C[G]^{adj}) &= \dim \Hom_G(\rho^{\otimes k}, \bigoplus_{\mu \in \mathrm{Irr}(G)} \mu^* \otimes \mu) \\ &= \sum_{\mu \in \mathrm{Irr}(G)} \dim \Hom_G(\rho^{\otimes k}\otimes \mu, \mu) \end{align*} In the right hand side, each summand $\dim \Hom_G(\rho^{\otimes k}\otimes \mu, \mu)$ is precisely the diagonal entry in $A^k_{\Gamma}$ corresponding to $\mu \in \mathrm{Irr}(G)$, so $$\sum_{\mu \in \mathrm{Irr}(G)} \dim \Hom_G(\rho^{\otimes k}\otimes \mu, \mu)= tr(A^k_{\Gamma})$$ as required. \end{proof} \begin{coro}\label{cor:trace} Assume $\Gamma$ is undirected and loop-less. Then $$\dim \Hom_G(\rho^{\otimes 2}, \C[G]^{adj}) =\sum_{g \in G//G} \chi_\rho(g)^2 = 2\abs{\{\text{undirected edges in } \Gamma\}}.$$ \end{coro} \subsection{Bipartite McKay graphs} \begin{lemma}\label{lem:bipartite_eigen} Let $\Gamma$ be a bipartite graph with adjacency matrix $A_{\Gamma}$. Then for each eigenvalue $\lambda$ of $A_{\Gamma}$, $-\lambda$ is also an eigenvalue of $A_{\Gamma}$. \end{lemma} \begin{proof} Let $X(\Gamma) = X_0 \sqcup X_1$ be the bipartition of the set of vertices, such that $$\forall i\in \{1,2\}, \; \forall x, y \in X_i, \; x\notin \mathtt{N}(y).$$ Let $f: X(\Gamma) \to \C$ be the eigenvector of $A_{\Gamma}$ with eigenvalue $\lambda$. Then $$\forall x\in X(\Gamma), \; \lambda f(x) = \sum_{y \in \mathtt{N}(x)} f(y).$$ Now define a new function $\tilde{f}: X(\Gamma) \to \C$ by setting $$\forall i\in \{1,2\}, \; \forall x\in X_i, \; \tilde{f}(x) \coloneqq (-1)^i f(x).$$ Then for any $x\in X_i$, we have: $$-\lambda \tilde{f}(x) = -\lambda (-1)^i f(x) = \sum_{y \in \mathtt{N}(x)}(-1)^{i+1} f(y) = \sum_{y \in \mathtt{N}(x)} \tilde{f}(y),$$ making $\tilde{f}$ an eigenvector of $A_{\Gamma}$ with eigenvalue $-\lambda$. \end{proof} Let $\Gamma \coloneqq \Gamma(G, \rho)$ be the McKay graph for a finite group $G$ and a representation $\rho$ of~$G$. \begin{lemma}\label{lem:bipartite_center} Assume $\rho$ is irreducible and faithful. Then the graph $\Gamma= \Gamma(G, \rho)$ is bipartite if and only if $C_2 \subset Z(G)$. \end{lemma} \begin{proof} $[\mathbf{\Leftarrow}]$: Assume $C_2 \subset Z(G)$, and let $z\in C_2\subset Z(G)$, $z\neq 1_G $. Then the vertices in $\Gamma$ can be partitioned into two disjoint subsets, according to the eigenvalue by which $z$ acts on the given irreducible representation of $G$. Since $\rho$ is faithful and irreducible, $\rho(z) =-\id$. So clearly, there are no edges in $\Gamma$ between vertices $\lambda, \mu \in \mathrm{Irr}(G)$ such that $\lambda(z) = \mu(z)$. Hence $\Gamma$ is bipartite. $[\mathbf{\Rightarrow}]$: Assume $\Gamma$ is bipartite. By Lemma \ref{lem:bipartite_eigen}, for each eigenvalue $\lambda$ of $A_{\Gamma}$, we also have an eigenvalue~$-\lambda$. Next, the eigenvalues of $A_{\Gamma}$ are precisely $\chi_\rho(g)$ by Proposition \ref{prop:spectra_adj_matrix}, so there exists $z \in G$ with $$\chi_\rho(z) = -\chi_{\rho}(1_G) = - \dim \rho$$ Since $z \in G$ has finite order, $\rho(z)$ is a diagonalizable operator whose eigenvalues are all roots of unity. We have $tr(\rho(z)) = - \dim \rho$ and hence $\rho(z) = -\id$. Faithfulness of $\rho$ now implies that $z \in Z(G)$ and $z^2 = 1_G$. Hence $C_2 \subset Z(G)$ as required. \end{proof} \begin{lemma}\label{lem:faithful_center} Assume $\rho$ is irreducible and faithful, and that $\rho^* \cong \rho$. Then $Z(G) \subset C_2 $. \end{lemma} \begin{proof} By Schur's lemma, $\rho$ defines a character of the center $$\lambda:Z(G) \to \C^{\times}, \;\, z\mapsto \lambda(z),$$ where $\rho(z) = \lambda(z)\id$. Since $\rho^* \cong \rho$, we have: $\triv \subset \rho \otimes \rho^* \cong \rho^{\otimes 2}$ and on this space $z \in Z(G)$ acts by $\lambda^2(z)\id$. So $\lambda(z)^2 = 1$ and thus $\lambda(z)=\pm 1$. Now, since $\rho$ is faithful, the map $\lambda: Z(G) \to \C$ is injective, hence $Z(G) \subset C_2 $. \end{proof} \begin{rema} {These statements relate to the fact that the group of central characters $U\coloneqq \Hom(Z(G), \C^{\times})$ defines a universal grading on the tensor category $\Rep(G)$, and thus means that $\Gamma(G, \rho)$ is a $\abs{Z(G)}$-partite graph for any $\rho \in \Rep(G)$. Furthermore, if $\rho$ is irreducible and $\zeta_{\rho} \in U$ is the central character corresponding to $\rho$, every closed walk in $\Gamma(G, \rho)$ has length divisible by the order of $\zeta_{\rho}$ in $U$, which implies the statement of Lemma \ref{lem:faithful_center}.} \end{rema} Recall that by Lemma \ref{lem:undirected}, $\rho^* \cong \rho$ if and only if $\Gamma$ is undirected, and by Lemma~\ref{lem:connectivity}, $\rho$ is faithful if and only if $\Gamma$ is connected. Using Lemmas \ref{lem:bipartite_center}, \ref{lem:faithful_center}, we conclude: \begin{coro}\label{cor:bipartite_center_Z_2} Assume $\rho$ is irreducible and $\Gamma = \Gamma(G, \rho)$ is an undirected and connected graph. Then $\Gamma$ is bipartite if and only if $Z(G) = C_2 $. \end{coro} \section{Trees}\label{sec:trees} \begin{theorem}\label{thrm:main} Let $\Gamma \coloneqq \Gamma(G, \rho)$ be the McKay graph for a finite group $G$ and a representation $\rho$ of~$G$. Assume $\Gamma$ is an (undirected) tree. Then $\rho$ is a faithful irreducible representation of $G$, and one of the following conditions is satisfied: \begin{itemize} \item $\dim \rho =2$, and the graph $\Gamma$ is an affine Dynkin diagram as in Proposition \ref{prop:McKay_classification}; in that case $(G, \rho)$ belongs to the list appearing in Theorem \ref{thrm:mckay_class}, or $G=Dih_{2n}$ and $\rho$ is its natural $2$-dimensional representation. \item $G$ is an extra special $2$-group of order $2^{1+2n}$ ($n\geq 0$), with $\rho$ its unique irreducible $2^n$-dimensional representation on which the center of $G$ acts non-trivially; in that case $\Gamma$ is a ``hedgehog'' as in Example \ref{ex:extra_special}, whose number of spines (leaves) is $4^n$. \end{itemize} \end{theorem} \begin{proof} First of all, since $\Gamma$ is undirected and connected, we have, by Lemmas \ref{lem:connectivity} and~\ref{lem:undirected}, that $\rho$ is a self-dual, faithful representation of $G$. Next, the condition that $\Gamma$ is a tree implies that $$\abs{\{\text{undirected edges in } \Gamma\}} = \abs{\mathrm{Irr}(G)}-1 = \abs{G//G} -1.$$ By Corollary \ref{cor:trace} we have: \begin{equation}\label{eq:sq_char} \dim \Hom_G(\rho^{\otimes 2}, \C[G]^{adj}) = tr(A_{\Gamma}^{\otimes 2})= 2(\abs{G//G} -1). \end{equation} Now, $$\C[G]^{adj} = \bigoplus_{[g] \in G//G} \Span\{g |g\in [g]\} \cong \bigoplus_{[g] \in G//G} \C[G/C(g)] \cong \bigoplus_{[g] \in G//G} \C\uparrow^G_{C(g)}, $$ where $C(g)$ is the centralizer of an element $g$ in the conjugacy class $[g]$ (the isomorphisms depend on the choices of representatives $g\in [g]$, of course). Thus we have: \begin{align}\label{eq:sum_dim_end} \nonumber&2(\abs{G//G} -1) = \dim \Hom_G(\rho^{\otimes 2}, \C[G]^{adj}) = \sum_{[g] \in G//G} \dim \Hom_G(\rho^{\otimes 2}, \C\uparrow^G_{C(g)} ) \\ &=\sum_{[g] \in G//G} \dim \Hom_{C(g)}\left(\rho^{\otimes 2} \downarrow_{C(g)}, \triv\right)= \sum_{[g] \in G//G} \dim \End_{C(g)}(\rho \downarrow_{C(g)}) \end{align} (the last equality follows from the fact that $\rho$ is self-dual). Let us compute $ \dim \End_{C(g)}(\rho \downarrow_{C(g)})$. This value is clearly at least $1$, and we will show that this is precisely $2$ when $g\notin Z(G)$. Assume $\rho$ is reducible as a $G$-representation. Hence it is reducible as a $C(g)$-representation for each $g\in G$. This implies: $$\dim \End_{C(g)}(\rho \downarrow_{C(g)})\geq 2$$ for all $g\in G$ and so $$\sum_{[g] \in G//G} \dim \End_{C(g)}(\rho \downarrow_{C(g)}) \geq 2\abs{G//G} >2(\abs{G//G} -1)$$ which is a contradiction. Hence $\rho$ is irreducible. For $g\in Z(G)$ we have: $C(g)=G$ so clearly $ \dim \End_{C(g)}(\rho \downarrow_{C(g)})=1$ in that case. Now let $g\in G \setminus Z(G)$. The operator $\rho(g)$ is an intertwining operator on the $C(g)$-representation $\rho \downarrow_{C(g)}$ and hence acts by scalar on any simple $C(g)$-summand of $\rho \downarrow_{C(g)}$. Note that $\rho(g)$ cannot be a scalar endomorphism: indeed, if that were the case, $\rho(g)$ would commute with $\rho(h)$ for any $g\in G$. Since $\rho$ is faithful, this would imply that $g \in Z(G)$, contrary to our assumption on $g$. Hence $\rho(g)$ is not a scalar endomorphism, and so $\rho \downarrow_{C(g)}$ is not simple. Hence we have: for any $g\in G \setminus Z(G)$, $\dim \End_{C(g)}(\rho \downarrow_{C(g)}) \geq 2$. Next, by Corollary \ref{cor:bipartite_center_Z_2} we have: $Z(G) = C_2$. So by Equation \eqref{eq:sum_dim_end}, we have: $$\sum_{\substack{[g] \in G//G,\; g \notin Z(G)}} \dim \End_{C(g)}(\rho \downarrow_{C(g)}) = 2(\abs{G//G} -2).$$ Notice that the left hand side has $(\abs{G//G} -2)$ summands, so that the average value of $\dim \End_{C(g)}(\rho \downarrow_{C(g)}) $ is $2$. But since we showed that the minimal value is also $2$, we conclude that $\dim \End_{C(g)}(\rho \downarrow_{C(g)}) =2$ for any $g\notin Z(G)$, i.e. the representation $\rho \downarrow_{C(g)}$ has length~$2$. If $C(g)$ is abelian for some $g\notin Z(G)$, then $\rho \downarrow_{C(g)}$ is a direct sum of two $1$-dimensional representations and the statement of the theorem is proved. If $G$ itself is abelian, then $\dim \rho = 1$ and $\Gamma$ is tree only if $G= C_2$, $\rho = \sgn$; again, the statement of the theorem is then proved. Thus we will assume from now on that $C(g)$ is not abelian for any $g\in G$. Since $\dim \End_{C(g)}(\rho \downarrow_{C(g)}) =2$, for any $g\notin Z(G)$, $\rho(g)$ is a diagonalizable endomorphism with precisely $2$ distinct eigenvalues. Furthermore, since $\rho \cong \rho^*$ as $G$-representations, we have: for each eigenvalue $z$ of $\rho(g)$, its complex conjugate $\bar{z}$ is also an eigenvalue of $\rho(g)$ with the same multiplicity. So the set of eigenvalues of each $\rho(g), g\notin Z(G)$ is either $\{\pm 1\}$ or $\{z, \bar{z}\}$ where $z$ is a root of unity of order $\abs{G}$, $z\neq \pm 1$. Note that the second option can occur only if $\dim \rho$ is even. Assume {that the eigenvalues of $\rho(g)$ belong to $\{\pm 1\}$ for all $g\in G$}. This implies that each {(non-trivial)} element in $G$ has order $2$. In particular, $$\forall g, h\in G, \, ghg^{-1}h^{-1} = ghgh=1_G \; \Rightarrow \; gh=hg$$ so $G$ is abelian. But that contradicts our assumption. So there exists $g \in G$ such that $g^2 \neq 1_G$, i.e. the eigenvalues of $\rho(g)$ are $z_1 \neq z_2$ (these are roots of unity, and $z_1 =\bar{z_2} { \notin \{\pm 1\}}$). Let $V_{z_k}$ denote the eigenspace of $\rho(g)$ corresponding to the eigenvalue $z_k$, $k=1,2$; then $V_{z_1} \oplus V_{z_2}$ is the entire space underlying the representation $\rho$, and $\dim V_{z_1} = \dim V_{z_2}$. Let $h\in C(g)$. The operators $\rho(h), \rho(g)$ commute so they are simultaneously diagonalizable ($\rho(h)$ also having at most $2$ distinct eigenvalues). We will say that $h$ is {\it aligned} with $g$ if the restriction of $\rho(h)$ to each of the subspaces $V_{z_k}, k=1,2$ is a scalar endomorphism. The set of elements $h\in C(g)$ aligned with $g$ clearly forms an abelian subgroup. Since we assumed that the group $C(g)$ is itself not abelian, we can find $h \in C(g)$ which is not aligned with $g$. We have: $h\notin Z(G)$, so we denote by $t_1 \neq t_2$ the distinct eigenvalues of $\rho(h)$. Since $h$ is not aligned with $g$, the eigenvalues of $\rho(gh)$ would be $\{t_j z_k |k, j\in \{1,2\}\}$ or at least $3$ of these products. {Since $\rho(gh)$ also has at most $2$ distinct eigenvalues, this} implies that in at least one of the pairs $(t_1 z_1, t_2 z_2)$, $(t_1 z_2, t_2 z_1)$ the elements coincide. {Without loss of generality, let us assume that $t_1z_1 = t_2z_2 = \bar{t_1}\bar{z_1}$. So the eigenvalues of $\rho(gh)$ are either $\{t_1z_1, t_1z_2\}$ or $\{t_1z_1, t_2z_1\}$. Then $$ (t_1 z_1)^2= t_1 z_1 t_2 z_2 =\abs{t_1}^2 \abs{z_1}^2 = 1 .$$ So $t_1z_1 = \pm 1$ (implying $t_1 = \pm z_2$) and the eigenvalues of $\rho(gh)$ must be $\pm 1$. Thus at least one of the following equalities holds: $ z_2^2 = \pm t_1 z_2 = \pm 1$ or $z_1^2 = \pm t_2 z_1 = \pm 1$, any of which implies} $z_1, z_2 \in \{\pm i\}$. So we see that for every $g\in G$, the eigenvalues of $\rho(g)$ are either $\{\pm i\}$ or a subset of $\{\pm 1\}$. In particular, $\rho(g)^2 = \pm \id$ for each $g\in G$, so $G/Z(G)$ is a group {whose elements all square to identity}. {Hence $G/Z(G)$ is} of the form $\mathbb{F}_2^m$ (an elementary abelian $2$-group). Since $Z(G)=C_2$, we conclude that $G$ is an extra special $2$-group, $m$ is even and $\rho$ is the unique irreducible representation of $G$ of dimension greater than $1$ (see Example~\ref{ex:extra_special}). This concludes the proof of the theorem. \end{proof} \section{Forests}\label{sec:forests} In this section we investigate the case of an undirected forest graph, i.e. a disjoint union of undirected trees. \subsection{Classification of McKay forests} \begin{prop}\label{prop:forest} Let $\Gamma \coloneqq \Gamma(G, \rho)$ be the McKay graph for a finite group $G$ and an representation $\rho$ of $G$. Assume $\Gamma$ is an (undirected) forest. Then $\rho$ is a irreducible, self-dual representation. \end{prop} \begin{proof} Let $N {\coloneqq } \Ker(\rho) \vartriangleleft G$ and let $K$ be the number of connected components of $\Gamma$. By Lemma~\ref{lem:connected_comp_Browne}, we have: $K$ is the number of $G$-conjugacy classes in $N$. The principal component $\Gamma_{\triv} = \Gamma(G/N, \rho)$ is a tree, so Theorem \ref{thrm:main} shows that $\rho$ is a self-dual irreducible representation of $G/N$. Hence $\rho$ possesses the same properties when considered as a $G$-representation, which proves the first part of the statement. \end{proof} \begin{theorem}\label{thrm:forest} Let $\Gamma \coloneqq \Gamma(G, \rho)$ be the McKay graph for a finite group $G$ and a representation $\rho$ of $G$. Let $N\coloneqq \Ker(\rho)$. Assume $\Gamma$ is an undirected forest. Then we have: \begin{enumerate} \item All the connected components of $\Gamma$ are of one of the forms described in Theorem \ref{thrm:main}. \item If one of the components is a hedgehog with $4^n$ spines for ${n\neq 1}$, then all the components of $\Gamma$ are of isomorphic to each other ({in particular}, they are isomorphic hedgehogs). \end{enumerate} \end{theorem} \begin{rema} For ${n=1}$, the hedgehog with $4$ spines is the affine Dynkin diagram $\widetilde{D}_4$. \end{rema} \begin{rema} In particular, if one of the components is an affine Dynkin diagram of types $D$ of $E$, the remaining components are also affine Dynkin diagrams of types $D$ or $E$. They do not have to be isomorphic to each other, as we will show in {the examples of Section~\ref{ssec:forest_examples}}. However, the theorem above states that the size of the dihedral or binary polyhedral group corresponding to the principal component (that is, $G/N$) will be divisible by the sizes of the dihedral or binary polyhedral groups corresponding to other connected components. For instance, if the principal component is of type $\widetilde{E}_6$, then {any connected component in this graph is either of type} $\widetilde{E}_6$ or {of type} $\widetilde{D}_4$. \end{rema} { For the proof, we need the following standard lemma: \begin{lemma}\label{lem:graph_aux} Given a tree $\Gamma$, if {any two leaves have a common neighbor} then $\Gamma$ is a hedgehog. \end{lemma} } \begin{proof}[Proof of Theorem \ref{thrm:forest}] The principal component $\Gamma_{\triv}$ of $\Gamma$ is a tree, and a McKay graph in its own right: $\Gamma_{\triv} = \Gamma(G/N, \rho)$. Hence it is isomorphic one of the graphs given by Theorem \ref{thrm:main}. Consider a connected component $\Gamma'$ of $\Gamma$ corresponding to some $T\in \mathrm{Irr}(N)//G$. Let $s$ be the dimension of any representative of $T$. By Lemma \ref{lem:conn_comp_sum_of_sq} we have: \begin{equation}\label{eq:sum_squares_conn_comp} |T|s^2\abs{G/N} = \sum_{\mu \in X(\Gamma')}(\dim \mu)^2. \end{equation} We will now consider the different possibilities for $\Gamma_{\triv}$. {\bf Case when $\Gamma_{\triv}$ is a ``hedgehog'' with ${4}^n$ spines, $n\geq 0$}: in that case, $\dim \rho = 2^n$ {and $|G/N|=2^{2n+1}$. The tree $\Gamma'$ is not a singleton, so} for each leaf $\tau$ in $\Gamma'$, we have a single vertex $\mu$ connected to it. Hence $$ \dim\mu = \dim \rho \cdot \dim\tau = 2^n \cdot \dim\tau.$$ Let $a$ be the multiplicity of any representative of $T$ in $\tau \downarrow_{N}$: then $\tau \downarrow_{N} = \bigoplus_{\sigma\in T} \sigma^{\oplus a}$ so $\dim\tau = a|T|s$. Hence \begin{align*} (\dim \tau)^2 + (\dim\mu)^2 &= (\dim \tau)^2 (1+2^{2n}) = |T|^2 s^2 a^2(1+2^{2n})\leq |T|s^2\abs{G/N} \\ &= |T|s^2 2^{1+2n} = |T|s^2 2\cdot 2^{2n}. \end{align*} { Thus $a^2|T| {\leq \frac{2\cdot 2^{2n}}{1+2^{2n}}} <2$ and so $a=|T|=1$, which implies $\dim\tau = s$, {$\dim \mu=2^n$}. So we have: \begin{enumerate}[label=(\roman*)] \item\label{itm:conn_comp_1} All leaves in $\Gamma'$ have dimension $s$. \item\label{itm:conn_comp_2} {Any vertex $ \nu$ which is connected to a leaf has dimension $2^n s$.} \end{enumerate} } {This, together with Equation \eqref{eq:sum_squares_conn_comp} implies that either there a unique such vertex $\nu$, or $\Gamma'$ is the tree with $2$ vertices. In the former case,} all the leaves in $\Gamma'$ are connected to this vertex $\nu$. Hence {by Lemma \ref{lem:graph_aux}, this implies that $\Gamma'$ is a hedgehog. It now follows from \eqref{eq:sum_squares_conn_comp} and from \ref{itm:conn_comp_1}, \ref{itm:conn_comp_2} that the hedgehog has precisely $4^n$ spines, and it is isomorphic to the principal component $\Gamma_{\triv}$.} This shows that when $G/N$ is an extra special $2$-group, all the connected components of $\Gamma$ are isomorphic to each other. {\bf Case when $\Gamma_{\triv}$ is an affine Dynkin diagram of types $\tilde{D}, \tilde{E}$}: in that case $\dim \rho = 2$. {Recall that $2$ is an eigenvalue of $A_{\Gamma}$ and there exists a corresponding eigenvector with positive integer entries; this implies that} each connected component $\Gamma'$ of $\Gamma$ is a tree with the following property: $2$ is an eigenvalue of $A_{\Gamma'}$ and there exists a corresponding eigenvector with positive integer entries. Hence the spectral radius of $\Gamma'$ is $2$ and so by Smith's classification \cite{Smith} described in Section \ref{ssec:mckay_class} we have: each connected component of $\Gamma$ is isomorphic to an affine Dynkin diagram of types $\tilde{D}$ or $\tilde{E}$. In particular, it cannot be a hedgehog with ${4}^n$ spines for $n\neq 1$. \end{proof} \subsection{Examples of forests with non-isomorphic connected components}\label{ssec:forest_examples} We will now construct examples where both $G, H$ are either binary polyhedral or dihedral groups. We will consider the tautological faithful $2$-dimensional irreducible representation $\rho$ of $G\subset SL_2(\mathbb{C})$. {So in our examples, both} $\Gamma(G, \rho)$ and $\Gamma(H, \rho)$ {will be} affine Dynkin diagrams of types $D$ or $E$. \begin{exam} \mbox{} \begin{enumerate} \item {Let $n>1$.} Let $\mathrm{Dih}_{4n}$ be the group of symmetries of a regular $4n$-gon. Then $\mathrm{Dih}_{4n}$ has a subgroup $H$ of index $2$ which is isomorphic to $\mathrm{Dih}_{2n}$ (these are the symmetries preserving {a regular $2n$-gon obtained by removing half of the vertices}). Let $\rho$ be the tautological $2$-dimensional representation of $\mathrm{Dih}_{4n}$. Restricted to $H$, this gives the tautological representation of $\mathrm{Dih}_{2n}$. We obtain a McKay graph for the $2$-dimensional representation of $G'=\mathrm{Dih}_{4n} \ltimes {C}_3$ coming from $\rho$ {satisfying} $$\Gamma(G', \rho) \;=\; \Gamma(\mathrm{Dih}_{4n}, \rho) \,\bigsqcup\, \Gamma(\mathrm{Dih}_{2n}, \rho\downarrow_H).$$ Thus $\Gamma(G', \rho)$ is a {disjoint} union of $2$ non-isomorphic trees $\tilde{D}_{{4}n}$ and $\tilde{D}_{{2}n}$, where one has ${2n} + 3$ vertices and the other ${n} + 3$ vertices. A similar construction is possible for the binary dihedral groups $\mathrm{BDih}_{2n}$ and $\mathrm{BDih}_n$. \item Let $\mathrm{B}\mathbf{T}$ be the binary tetrahedral group. {Consider the subgroup $\mathrm{BDih}_2 \triangleleft \mathrm{B}\mathbf{T}$. Let $\rho$ be the tautological $2$-dimensional representation of $\mathrm{B}\mathbf{T}\subset SU(2)$. Then $\rho\downarrow_{\mathrm{BDih}_2}$ is the $2$-dimensional irreducible representation of $\mathrm{BDih}_2 \cong Q_8$.} The quotient $\quotient{\mathrm{B}\mathbf{T}}{\mathrm{BDih}_2} \cong C_3$ acts on the Klein $4$-group $\mathbb{F}_2^2$ by group automorphisms permuting transitively the order $2$ elements; the action is given by the embedding $$\quotient{\mathrm{B}\mathbf{T}}{\mathrm{BDih}_2} \cong C_3 \hookrightarrow GL_3(\mathbb{F}_2) \cong S_3.$$ We obtain a McKay graph for the $2$-dimensional representation of $G'=\mathrm{B}\mathbf{T}\ltimes \mathbb{F}_2^2$ coming from $\rho$: $$\Gamma(G', \rho) \; =\; \Gamma(\mathrm{B}\mathbf{T}, \rho) \,\bigsqcup \,\Gamma(Q_8, \rho\downarrow_{Q_8})$$ Thus $\Gamma(G', \rho)$ is a disjoint union of $2$ non-isomorphic trees $\widetilde{E}_6$ and $\widetilde{D}_4$. \item Let $\mathrm{B}\mathbf{O}$ be the binary octahedral group, and consider the subgroup $ \mathrm{B}\mathbf{T} \triangleleft \mathrm{B}\mathbf{O}$. Let $\rho$ be the tautological $2$-dimensional representation of $\mathrm{B}\mathbf{O}\subset SU(2)$. Then $\rho\downarrow_{\mathrm{B}\mathbf{T}}$ is the tautological $2$-dimensional irreducible representation of~$\mathrm{B}\mathbf{T}$. We obtain a McKay graph for the $2$-dimensional representation of $G'=\mathrm{B}\mathbf{O} \ltimes {C_3}$ coming from $\rho$: $$\Gamma(G', \rho) \;=\; \Gamma(\mathrm{B}\mathbf{O}, \rho) \,\bigsqcup \,\Gamma(\mathrm{B}\mathbf{T}, \rho\downarrow_{\mathrm{B}\mathbf{T}})$$ Thus $\Gamma(G', \rho)$ is a disjoint union of $2$ non-isomorphic trees $\widetilde{E}_7$ and $\widetilde{E}_6$. \item Let $G=\mathrm{B}\mathbf{O}$ and and consider the subgroup $\mathrm{BDih}_2 \triangleleft \mathrm{B}\mathbf{O}$. Let $\rho$ be the {tautological} $2$-dimensional representation of $\mathrm{B}\mathbf{O}\subset SU(2)$. Then $\rho\downarrow_{\mathrm{BDih}_2}$ is the tautological $2$-dimensional irreducible representation of $\mathrm{BDih}_2 \cong Q_8 $. Then $\quotient{\mathrm{B}\mathbf{O}}{\mathrm{BDih}_2} \cong S_3$ acts on the Klein $4$-group $\mathbb{F}_2^2$ by group automorphisms permuting transitively the order $2$ elements; the action is given by the isomorphism $$\quotient{\mathrm{B}\mathbf{O}}{\mathrm{BDih}_2} \cong S_3 \stackrel{\sim}{\longrightarrow} GL_3(\mathbb{F}_2) .$$ We obtain a McKay graph for the $2$-dimensional representation of $G'=\mathrm{B}\mathbf{O}\ltimes \mathbb{F}_2^2$ coming from $\rho$: $$\Gamma(G', \rho) \;=\; \Gamma(\mathrm{B}\mathbf{O}, \rho) \,\bigsqcup\, \Gamma(Q_8, \rho\downarrow_{Q_8})$$ Thus $\Gamma(G', \rho)$ is a disjoint union of $2$ non-isomorphic trees $\widetilde{E}_7$ and $\widetilde{D}_4$. \end{enumerate} \end{exam} \bibliographystyle{mersenne-plain} \bibliography{ALCO_Entova-Aizenbud_683} \end{document}