Central limit theorem for $U$-statistics of tuples of vertex labels on a complete graph

In a complete graph with vertices $1,2, \ldots, n$, the vertices $2,3, \ldots, n$ are provided with independent random labels taking values in the finite set ${\mathcal A}_N$. Consider the set of all chains of $s$ adjacent edges, each of which leaves vertex $1$ and does not pass through the same vertex twice. Each chain corresponds to an $s$-tuple of random labels of the passed vertices. In this paper, we consider the $U$-statistics $U_k (s)$ with a kernel depending on the $k$ of such $s$-tuples. The number $k \ge 2$ is considered to be fixed, but $s \ge 1 $ can change. It has been proved that a sufficient condition for the asymptotic normality of $U_k (s)$ (under ordinary standardization) is a condition of the form $\mathbf{D} U_k(s) \ge C n^{2 (ks-1) + \varkappa},$ where $ C, \varkappa> 0.$