Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

5 Answers 5

up vote 8 down vote accepted

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

share|improve this answer
    
Thanks! That'll save me from wasting time doing it in a more complicated way. –  Douglas S. Stones Jan 19 '12 at 4:14
2  
PS. I tested "tutte" and "tutte_bhkk" on K_15 on my comp (which is much slower than yours): 19.468s vs. 7m42.791s, respectively (wow!). "tutte" computed K_18 in 9m11.544s. –  Douglas S. Stones Jan 19 '12 at 5:18

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

share|improve this answer

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.

share|improve this answer
2  
I'm pretty sure that your recurrence is essentially equivalent to the one that I was using in Maple, and alluded to in my answer (except that I called it symbolic computation rather than recurrence, but it is the same thing). The arithmetic on huge numbers is what takes up all the time. Just for fun, I'll implement your recurrence, compare and report back later on the weekend. –  Gordon Royle Jan 20 '12 at 8:32
    
Indeed, once it's pointed out that they're easy to count, the titled question is no longer relevant. Thanks for the links (they all look relevant)! –  Douglas S. Stones Jan 20 '12 at 21:41

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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