# On the graph of induction-restriction for group-subgroup representations

Let $G$ be a finite group, and $H$ a subgroup.
Let $(V_i)_{i \in I}$ and $(W_j)_{j \in J}$ be the irreducible complex representations of $G$ and $H$ (up to isom.).

Consider the graph $\mathcal{G}(H \subset G )$ whose vertices are $\{ V_i, W_j : i \in I, j \in J \}$ such that there are $d_{ij}$ edges between $V_i$ and $W_j$ if $\langle V_i\vert_H,W_j \rangle = d_{ij}$.

Let $\mathcal{G}_0(H \subset G )$ be the connected component of the trivial representation $V_0$ (noted $\star$) of $G$.
Note that if $K \subset H$ is a normal subgroup of $G$ then $\mathcal{G}_0(H \subset G )= \mathcal{G}_0(H/K \subset G/K )$.

The graph $\mathcal{G}_0$ is $n$-supertransitive ($n$-$st$) if up to distance $n$ from $\star$ it's just a linear chain: $$\star-\circ-\circ-\circ-\circ-\circ-\circ-\circ-\circ$$ Let $st(H \subset G )$ be the integer $n$ such that the graph $\mathcal{G}_0(H \subset G )$ is $n$-$st$ but not $(n+1)$-$st$.
Note that $st(H \subset G ) \ge 1$ and $st(H \subset G )= st(H/K \subset G/K )$.

Examples: $st(\{e\} \subset \mathbb{Z}_2)=2$ and $st(\{e\} \subset G)=1$ if $G \neq \mathbb{Z}_2$.
$st(\mathbb{Z}_2 \subset D_{10})=1$ and $st(S_4 \subset S_5)=3$

Question: Is there $(H_0 \subset G_0 )$ with $st(H_0 \subset G_0 ) > 7$ ? Is $st(H \subset G )$ bounded ?

Optional questions: Is there usual names for $\mathcal{G}_0(H \subset G )$ and $st(H \subset G )$ in groups theory ? References ? Is there a program drawing $\mathcal{G}_0(H \subset G )$ and computing $st(H \subset G )$ ?

(This is just a comment with some ideas and calculations, and graphics in comments are hard.)

For $G=S_7$, $H=S_6$, the perm rep $1_H^G$ is $7$-transitive, but only 3 supertransitive. The graph is connected, so $\mathcal{G}=\mathcal{G}_0$.

The graph is a bit weird looking. All edges are single edges. $$\begin{array}{} & & && \hspace{-2ex}\circ \to \circ \to \circ \\ & & & \hspace{-2ex}\circ \to \circ \rlap{\rightarrow}^{\nearrow} & \hspace{-2ex} \circ\\ & \hspace{-2ex}\circ\to\circ \rlap{\rightarrow}_{\searrow} &\hspace{-1.5ex}\circ \to \circ \rlap{\rightarrow}^{\nearrow} & \hspace{-2ex}\circ \to \circ \rlap{\rightarrow}^{\nearrow} & \hspace{-2ex} \circ\\ \star \to \circ \to \circ \to \circ {}^{\nearrow}_{\searrow} {} && \hspace{-1.5ex}\circ \to \circ \rlap{\rightarrow}_{\searrow}^{\nearrow} & \hspace{-2ex}\circ \to \circ {}^\nearrow\\ & \hspace{-2ex}\circ \to\circ \rlap{\rightarrow}^{\nearrow} &\hspace{-1.5ex}\circ \to \circ \to &\hspace{-2ex}\circ\\ \end{array}$$

By analogy with modular representation theory, I'd call the (bipartite) graph a “decomposition matrix”, and the connected components “blocks”, with $\mathcal{G}_0$ the “principal block.” I suspect it has been studied for a long time.

It can be computed as:

mat := MatScalarProducts(Irr(h),RestrictedClassFunctions(Irr(g),h));


in GAP. I found it helpful to write out the edge relation:

edges := Filtered( Cartesian([1..Size(mat)],-[1..Size(mat)]),
ij -> not IsZero(mat[ij][-ij]));

Sticking with the definition of $st(H \leq G)$, I find that for $|G| \leq 120$, $st(H \leq G) < 3$ except:

• $st(S_2 \leq S_3) = 4$
• $st(S_3 \leq S_4) = 3$
• $st(A_4 \leq A_5) = 3$
• $st(S_4 \leq S_5) = 3$
• $st(AGL(1,5) \leq PGL(2,5)) = 3$ (S5 = PGL(2,5))

Then checking all $H\leq G$ with $[G:H] \leq 15$ we see the same sorts of groups (natural Sn, natural An, some variants of natural PGL2, natural Mathieu groups) but also some weird ones (AGL, unnnatural mathieu). Also, other than natural $S_3$, $st(H \leq G) \leq 3$.

• One could compute st(H≤G) easily from edges but I worry that the definition is not right for you, since it doesn't seem to be too related to transitivity, other than 2-transitivity. – Jack Schmidt Mar 3 '14 at 3:09
• Thank you! In analogy with $k$-transitive groups classification and Mathieu groups, perhaps $st(H \subset G) \ge 3$ iff $(H \subset G) \sim (S_{n-1} \subset S_{n})$ or $(A_{n-1} \subset A_{n})$ or finitely many others possibilities (up to $\sim$) perhaps coming from the Mathieu groups. – Sebastien Palcoux Mar 3 '14 at 11:41
• I've posted an answer (due to Dave Penneys). – Sebastien Palcoux Mar 3 '14 at 21:20

Answer (due to Dave Penneys): $st(H\subset G) \le 3$ if $[G:H]>3$.

I report here his comment :

A subgroup subfactor (of index $> 3$) can be at most $3$-supertransitive. The $4$-box space is at least 15 dimensional. This can be seen by looking at the partition planar algebras (MR2972458).

As observed by Jack Schmidt, if $st(H\subset G) > 3$ and $[G:H] \le 3$ then $(H\subset G) \sim (S_2 \subset S_3 )$ and $st(S_2 \subset S_3 ) = 4$.

By reading the pages 13-14 of the paper cited by Dave (also with this book ex. 4.2.3 p53 and prop. A.4.4 p141), we see that "for $k=1,2$ or $3$", $st(H \subset G) = k$ iff $1_H^G$ is (at least) $k$-transitive, iff $G/H_G$ is (at least) a $k$-transitive group (it's false for $k \ge 4$).

Then the classification (up to $\sim$ ) of the inclusions $(H \subset G)$ with $st(H \subset G) = 3$ is given by the classification of the $3$-transitive groups.

Classification of the $4$-transitive groups: Symmetric, Alternating and Mathieu groups only (here).

Questions: Is there a classification of the $3$-transitive groups ? A conjecture ?
Is there a table of the number of $3$-transitive groups of degree $n$ ?

• For most $n$ there are exactly two, $A_n$ and $S_n$. If $n-1$ is a prime power, then $\operatorname{PGL}(2,n-1)$ is as well. If $n-1$ is the square of a prime power, then an analogue of the Mathieu group of degree 10 exists, sometimes called $M(n)$ or $M(q^2)$ where $q=\sqrt{n-1}$. If $n\geq 5$ is odd, then every non-identity normal subgroup of a triply transitive group is triply transitive, so there has to be a simple group (so the classification of finite simple groups theoretically settles it there). Let me know if you want a table of the small exceptions (it's a bit long). – Jack Schmidt Mar 3 '14 at 21:25
• @JackSchmidt : thank you. Yes I would like a table of the exceptions and (or) a reference. I don't understand (yet) why a non-identity normal subgroup of odd index $n \ge 5$ of a $3$-$T$ group is $3$-$T$ and simple. Is there such a classification for the $2$-$T$ or the $1$-$T$ primitive groups ? – Sebastien Palcoux Mar 3 '14 at 22:40
• 3 is special in that result of Wagner (1966). For general $k$, non-identity normal subgroups are $k-1$ transitive. – Jack Schmidt Mar 4 '14 at 0:52
• I asked about triply transitive groups here: math.stackexchange.com/questions/698327/… – Jack Schmidt Mar 4 '14 at 0:53
• – Sebastien Palcoux Mar 5 '14 at 12:57