# Number of edge-invariant walks in complete graph

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?

• What do you mean by complete directed graph? Tournament? Next, what is "edge invariant" - a binary relation on pairs? Then what does "how many edge-invariant paths" mean? Apr 10, 2019 at 14:30
• @FedorPetrov Sorry, I meant simply a complete graph (with edges from each vertices to any other) and not a tournament. I also clarified the edge-invariant property.
– Jiro
Apr 10, 2019 at 14:55
• @MaxAlekseyev oh yes, I'm sorry, it should be trails not paths. I will correct this
– Jiro
Apr 10, 2019 at 15:20
• @MaxAlekseyev In fact, it's even walks
– Jiro
Apr 10, 2019 at 15:27
• @MaxAlekseyev Thanks for the clarification. $e_p$ are multisets.
– Jiro
Apr 10, 2019 at 15:31

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, ...

• that's certainly very helpful! Also I can confirm the solutions to $n=4$.
– Jiro
Apr 10, 2019 at 22:16
• Although, ideally I would prefer a bit more closed Form solution. I had the impression that the generating functions for this problem are rather compact, although I don't know exactly how to get there.
– Jiro
Apr 10, 2019 at 22:24
• @SebastianSchlecht: I doubt there is a simple general formula. But for a fixed $n$, it seems to be a polynomial in $l$. For $n=2$ and $n=3$, we have second- and sixth- degree polynomials. Apr 10, 2019 at 22:31

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$$.