How many Tutte polynomials of complete graphs are known? - MathOverflow

How many Tutte polynomials of complete graphs are known?

2012-01-19T03:07:43Z

I would like to compute the Tutte polynomial of the complete graph $K_n$ for n as large as possible. Using a program by Björklund, Husfeldt, Kaski, Koivisto (here), I managed to compute up to n=18 on my home computer (in serial) in less than a day. Overall, I've been very impressed by this program.

I'm likely to include the results of these computations in an upcoming paper, so, for comparison, I would also like to mention what people have done previously in the area. (Also, I'd like to check that the computations are consistent with one another.)

Question: How far have others computed the Tutte polynomial of the complete graph?

Answer by gordon-royle for How many Tutte polynomials of complete graphs are known?

2012-01-19T04:00:33Z

Our program "tutte" (http://homepages.ecs.vuw.ac.nz/~djp/tutte/#download) can compute the TP of $K_{18}$ in 160s (on a recent machine with an i7).

However you wouldn't want to do it with this sort of program that works on general graphs, because the complete graph is special and by tackling it symbolically you can go much further.

I can do $K_{40}$ in under a minute with Maple.

Just FYI, some quick checks on consistency can be done by evaluating $T(1,1)$ and making sure it is equal to the number of spanning trees, and then $T(2,2)$ and making sure it is equal to $2^{n(n-1)/2}$.

Answer by grshutt for How many Tutte polynomials of complete graphs are known?

2012-01-19T04:08:19Z

I had already begun composing my answer when one of the authors of the paper I cite got the first post. This is as it should be, I suppose.

In any case, Haggard, Pearce, and Royle published a paper on computing Tutte polynomials in ACM Transactions on Mathematical Software Volume 37(3), article 24, 2010.

Here's the ACM link: http://dl.acm.org/citation.cfm?doid=1824801.1824802

This paper and a second on the topic are available on Pearce's web page.

Answer by Agol for How many Tutte polynomials of complete graphs are known?

2012-01-19T05:28:39Z

I think one can reduce this to computing $T_{K_n}(1,y)$.

If you consider the expansion of the Tutte polynomial in terms of subgraphs, then one may consider how this expansion breaks up under the action of permutations of the vertices of $K_n$. For a partition of $n = k_1+k_2+\cdots+k_m$, one may take a corresponding partition of the vertices of $K_n$, and then take spanning subgraphs of $K_{k_1}, \ldots, K_{k_m}$. One gets a contribution to the Tutte polynomial of $(x-1)^{m-1}\prod_{i=1}^m T_{K_{k_i}}(1,y)$. This gets multiplied by a multinomial coefficient for choosing all possible partitions with this signature, and then you sum over partitions to get the Tutte polynomial. I suppose the only issue with this approach is computing $T_{K_n}(1,y)$, corresponding to the trivial partition $m=1$.

Answer by Igor Pak for How many Tutte polynomials of complete graphs are known?

2012-01-20T06:54:39Z

This question is based on misunderstanding. Tutte polynomials of complete graphs are extremely easy to compute because there is a simple recurrence relation. See here for a simple to use formula. I (re)discovered this formula 20 years ago, but Ira Gessel found it much earlier. For references and background, see this paper by Gessel, and this followup by Gessel and Sagan. See also this recent paper (joint with Konvalinka), on how Tutte polynomial of $K_n$ is the volume of certain polytopes.

Answer by Federico Ardila for How many Tutte polynomials of complete graphs are known?

2012-07-03T01:03:20Z

There is a simple formula for the generating function of $T_{K_n}(x,y)$, which is more cleanly expressed in terms of the (equivalent) "coboundary polynomial" $X_M(q,t) = (t-1)^{r(M)} T_M(1+\frac{q}{t-1}, t)$: $$ 1+q\sum_{n \geq 1} X_{K_n}(q,t) \frac{x^n}{n!} = \left( \sum_{n \geq 0} t^{n \choose 2}\frac{x^n}{n!}\right)^q. $$ This is essentially due to Tutte in the 50s; see this paper and the references in it.

For what it's worth, using similar methods one easily obtains formulas for other similar families such as complete bipartite graphs (for graphs) and classical root systems (for matroids).