# Is this graph polynomial known? Can it be efficiently computed?

Consider a connected simple graph $G$ with $n$ vertices and $m$ edges. View each edge $\ell$ as a transposition $t_{\ell}$ acting on the set of vertices. [To be more explicit, given an edge $\ell$ joining vertices $v_1$ and $v_2$, $t_{\ell}$ is a permutation exchanging $v_1$ and $v_2$, leaving all other vertices fixed.] Let ${\cal L}$ be the set of ordered $m$-tuples of the edges, so that elements of ${\cal L}$ are of the form $L = (\ell_1, \dots, \ell_m)$, with each edge appearing exactly once.

To each $L \in {\cal L}$ we can associate a permutation $\pi(L) \in S_n$ by taking the product of transpositions, $$$\pi[(\ell_1, \dots, \ell_m)] = t_{\ell_1} t_{\ell_2} \cdots t_{\ell_m}.$$$

For $\pi \in S_n$, let $c(\pi)$ be the number of cycles in the the cycle decomposition, counting 1-cycles. So for example $c(1) = n$, and $c(\pi) = 1$ for $\pi$ an $n$-cycle. Then I can define the polynomial of interest: $$$X(N) = \sum_{L \in {\cal L}} N^{c[\pi(L)]} \text{.}$$$

My primary question is whether an efficient (in practical terms) procedure is known to compute $X(N)$, either for arbitrary graphs, or for certain families of graphs. In my application, I need to compute $X(N)$ for all graphs that are subgraphs of a given regular lattice, up to some maximum number of edges (which I would like to make as large as possible). In particular, I am focused on the square lattice (for now), which restricts to bipartite planar graphs. Perhaps also relevant, in my application parallel edges are allowed, but I focused on simple graphs here for simplicity.

I already know $X(N) = m! N$ if $G$ is a tree, and $X(N) = m! N^2$ if $G$ is a cycle. In addition, removing all bridges from $G$, there is a simple formula giving $X(N)$ as a product of the $X(N)$'s of the resulting components, multiplied by an overall factor. Beyond this, so far the best I can do is to take a brute force approach. Beyond my primary question, I am also more generally interested to learn what, if anything, is known about this polynomial. For instance, are there references where $X(N)$ is studied, is $X(N)$ related to other (perhaps better-known) graph polynomials, etc.?

Cross posted from mathoverflow, https://mathoverflow.net/questions/177103/is-this-graph-polynomial-known-can-it-be-efficiently-computed#177103"

• An example of an "edge acting as a transposition on the set of vertices" is the symmetric group $S_{8}$, and efficient computation implies some polynomial in the size of the graph. – user3483902 Oct 6 '14 at 18:45
• maybe some connections here to look into? applications of representation theory of the symmetric group (tcs.se) – vzn Oct 7 '14 at 1:21
• Would +ve grassmanians be relevant too? – user3483902 Oct 7 '14 at 1:47
• it might help some to tie this in with the original physics problem that leads to it.... ? – vzn Oct 9 '14 at 22:24
• "The problem stems from quantum spin models with $SU(N)$ symmetry". This is not very helpful, but its a start, as in the chat about this posting, the tutte polynomial could be associated with the graph. An answer, which just came up in the MO is to "test whether the tutte poly is really associated with the graph is check the deletion-contraction recurrence". And you ask a good question, as to the origins of the problem. The problem formulation is different. – user3483902 Oct 10 '14 at 0:29