Generating function in graph theory

Question

I am looking for a simple illustration of generating functions in graph theory.

So far, the matching polynomial seems to be the best. But I want something bit richer; at least a derivative should show up.

Please help.

Answer 1

Consider all trees with labelled vertices $1,\dots,n$, for each tree take a monomial $\prod_{i=1}^n x_i^{\deg(i)-1}$. The sum $F_n$ of these monomials equals $(\sum x_i)^{n-2}$. This may be proved by induction. The step from $n-1$ to $n$: note that $F_n$ is symmetric of degree $n-2$, thus it suffices to prove that all monomials in $F_n$ without $x_n$ sum up to $(x_1+\dots+x_{n-1})^{n-2}$. They correspond to the trees in which the vertex $n$ is a leaf, which are the trees on the vertices $1,\dots,n-1$ plus an edge from any of these vertices to $x_n$. This sum equals $F_{n-1}(x_1,\dots,x_{n-1})(x_1+\dots+x_{n-1})=(x_1+\dots+x_{n-1})^{n-2}$ as desired.

It implies, in particular, the Cayley theorem that the total number of labelled trees on $n$ vertices equals $n^{n-2}$.

The method may be adapted to other enumerative problems, like the trees on $n+k$ vertices $\{-k,-1,\dots,-1,1,2,\dots,n-1,n\}$ in which any edge joins two vertices with different signs (spanning trees of the complete bipartite graph).

This is essentially the essence of Cayley's paper 'A theorem on Trees' (Quart. Math. Journ. 1889).

Answer 2

A good source (despite not being very modern) is Harary, Palmer - Graphical enumeration. A few examples: let $C(x) = \sum_{n = 0}^{\infty} x^n \frac{2^{n(n - 1) / 2}}{n!}$ be the e.g.f. of labelled graphs on $n$ vertices. It is well-known that $\ln C(x)$ is the e.g.f. of connected labelled graphs on $n$ vertices (it is true in general for any type of structures on $n$ labelled elements that can be uniquely separated into inseparable "atoms" of any kind, e.g. permutations, equivalence relations, hypergraphs, and so on). A bit more work yields that the e.g.f. $B(x)$ of 2-connected labelled graphs satisfies $\ln C'(x) = B(xC(x))$.

Answer 3

Does Tutte polynomial count?

Also, to generalize slightly what was noted in another answer, if graphs in a combinatorial class have no restriction on the number of connected components then, for the exponential generating functions over that class, we have $$\mathrm{All}(x)=e^{\mathrm{Connected}(x)}.$$

Update: Here is another example, this time for trees. Suppose the trees in a combinatorial class $\mathcal{T}$ (with no restriction on depth of nodes) have the ordinary generating function $T$, and the ogf's counting vertices and leaves in those trees are $V$ and $L$, respectively. Then $$V=LT.$$ This can be refined with other statistics as well.

Answer 4

See Duchamp's discussion of the exponential formula in the MO-Q Important formulas in combinatorics (cf. also "Three lectures on free probability" by Novak and LaCroix https://arxiv.org/abs/1205.2097).

Also see one of my answers to that question on how iterated tangent vectors / Lie derivatives can generate partition polynomials enumerating distinct faces of associahedra and other combinatorial structures that can be related to rooted trees.

Answer 5

You asked for a polynomial that involved derivatives, and one that has a nice such relation is the Independence polynomial, which is discussed in a survey article by Levit and Mandrescu

If we define $I(G,x):=\sum_j s_j x^j$ where $s_j$ counts the number of independent sets of cardinality $j$ then it is straightforward to prove that

$$I' (G,x) = \sum_{v\in V(G)} I(G - N[v],x)$$

where $N[v]$ is the closed set of neighbours of $v$ in $G$ (also including $v$ itself).

Answer 6

The e.g.f. $(1-mx)^{-1/m}-1 \;$ for the varieties of plane (m+1)-ary increasing trees as presented by Bergeron, Flajolet, and Salvy in "Varieties of increasing trees" has several connections to differential operators and equations as well as other combinatorial structures. See OEIS A094638 for some references and relations.

Answer 7

Generating functions are ubiquitous in the enumerative theory of maps, that is, graphs on surfaces. For planar graphs this theory was first developed in the seminal work of Tutte in the late 60s through early 80s. But in recent years there has also been a lot of work devoted to the higher genus maps as well. It turns out that the generating functions for these objects satisfy sophisticated differential equations (coming from the "KP hierary"); see for instance Goulden and Jackson, "The KP hierarchy, branched covers, and triangulations" (https://arxiv.org/abs/0803.3980) or Carrell and Chaupy, "A simple recurrence formula for the number of rooted maps on surfaces by edges and genus" (https://dmtcs.episciences.org/2424/)

Answer 8

For any set $V$, we let $V^{!2}$ denote the set of all pairs $\left(u, v\right) \in V^2$ with $u \neq v$.

A loopless simple digraph shall mean a pair $\left(V, A\right)$, where $V$ is a finite set and $A$ is a subset of $V^{!2}$. Thus, we are not considering multidigraphs, and we are forbidding loops.

A Hamiltonian path in a loopless simple digraph $\left(V, A\right)$ means a list $\left(v_1, v_2, \ldots, v_n\right)$ containing each $v \in V$ exactly once and having the property that $\left(v_i, v_{i+1}\right) \in A$ for each $i \in \left\{1,2,\ldots,n-1\right\}$.

If $D = \left(V, A\right)$ is a loopless simple digraph, then the complement $\overline{D}$ of $D$ is defined to be the loopless simple digraph $\left(V, V^{!2} \setminus A\right)$. (Thus, roughly speaking, $\overline{D}$ has none of the arcs that $D$ has, but has all of the arcs that $D$ is missing.)

Theorem 1 (Berge). If $D$ is a loopless simple digraph, then the number of Hamiltonian paths of $D$ has the same parity as the number of Hamiltonian paths of $\overline{D}$.

A tournament means a loopless simple digraph $D = \left(V, A\right)$ such that each $\left(u, v\right) \in V^{!2}$ satisfies either $\left(u, v\right) \in A$ or $\left(v, u\right) \in A$ but never both.

Theorem 2 (Redei). If $D$ is a tournament, then the number of Hamiltonian paths of $D$ is odd.

Both theorems above are proven using generating functions in Bodo Lass, Variations sur le thème $E + \overline{E} = XY$. (Namely, Theorem 1 is part of his Corollaire 4.1, whereas Theorem 2 is part of his Corollaire 5.1.)

These theorems are not as easy as they sound. The most beautiful proofs I know of appear in §10.2 (Theorem 6) of Claude Berge, Graphs, 3rd edition, North-Holland 1991. I have reproduced them in Math 5707 Spring 2017 lecture 7 (the notes are handwritten; I will probably TeX them when I get to teach that class again).

Also, Theorem 1 and Theorem 2 are problem 19 and problem 20 in §5 of the famous László Lovász, Combinatorial Problems and Exercises, 2nd edition 2003.

There is also Rédei's original proof and another proof (apparently the same) in §9 of John W. Moon, Topics on Tournaments, 2015, Project Gutenberg Release #42833.