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?

Improve this question
$\endgroup$

5 Answers 5

Reset to default
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}$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks! That'll save me from wasting time doing it in a more complicated way. $\endgroup$
    – Douglas S. Stones
    Commented 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$
    – Douglas S. Stones
    Commented Jan 19, 2012 at 5:18
  • $\begingroup$ The provided link is broken, but I think this (whileydave.com/projects/tutte) might be the same? $\endgroup$
    – QCD_IS_GOOD
    Commented Oct 23 at 22:41
  • $\begingroup$ @QCD_IS_GOOD Yes, Dave has moved and the link you give is correct. Note that the latest version has altered the output when using "--chromatic" so that it gives the correct coefficients, but expressed in a different basis. You need to substitute $x \to x-1$ and multiply by $x$ to get the actual chromatic polynomial. Or just use the previous version. $\endgroup$
    – Gordon Royle
    Commented Oct 24 at 7:54
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).

Improve this answer
$\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.

Improve this answer
$\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$
    – Gordon Royle
    Commented 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$
    – Douglas S. Stones
    Commented 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.

Improve this answer
$\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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .