# Tree Orbits under Permutation Group Action: Algorithm, Enumeration and Application to Viral Assembly - Mathematics > Combinatorics

Abstract: This paper uses combinatorics and group theory to answer questions about theassembly of icosahedral viral shells. Although the geometric structure of thecapsid shell is fairly well understood in terms of its constituent subunits,the assembly process is not. For the purpose of this paper, the capsid ismodeled by a polyhedron whose facets represent the monomers. The assemblyprocess is modeled by a rooted tree, the leaves representing the facets of thepolyhedron, the root representing the assembled polyhedron, and the internalvertices representing intermediate stages of assembly subsets of facets.Besides its virological motivation, the enumeration of orbits of trees underthe action of a finite group is of independent mathematical interest. If $G$ isa finite group acting on a finite set $X$, then there is a natural inducedaction of $G$ on the set $\mathcal{T} X$ of trees whose leaves are bijectivelylabeled by the elements of $X$. If $G$ acts simply on $X$, then $|X| := |X n| =n \cdot |G|$, where $n$ is the number of $G$-orbits in $X$. The basiccombinatorial results in this paper are 1 a formula for the number of orbitsof each size in the action of $G$ on $\mathcal{T} {X n}$, for every $n$, and2 a simple algorithm to find the stabilizer of a tree $\tau \in\mathcal{T} X$ in $G$ that runs in linear time and does not need memory inaddition to its input tree.

Author: Miklos Bona, Meera Sitharam, Andrew Vince

Source: https://arxiv.org/