Generalized activities and the Tutte polynomial (Q1173634): Difference between revisions

This paper examines the Tutte polynomial of a matroid (a generalization of the Tutte's polynomial of graph) from the point of view of basis activities. If \(r(S)\) is the rank of a subset \(S\) of the underlying set \(E\) in a matroid \(M\), then the Tutte polynomial \(t(M;x,y)\) of \(M\) is given by \[ t(M;x,y)=\sum_{S\subseteq E}(x-1)^{r(E)-r(S)}(y- 1)^{| S|-r(S)}. \] Let \(E\) be given some linear order and \(B\) be a basis of \(M\). If \(e\in E\) is not in \(B\), then \(B\cup e\) contains a unique circuit and \(e\) is called externally active or externally inactive with respect to \(B\) according to whether or not \(e\) is the least element (in the linear order of \(E\)) in this unique circuit. If \(e\in E\) is in \(B\), then \((E-B)\cup e\) contains a unique bond and \(e\) is called internally active or internally inactive with respect to B according to whether or not \(e\) is the least element in this unique bond. Letting \(e(B)\) and \(i(B)\) denote the number of externally and internally active elements with respect to basis \(B\), respectively, one obtains an alternative representation of the Tutte polynomial \[ t(M;x,y)=\sum_{\hbox {all }B}x^{i(B)}y^{e(B)}. \] The authors develop a theory of activities with respect to arbitrary sets (not just bases) that offers, among other things, a unified viewpoint on the two expansions of the Tutte polynomial given above.