The sand-pile model and Tutte polynomials

A new explicit bijection between spanning trees and recurrent configurations of the sand-pile model is given. This mapping is such that the difference between the number of grains on a configuration and the external activity of the associate tree is the number of edges of the graph. It gives a bijective proof of a result of Merino López expressing the generating function of recurrent configurations as an evaluation of the Tutte polynomial.     

Tutte polynomials for trees

We define two two-variable polynomials for rooted trees and one two-variable polynomial for unrooted trees, all of which are based on the coranknullity formulation of the Tutte polynomial of a graph or matroid. For the rooted polynomials, we show that the polynomial completely determines the rooted tree, i.e., rooted trees T₁ and T₂ are isomorphic if and only if f(T₁) = f(T₂). The corresponding question is open in the unrooted case, although we can reconstruct the degree sequence, number of subtrees of size k for all k, and the number of paths of length k for all k from the (unrooted) polynomial. The key difference between these three polynomials and the standard Tutte polynomial is the rank function used; we use pruning and branching ranks to define the polynomials. We also give a subtree expansion of the polynomials and a deletion-contraction recursion they satisfy.     

Combinatorial interpretations for TG(1, −1)

Let G be a connected and simple graph with vertex set {1, 2, …, n + 1} and T_G(x, y) the Tutte polynomial of G. In this paper, we give combinatorial interpretations for T_G(1, ?1). In particular, we give the definitions of even spanning tree and left spanning tree. We prove T_G(1, ?1) is the number of even‐left spanning trees of G. We associate a permutation with a spanning forest of G and give the definition of odd G‐permutations. We show T_G(1, ?1) is the number of odd G‐permutations. We give a bijection from the set of odd K_{n + 1}‐permutations to the set of alternating permutations on the set {1, 2, …, n}. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 341–348, 2012     

Coboundaries, Flows, and Tutte Polynomials of Matrices

Using matroid duality and the critical problem, we show that certain evaluations of the Tutte polynomial of a matroid represented as a matrix over a finite field GF(q) can be interpreted as weighted sums over pairs f , g of functions defined from the ground set to GF(q) whose difference f – g is the restriction of a linear functional on the column space of the matrix. Similar interpretations are given for the characteristic polynomial evaluated at q. These interpretations extend and elaborate interpretations for Tutte and chromatic polynomials of graphs due to Goodall and Matiyasevich. Received July 14, 2006     

Level of nodes in increasing trees revisited

Simply generated families of trees are described by the equation T(z) = ϕ(T(z)) for their generating function. If a tree has n nodes, we say that it is increasing if each node has a label ∈ { 1,…,n}, no label occurs twice, and whenever we proceed from the root to a leaf, the labels are increasing. This leads to the concept of simple families of increasing trees. Three such families are especially important: recursive trees, heap ordered trees, and binary increasing trees. They belong to the subclass of very simple families of increasing trees, which can be characterized in 3 different ways. This paper contains results about these families as well as about polynomial families (the function ϕ(u) is just a polynomial). The random variable of interest is the level of the node (labelled) j, in random trees of size n ≥ j. For very simple families, this is independent of n, and the limiting distribution is Gaussian. For polynomial families, we can prove this as well for j,n → ∞ such that n − j is fixed. Additional results are also given. These results follow from the study of certain trivariate generating functions and Hwang's quasi power theorem. They unify and extend earlier results by Devroye, Mahmoud, and others. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

The active bijection in graphs, hyperplane arrangements, and oriented matroids, 1: The fully optimal basis of a bounded region

The present paper is the first in a series of four dealing with a mapping, introduced by the present authors, from orientations to spanning trees in graphs, from regions to simplices in real hyperplane arrangements, from reorientations to bases in oriented matroids (in order of increasing generality). This mapping is actually defined for ordered oriented matroids. We call it the active orientation-to-basis mapping, in reference to an extensive use of activities, a notion depending on a linear ordering, first introduced by W.T. Tutte for spanning trees in graphs. The active mapping, which preserves activities, can be considered as a bijective generalization of a polynomial identity relating two expressions–one in terms of activities of reorientations, and the other in terms of activities of bases–of the Tutte polynomial of a graph, a hyperplane arrangement or an oriented matroid. Specializations include bijective versions of well-known enumerative results related to the counting of acyclic orientations in graphs or of regions in hyperplane arrangements. Other interesting features of the active mapping are links established between linear programming and the Tutte polynomial.We consider here the bounded case of the active mapping, where bounded corresponds to bipolar orientations in the case of graphs, and refers to bounded regions in the case of real hyperplane arrangements, or of oriented matroids. In terms of activities, this is the uniactive internal case. We introduce fully optimal bases, simply defined in terms of signs, strengthening optimal bases of linear programming. An optimal basis is associated with one flat with a maximality property, whereas a fully optimal basis is equivalent to a complete flag of flats, each with a maximality property. The main results of the paper are that a bounded region has a unique fully optimal basis, and that, up to negating all signs, fully optimal bases provide a bijection between bounded regions and uniactive internal bases. In the bounded case, up to negating all signs, the active mapping is a bijection.     

On the Tutte–Krushkal–Renardy polynomial for cell complexes

Recently V. Krushkal and D. Renardy generalized the Tutte polynomial from graphs to cell complexes. We show that evaluating this polynomial at the origin gives the number of cellular spanning trees in the sense of A. Duval, C. Klivans, and J. Martin. Moreover, after a slight modification, the Tutte–Krushkal–Renardy polynomial evaluated at the origin gives a weighted count of cellular spanning trees, and therefore its free term can be calculated by the cellular matrix-tree theorem of Duval et al. In the case of cell decompositions of a sphere, this modified polynomial satisfies the same duality identity as the original polynomial. We find that evaluating the Tutte–Krushkal–Renardy along a certain line gives the Bott polynomial. Finally we prove skein relations for the Tutte–Krushkal–Renardy polynomial.     

Milnor numbers, spanning trees, and the Alexander–Conway polynomial

We study relations between the Alexander–Conway polynomial _L and Milnor higher linking numbers of links from the point of view of finite-type (Vassiliev) invariants. We give a formula for the first non-vanishing coefficient of _L of an m-component link L all of whose Milnor numbers μ_i1…ip vanish for pn. We express this coefficient as a polynomial in Milnor numbers of L. Depending on whether the parity of n is odd or even, the terms in this polynomial correspond either to spanning trees in certain graphs or to decompositions of certain 3-graphs into pairs of spanning trees. Our results complement determinantal formulas of Traldi and Levine obtained by geometric methods.     

Generating the maximum spanning trees of a weighted graph

The present paper contains an efficient algorithm for generating all the maximum spanning trees of a weighted graph and a polynomial time algorithm for counting them. As known, the tree representations of an acylic hypergraph are exactly the maximum spanning trees of the weighted intersection graph of its edges. Therefore, they can be generated and counted by these algorithms.     

Counting colored planar maps: Algebraicity results

We address the enumeration of properly q-colored planar maps, or more precisely, the enumeration of rooted planar maps M weighted by their chromatic polynomial χM(q) and counted by the number of vertices and faces. We prove that the associated generating function is algebraic when q≠0,4 is of the form 2+2cos(jπ/m), for integers j and m. This includes the two integer values q=2 and q=3. We extend this to planar maps weighted by their Potts polynomial PM(q,ν), which counts all q-colorings (proper or not) by the number of monochromatic edges. We then prove similar results for planar triangulations, thus generalizing some results of Tutte which dealt with their proper q-colorings. In statistical physics terms, the problem we study consists in solving the Potts model on random planar lattices. From a technical viewpoint, this means solving non-linear equations with two “catalytic” variables. To our knowledge, this is the first time such equations are being solved since Tutte?s remarkable solution of properly q-colored triangulations.     

Chip firing and the tutte polynomial

It is shown that the generating function of critical configurations of a version of a chip firing game on a graphG is an evaluation of the Tutte polynomial ofG, thus proving a conjecture of Biggs [3]. Supported by a grant from D.G.A.P.A.     

A Bijection for Eulerian-equivalence Classes of Totally Cyclic Orientations

Gioan showed that the number of cycle reversing classes of totally cyclic orientations of a given graph can be calculated as an evaluation of the corresponding Tutte polynomial. We note that the concept of cycle reversing classes of orientations coincides with that of Eulerian-equivalence classes considered by Chen and Stanley, and Kochol. Based on this coincidence, we give a bijective proof of Gioan’s result. Precisely, the main result of the paper is an algorithmic bijection between the set of Eulerian-equivalence classes of totally cyclic orientations and the set of spanning trees without internally active edges.      

On Graphs Determined by Their Tutte Polynomials

We say that a graph G is T-unique if any other graph having the same Tutte polynomial as G is necessarily isomorphic to G. In this paper we show that several well-known families of graphs are T-unique: wheels, squares of cycles, complete multipartite graphs, ladders, Möbius ladders, and hypercubes. In order to prove these results, we show that several parameters of a graph, like the number of cycles of length 3, 4 and 5, and the edge-connectivity are determined by its Tutte polynomial.Research partially supported by projects BFM2001-2340 and by CUR Gen. Cat. 1999SGR00356Final version received: January 10, 2003     

Strongly inequivalent representations and Tutte polynomials of matroids

We develop constructive techniques to show that non-isomorphic 3-connected matroids that are representable over a fixed finite field and that have the same Tutte polynomial abound. In particular, for most prime powers q, we construct infinite families of sets of 3-connected matroids for which the matroids in a given set are non-isomorphic, are representable over GF(q), and have the same Tutte polynomial. Furthermore, the cardinalities of the sets of matroids in a given family grow exponentially as a function of rank, and there are many such families.In Memory of Gian-Carlo Rota     

Tutte sets in graphs I: Maximal tutte sets and D‐graphs

A well‐known formula of Tutte and Berge expresses the size of a maximum matching in a graph G in terms of what is usually called the deficiency of G. A subset X of V(G) for which this deficiency is attained is called a Tutte set of G. While much is known about maximum matchings, less is known about the structure of Tutte sets. In this article, we study the structural aspects of maximal Tutte sets in a graph G. Towards this end, we introduce a related graph D(G). We first show that the maximal Tutte sets in G are precisely the maximal independent sets in its D‐graph D(G), and then continue with the study of D‐graphs in their own right, and of iterated D‐graphs. We show that G is isomorphic to a spanning subgraph of D(G), and characterize the graphs for which G?D(G) and for which D(G)?D²(G). Surprisingly, it turns out that for every graph G with a perfect matching, D³(G)?D²(G). Finally, we characterize bipartite D‐graphs and comment on the problem of characterizing D‐graphs in general. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 343–358, 2007     

Contraction–Deletion Invariants for Graphs

We consider generalizations of the Tutte polynomial on multigraphs obtained by keeping the main recurrence relation T(G)=T(G/e)+T(G−e) for eE(G) neither a bridge nor a loop and dropping the relations for bridges and loops. Our first aim is to find the universal invariant satisfying these conditions, from which all others may be obtained. Surprisingly, this turns out to be the universal V-function Z of Tutte (1947, Proc. Cambridge Philos. Soc.43, 26–40) defined to obey the same relation for bridges as well. We also obtain a corresponding result for graphs with colours on the edges and describe the universal coloured V-function, which is more complicated than Z. Extending results of Tutte (1974, J. Combin. Theory Ser. B16, 168–174) and Brylawski (1981, J. Combin. Theory Ser. B30, 233–246), we give a simple proof that there are non-isomorphic graphs of arbitrarily high connectivity with the same Tutte polynomial and the same value of Z. We conjecture that almost all graphs are determined by their chromatic or Tutte polynomials and provide mild evidence to support this.     

Packing of Steiner trees and S-connectors in graphs

Nash-Williams and Tutte independently characterized when a graph has k edge-disjoint spanning trees; a consequence is that 2k-edge-connected graphs have k edge-disjoint spanning trees. Kriesell conjectured a more general statement: defining a set S⊆V(G) to be j-edge-connected in G if S lies in a single component of any graph obtained by deleting fewer than j edges from G, he conjectured that if S is 2k-edge-connected in G, then G has k edge-disjoint trees containing S. Lap Chi Lau proved that the conclusion holds whenever S is 24k-edge-connected in G.We improve Lau?s result by showing that it suffices for S to be 6.5k-edge-connected in G. This and an analogous result for packing stronger objects called “S-connectors” follow from a common generalization of the Tree Packing Theorem and Hakimi?s criterion for orientations with specified outdegrees. We prove the general theorem using submodular functions and the Matroid Union Theorem.     

Limit laws for embedded trees: Applications to the integrated superBrownian excursion

We study three families of labeled plane trees. In all these trees, the root is labeled 0 and the labels of two adjacent nodes differ by 0,1, or ?1. One part of the paper is devoted to enumerative results. For each family, and for all j ∈ ?, we obtain closed form expressions for the following three generating functions: the generating function of trees having no label larger than j; the (bivariate) generating function of trees, counted by the number of edges and the number of nodes labeled j; and finally the (bivariate) generating function of trees, counted by the number of edges and the number of nodes labeled at least, j. Strangely enough, all these series turn out to be algebraic, but we have no combinatorial intuition for this algebraicity. The other part of the paper is devoted to deriving limit laws from these enumerative results. In each of our families of trees, we endow the trees of size n with the uniform distribution and study the following random variables: M_n, the largest label occurring in a (random) tree; X_n(j), the number of nodes labeled j; and X(j), the number of nodes labeled j or more. We obtain limit laws for scaled versions of these random variables. Finally, we translate the above limit results into statements dealing with the integrated superBrownian excursion. In particular, we describe the law of the supremum of its support (thus recovering some earlier results obtained by Delmas) and the law of its distribution function at a given point. We also conjecture the law of its density (at a given point). © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006