1
$\begingroup$

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?

$\endgroup$
11
  • $\begingroup$ 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? $\endgroup$ Apr 10, 2019 at 14:30
  • $\begingroup$ @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. $\endgroup$
    – Jiro
    Apr 10, 2019 at 14:55
  • $\begingroup$ @MaxAlekseyev oh yes, I'm sorry, it should be trails not paths. I will correct this $\endgroup$
    – Jiro
    Apr 10, 2019 at 15:20
  • $\begingroup$ @MaxAlekseyev In fact, it's even walks $\endgroup$
    – Jiro
    Apr 10, 2019 at 15:27
  • $\begingroup$ @MaxAlekseyev Thanks for the clarification. $e_p$ are multisets. $\endgroup$
    – Jiro
    Apr 10, 2019 at 15:31

2 Answers 2

1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ that's certainly very helpful! Also I can confirm the solutions to $n=4$. $\endgroup$
    – Jiro
    Apr 10, 2019 at 22:16
  • $\begingroup$ 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. $\endgroup$
    – Jiro
    Apr 10, 2019 at 22:24
  • $\begingroup$ @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. $\endgroup$ Apr 10, 2019 at 22:31
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.