4
$\begingroup$

Given a finite tree $T$ with $n$ vertices labelled $1,\dots,n$, we say that a permutation $\sigma$ of $1,\dots,n$ rips all edges if $\{\sigma(i),\sigma(j)\}$ is never an edge for every edge $\{i,j\}$ of $T$. It is easy to see that every tree of diameter at least $3$ has such permutations. They are not very hard to count (see A2464 of the Encyclopedia of Integer Sequences) for Dynkin diagrams of type $A$ (with edges given by $\{i,i+1\}$ for $i=1,\dots,n-1$). Can they be counted similarly in polynomial time for an arbitrary tree of diameter $\geq 3$?

More generally, can one compute efficiently the ripping polynomial $R(T)=\sum_{k=0}^{n-1}\alpha_k t^k$ which counts numbers $\alpha_k$ of permutations preserving exactly $k$ edges of $T$? This is again easy for Dynkin diagrams of type $A$ with $R(n)$ defined by \begin{eqnarray*} R(n)&=&A(n)+tB(n),\\ A(1)&=&1,\\ A(n+1)&=&(1-t)A'(n)+(n-2)A(n)+t(1-t)B'(n)+t(n-2)B(n),\\ B(1)&=&0,\\ B(n+1)&=&(1+t)B(n)+2A(n). \end{eqnarray*} The picture obtained by plotting all complex roots (for $n\sim 100$) might be slightly unsuitable for a general audience. Interestingly, we have $R'(n)=2(n-1)(n-1)!$ showing that the mean number of non-ripped edges by a random permutation equals $2-\frac{2}{n}$.

Added: The polynomials $C(n)=\sum_{k=0}^{n-1}\gamma_kt^k$ defined by $R(n)=\sum_{k=0}^{n-1} (n-k)!\gamma_kt^k$ (with $R$ as above attached to the Dynkin diagram of type $A$ with $n$ vertices) are also somewhat interesting since they satisfy the recursion relation $C(n+1)=(1+t)C(n)+tC(n-1)$ (initial values are $C(1)=1,C(2)=1+2t$).

On can of course generalise the above questions to arbitrary graphs (answers are obvious for complete graphs for example).

$\endgroup$
4
  • $\begingroup$ Presumably it is also very easy to give a formula for these when $T$ is a star. $\endgroup$ Jun 15, 2015 at 13:35
  • $\begingroup$ @Sam Hopkins: Yes, $R(n)=(n-1)!t^{n-1}+(n-1)(n-1)!t$ which gives also a mean number of $2-2/n$ non-ripped edges if $T$ is a star with $n$ vertices. I guess the mean number of non-ripped edges is perhaps independent of the tree? $\endgroup$ Jun 15, 2015 at 13:38
  • $\begingroup$ I'm a bit confused by that last comment. Surely linearity of expectation shows that the mean number of non-ripped edges is the same for all trees on $n$ vertices, right? $\endgroup$ Jun 15, 2015 at 13:41
  • $\begingroup$ You are right, I did a mistake in my computation. $\endgroup$ Jun 15, 2015 at 13:42

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.