Speaker
Prof.
zhicheng gao
(carleton university)
Description
Let $(\Gamma,+)$ be a finite group. An $m$-composition over $\Gamma$ is an $m$-tuple $(g_1,g_2,\ldots,g_m)$ over $\Gamma$. It is called an $m$-composition of $g$ if
$\sum_{j=1}^m g_j = g$. A composition $(g_j)$ over $\Gamma$ is called locally restricted if there is a positive integer $\sigma$
such that any subsequence of $(g_j)$ of length $\sigma$ satisfies certain restrictions. Locally restricted compositions over $\Gamma$ can be modeled using walks in a de Bruijin graph.
The de Bruijin graph over $\Gamma$ with span$\sigma$, denoted by $B(\Gamma;\sigma)$, is a digraph whose vertices are $\sigma$-tuples such that there is an arc from ${\bf u}:=({\bf u}(1), {\bf u}(2),\ldots,{\bf u}(\sigma))$ to ${\bf v}:=({\bf v}(1),{\bf v}(2),\ldots,{\bf v}(\sigma))$
if ${\bf v}(j)={\bf u}(j+1)$, $1\le j\le \sigma-1$. Let $D$ be a subgraph of $B(S;\sigma)$. We associate with each directed walk ${\bf v}_1,{\bf v}_2,\ldots,{\bf v}_k$ in $B(\Gamma;\sigma)$ a composition
${\bf c}=({\bf v}_1(1),\ldots,{\bf v}_1(\sigma),{\bf v}_2(\sigma),{\bf v}_k(\sigma))$. That is, ${\bf c}$ is obtained from the walk by appending the last components of the subsequent vertices in the walk to the initial vertex of the walk.
We denote this set of compositions by ${\cal C}(D)$.
To keep track of the net sum of a composition in ${\cal C}(D)$, we make use of the derived graph of the voltage graph $(D,\alpha)$, where the voltage of the arc $({\bf u},{\bf v})$
is given by $\alpha({\bf u},{\bf v})={\bf v}(\sigma)$. Let $D'$ denote the derived graph of $(D,\alpha)$. That is, the vertex set of $D'$ is $V(D)\times \Gamma$, and there is an arc
from $({\bf u},g)$ to $({\bf v},h)$ if and only if $({\bf u},{\bf v})$ is an arc in $D$ and $h=g+{\bf v}(\sigma)$. Let $\cal S$ be the set of vertices in $D'$ such that the second component is equal to
the sum of the parts of the first component.
It is easy to see that, for $m\ge \sigma$, an $m$-composition of $g$ in ${\cal C}(D)$ corresponds to a walk
in $D'$ from ${\cal S}$ to a vertex whose second component is $g$. Fix an ordering of the vertices of $D'$ and let $T$ denote the corresponding adjacency (transfer) matrix of $D'$. That is, $T(i,j)$ is equal to 1 if there is an arc from ${\bf v}_i$ to ${\bf v}_j$, and zero otherwise.
Let $\vec s$ denote the $\{0,1\}$ row vector such that its $i$th component is equal to 1 if and only if the corresponding vertex belongs to ${\cal S}$.
Let ${\vec f}_g$ denote the $\{0,1\}$ column vector such that its $j$th component is equal to 1 if and only if the corresponding vertex is of the form $(*,g)$. Then, for $m\ge \sigma$, the number of $m$-compositions of $g$ in ${\cal C}(D)$ is equal to ${\vec s}M^{m-\sigma}{\vec f}_g$.
In this talk, we present some asymptotic results for the number of $m$-compositions, as $m\to \infty$, associated with some digraphs $D$ and some finite group $\Gamma$. It will also be shown that the distribution of the number of occurrences of a given subword in a random locally restricted $m$-composition is asymptotically normal with mean and variance proportional to $m$. These results extend previous results on compositions over a finite abelian group. The basic tools for deriving these results are covering graphs of de Bruijn graphs, Perron-Frobenius theorem, and analytic combinatorics.
Primary author
Prof.
zhicheng gao
(carleton university)
Co-author
Mr
Andrew MacFie
(carleton university)
