How many Tutte polynomials of complete graphs are known? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T00:30:27Z http://mathoverflow.net/feeds/question/86066 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/86066/how-many-tutte-polynomials-of-complete-graphs-are-known How many Tutte polynomials of complete graphs are known? Douglas S. Stones 2012-01-19T03:07:43Z 2012-07-03T01:03:20Z <p>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 (<a href="https://github.com/thorehusfeldt/tutte_bhkk" rel="nofollow">here</a>), 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.</p> <p>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.)</p> <p><strong>Question</strong>: How far have others computed the Tutte polynomial of the complete graph?</p> http://mathoverflow.net/questions/86066/how-many-tutte-polynomials-of-complete-graphs-are-known/86070#86070 Answer by gordon-royle for How many Tutte polynomials of complete graphs are known? gordon-royle 2012-01-19T04:00:33Z 2012-01-19T04:00:33Z <p>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).</p> <p>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. </p> <p>I can do $K_{40}$ in under a minute with Maple.</p> <p>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}$.</p> http://mathoverflow.net/questions/86066/how-many-tutte-polynomials-of-complete-graphs-are-known/86071#86071 Answer by grshutt for How many Tutte polynomials of complete graphs are known? grshutt 2012-01-19T04:08:19Z 2012-01-19T04:08:19Z <p>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. </p> <p>In any case, Haggard, Pearce, and Royle published a paper on computing Tutte polynomials in <em>ACM Transactions on Mathematical Software</em> Volume 37(3), article 24, 2010.</p> <p>Here's the ACM link: <a href="http://dl.acm.org/citation.cfm?doid=1824801.1824802" rel="nofollow">http://dl.acm.org/citation.cfm?doid=1824801.1824802</a></p> <p>This paper and a second on the topic are available on Pearce's web page.</p> http://mathoverflow.net/questions/86066/how-many-tutte-polynomials-of-complete-graphs-are-known/86076#86076 Answer by Agol for How many Tutte polynomials of complete graphs are known? Agol 2012-01-19T05:28:39Z 2012-01-19T05:28:39Z <p>I think one can reduce this to computing $T_{K_n}(1,y)$. </p> <p>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$. </p> http://mathoverflow.net/questions/86066/how-many-tutte-polynomials-of-complete-graphs-are-known/86174#86174 Answer by Igor Pak for How many Tutte polynomials of complete graphs are known? Igor Pak 2012-01-20T06:54:39Z 2012-01-20T06:54:39Z <p>This question is based on misunderstanding. Tutte polynomials of complete graphs are extremely easy to compute because there is a simple recurrence relation. See <a href="http://www.math.ucla.edu/~pak/papers/Pak_Computation_Tutte_polynomial_complete_graphs.pdf" rel="nofollow">here</a> 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 <a href="http://people.brandeis.edu/~gessel/homepage/papers/decomposition.pdf" rel="nofollow">this paper</a> by Gessel, and <a href="http://www.combinatorics.org/Volume_3/PDF/v3i2r9.pdf" rel="nofollow">this followup</a> by Gessel and Sagan. See also <a href="http://www.math.ucla.edu/~pak/papers/cayley10.pdf" rel="nofollow">this recent paper</a> (joint with Konvalinka), on how Tutte polynomial of $K_n$ is the volume of certain polytopes. </p> http://mathoverflow.net/questions/86066/how-many-tutte-polynomials-of-complete-graphs-are-known/101193#101193 Answer by Federico Ardila for How many Tutte polynomials of complete graphs are known? Federico Ardila 2012-07-03T01:03:20Z 2012-07-03T01:03:20Z <p>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 <a href="http://math.sfsu.edu/federico/Articles/arrangem.pdf" rel="nofollow">this paper</a> and the references in it.</p> <p>For what it's worth, using similar methods one easily obtains formulas for other similar families such as <a href="http://www.math.umn.edu/~reiner/Papers/cyclotomic.pdf" rel="nofollow">complete bipartite graphs</a> (for graphs) and <a href="http://math.sfsu.edu/federico/Articles/arrangem.pdf" rel="nofollow">classical root systems</a> (for matroids).</p>