A combinatorial view on star moments of regular directed graphs and trees

Abstract

We investigate the method of moments for $d$-regular digraphs and the limiting $d$-regular directed tree $T_d$ as the number of vertices tends to infinity, in the same spirit as McKay (Linear Algebra Appl., 1981) for the undirected setting. In particular, we provide a combinatorial derivation of the formula for the star moments (from a root vertex $o\in T_d$) $$M_d(w):=\sum _{\begin{array}{c}{v}_0,v_1\dots ,v_{k-1},v_k\in T_d\\ v_0=v_k=o\end{array}}{A}^{w_1}(v_0,v_1)A^{w_2}(v_1,v_2)\cdots A^{w_k}(v_{k-1},v_k)$$ with $A$ the adjacency matrix of $T_d$, where $w:=w_1\cdots w_k$ is any word on the alphabet $\{1,\ast \}$ and $A^{\ast }$ is the adjoint matrix of $A$. Our analysis highlights a connection between the non-zero summands of $M_d(w)$ and the non-crossing partitions of $\{1,\dots ,k\}$ which are in some sense compatible with $w$.

12 pages, 2 figures