9
$\begingroup$

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?

$\endgroup$

5 Answers 5

8
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks! That'll save me from wasting time doing it in a more complicated way. $\endgroup$ Jan 19, 2012 at 4:14
  • 2
    $\begingroup$ 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. $\endgroup$ Jan 19, 2012 at 5:18
13
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ Jan 20, 2012 at 8:32
  • $\begingroup$ 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)! $\endgroup$ Jan 20, 2012 at 21:41
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

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

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