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$
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$
  • $\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$ – Gordon Royle Oct 26 '10 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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