<p>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.</p>

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

<p>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: $\begin{equation} X(N) = \sum_{L \in {\cal L}} N^{c[\pi(L)]} \text{.} \end{equation}$</p>

<p>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.</p>

<p>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.?</p>

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

CC BY-SA 3.0
2014-10-06T18:45:02.087Z
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
CC BY-SA 3.0
2014-10-07T01:21:18.163Z
maybe some connections here to look into? [applications of representation theory of the symmetric group](http://cstheory.stackexchange.com/questions/12691/applications-of-representation-theory-of-the-symmetric-group) (tcs.se)
vzn
CC BY-SA 3.0
2014-10-07T01:47:29.297Z
Would +ve grassmanians be relevant too?
user3483902
CC BY-SA 3.0
2014-10-09T22:24:50.780Z
it might help some to tie this in with the original physics problem that leads to it.... ?
vzn
CC BY-SA 3.0
2014-10-10T00:29:30.987Z
"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
CC BY-SA 3.0
2014-10-10T01:43:18.793Z
ok. idea: maybe quantum computing theory could shed some light on it somehow. dont follow the connection to the Tutte polynomial so far.
vzn
<cc.complexity-theory><graph-theory><co.combinatorics><symmetry>
Is this graph polynomial known? Can it be efficiently computed?
user3483902
# Is this graph polynomial known? Can it be efficiently computed?

(Asked by: username_0 on 2014-10-06)

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, $\begin{equation} \pi[(\ell\_1, \dots, \ell\_m)] = t\_{\ell\_1} t\_{\ell\_2} \cdots t\_{\ell\_m}. \end{equation}$

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: $\begin{equation} X(N) = \sum\_{L \in {\cal L}} N^{c[\pi(L)]} \text{.} \end{equation}$

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>"

**Tags:** cc.complexity-theory, graph-theory, co.combinatorics, symmetry
> **Comments:**
> **username_0**: 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.  
> **username_1**: maybe some connections here to look into? [applications of representation theory of the symmetric group](http://cstheory.stackexchange.com/questions/12691/applications-of-representation-theory-of-the-symmetric-group) (tcs.se)  
> **username_0**: Would +ve grassmanians be relevant too?  
> **username_1**: it might help some to tie this in with the original physics problem that leads to it.... ?  
> **username_0**: "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.  
> **username_1**: ok. idea: maybe quantum computing theory could shed some light on it somehow. dont follow the connection to the Tutte polynomial so far.  

---

## 0 answers

