Number of edge-invariant walks in complete graph

Question

Given a complete graph $(V,E)$ with $n$ vertices $V$ and walks $p \in V^{l+1}$ of length $l$. We say the edges of walks $p$ are the multiset

$$ e_p = \{ (p_i,p_{i+1}) \mid 1 \leq i \leq l \}. $$ Also the frequency of vertex $v \in V$ in walk $p$ is $p[v] = |\{ i \mid p_i = v \}|$. The frequency of all vertices $f_p \in \mathbb{N}^n$ in walk $p$ is then given by $$ f_p = [ p[v_1], p[v_2], \dots, p[v_n] ]. $$

Now, two walks $p$ and $q$ are called edge-invariant if $f_p = f_q$ and $e_p = e_q$. How many different walks of length $l$, which are not edge-invariant, exist? More precisely, i.e., $$ max_{P \subset V^{l+1}} | \{ P \mid \forall p, q \in P: e_p \neq e_q \textrm{ or } f_p \neq f_q \textrm{ for } p \neq q \}|. $$

For example, $n = 2$, it's $4, 8, 14, 22, 32, 44, 58, 74, 92, 112, 134, 158$ for $l = 1,\dots,12$. Specifically for $l = 3$, out of the 16 possible walks, two are edge-invariant: $$ e_{[1,1,2,1]} = e_{[1,2,1,1]} \textrm{ and } e_{[2,2,1,2]} = e_{[2,1,2,2]}. $$

For $n = 3$, it's given here as $9, 27, 75, 186, 414, 840, 1578, 2784, 4662, 7476, 11556$ for $l = 1,\dots,11$.

It seems to be related to k-abelian equivalence classes, where the general problem seems to be rather difficult, but maybe the 2-abelian cases is simpler?

Answer 1

I'm not sure if the formula below is useful, but at least it can be used to numerically count edge-invariant walks classes for small $n,l$.

Let's assign a unique variable to each edge and each vertex of the complete graph, say, $x_{ij}$ to an edge $(i,j)$ and $y_i$ to a vertex $i$. Then, we assign to each edge $(i,j)$ the weight $x_{i,j}y_j$ and consider the graph adjacency matrix $A$. For example, for $n=4$ the matrix is $$A = \begin{bmatrix} x_{11}y_1 & x_{12}y_2 & x_{13}y_3 & x_{14}y_4\\ x_{21}y_1 & x_{22}y_2 & x_{23}y_3 & x_{24}y_4\\ x_{31}y_1 & x_{32}y_2 & x_{33}y_3 & x_{34}y_4\\ x_{41}y_1 & x_{42}y_2 & x_{43}y_3 & x_{44}y_4 \end{bmatrix}.$$

Then the number of classes of edge-invariant of length $l$ is given by the number of distinct monomial terms in $$[y_1,y_2,\dots,y_n]\cdot A^l\cdot [1,1,\dots,1]^T.$$

For example, for $n=2$ and $l=3$ we get the polynomial: $$x_{11}^3y_1^4 + x_{11}^2x_{12}y_1^3y_2 + x_{11}^2x_{21}y_1^3y_2 + 2x_{11}x_{12}x_{21}y_1^3y_2 + x_{11}x_{12}x_{21}y_1^2y_2^2 + x_{12}^2x_{21}y_1^2y_2^2 + x_{12}x_{21}^2y_1^2y_2^2 + x_{11}x_{12}x_{22}y_1^2y_2^2 + x_{11}x_{21}x_{22}y_1^2y_2^2 + x_{12}x_{21}x_{22}y_1^2y_2^2 + 2x_{12}x_{21}x_{22}y_1y_2^3 + x_{12}x_{22}^2y_1y_2^3 + x_{21}x_{22}^2y_1y_2^3 + x_{22}^3y_2^4,$$ where the monomials describe equivalence classes of walks (more specifically, $x$'s describe $e_p$ and $y$'s describe $f_p$) and the coefficients give the size of each class. There are $14$ distinct monomials here and only two of them have coefficient $2$, as expected.

Here is my SAGE implementation of this formula:

# generator for variables
class VariableGenerator(object): 
  def __init__(self, prefix): 
     self.__prefix = prefix 
  @cached_method 
  def __getitem__(self, key): 
     return SR.var("%s%s"%(self.__prefix,key)) 

def NumEIClasses2(n,l):
  x = VariableGenerator('x')
  y = VariableGenerator('y')

  R = PolynomialRing(QQ,[x[i] for i in range(n*n)] + [y[i] for i in range(n)])

  A = matrix([[x[n*i + j]*y[j] for j in range(n)] for i in range(n)])

  u = vector([1 for i in range(n)])
  Y = vector([y[i] for i in range(n)])

  P = R( (Y.row() * A^l * u.column())[0,0] )
  #print P    # print the resulting polynomial

  return P.hamming_weight()

For example, for $n=4$ it gives counts 16, 64, 244, 856, 2728, 7892, 20876, 51020, 116408, ...

Answer 2

I believe, I have found an asymptotic answer here.

Define our problem in terms of k-abelian equivalence classes. Two words $u$ and $v$ are said to be $k$-abelian equivalent if, for each word $x$ of length at most $k$, the number of occurrences of $x$ as a factor of $u$ is the same as for $v$. It is easy to see the correspondence between words and walks (used in the question), and the subwords of length 1 ($f_p$) and length ($e_p$). Thus, our problem is to find the number of 2-abelian equivalence classes with length $l$ and alphabet size $n$.

In the mentioned paper (Theorem 5.1), it is shown that the number of $k$-abelian equivalence classes is asymtotically equal to $C l^{n^{k}(n-1)}$, where $C$ is a rational number dependent on $k$ and $n$.