10
$\begingroup$

Let Tutte polynomial on graph with edge-set $E$ be defined as follows

$$f(q,v)=\sum_{A\subseteq E} q^{\kappa(A)} v^{|A|}$$

Here the sum is over all subgraphs $A$, $\kappa(A)$ is the number of connected components in $A$, $|A|$ is number of edges in $A$.

Let $$g(q,v)=\frac{\partial}{\partial v} \log f(q,v)$$ $$h(q,v)=\frac{\partial}{\partial v} f(q,v)$$

Is anything known about $g(q,-1)$ or $h(q,-1)$?

(Edit Oct 26 2010: actually it's the multivariate Tutte polynomial restricted to all $v$'s being equal, relation to regular Tutte polynomial in Jeremy Martin's answer)

Update Oct 24 2010

$f(q,-1)$ is the number of proper $q$ colorings, $h(q,-1)$ is ???, $g(q,-1)$ is their ratio. Below are tables of values of $h(q,-1)$ for paths, cycles, complete graphs. Columns give graph size, $n=3..6$, rows give $q=2..8$

(source)

Mathematica code to generate this:

computeH[graphName_, q_] := (
   g = Normal[GraphData[graphName, "AdjacencyMatrix"]];
   edges = Select[Position[g, 1], #[[1]] < #[[2]] &];
   kr[x_, edge_] := Boole[x[[First[edge]]] == x[[Last[edge]]]];
   term[x_] := Times @@ (1 + v kr[x, #] & /@ edges);
   xs = Tuples[Range[q], Length[g]];
   f = Total[term /@ xs];
   D[f, v] /. v -> -1
   );
TableForm[
   Table[computeH[{#, n}, q], {q, 2, 8}, {n, 3, 6}]] & /@ {"Path", 
  "Cycle", "Complete"}
$\endgroup$

2 Answers 2

7
$\begingroup$

This polynomial isn't the usual Tutte polynomial, but it's equivalent. Provided that $G$ is connected (which is probably the case you're interested in, and I'll assume), it looks like $f_G(q,v)=qv^{n-1}T_G(q/v+1,v+1)$, where $n$ is the number of vertices of $G$.

One thing that comes to mind is the Crapo beta invariant, which is $(-1)^n\chi_G'(1)$, where $\chi_G(k)=(-1)^{n-1}kT_G(1-k,0)$ is the chromatic polynomial. (E.g., see exercise 22 of lecture 4 of Stanley's notes on hyperplane arrangements: http://www-math.mit.edu/~rstan/arrangements/arr.html.) Your polynomials, especially $g$, might be related to this, but I haven't thought about the details.

$\endgroup$
1
  • $\begingroup$ The polynomial as given is actually just the partition function of the q-state Potts model; this is known to be equivalent to the Tutte Polynomial, but often it is useful to work with it in the given form. $\endgroup$ Commented Oct 26, 2010 at 23:56
1
$\begingroup$

But if anyone is interested in formal derivatives of the original Tutte polynomial (for Matroids), there is a nice expression of its derivatives in terms of activities (which of course is how Tutte defined his polynomial originally) in this paper of Las Vergnas: http://arxiv.org/pdf/1205.5247.pdf.

$\endgroup$

You must log in to answer this question.

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