4
$\begingroup$

I was reading the first answer to this question, where the answer refers to a book by F. Harary and E.M. Palmer. In the book on page 8, they provide the following result:

Theorem: The exponential generating functions $G(x)$ and $C(x)$ for labeled graphs and labeled connected graphs come to terms in the following relation $$1+G(x) = e^{C(x)}$$

What is intriguing to me is the following statement (the last paragraph of page 8) :

Furthermore, it is evident that if the exponential generating function for a class of graphs is known, then the exponential generating function for the corresponding connected graphs will be the formal logarithm of the first series, just as in (1 .2.6) for all graphs

1.2.6 is the equation above.

So if I have a generating function, $G'(x)$, for any arbitrary property,$P(a)$, on labelled graphs, then I can find generating function for a labelled graph which obeys $P(a)$ and is connected as follows:

$$1+G'(x) = e^{C'(x)}$$

Where $C'(x)$ is the generating function for the connected graph such that it obeys $P(a)$.

Is my understanding of the statement correct ? So for example if $G'(x)$ is the generating function for 2-regular graphs then the generating function for $C'(x)$ i.e connected 2-regular graphs is given as follows : $$C'(x) = \log(1+G'(x))$$

$\endgroup$

1 Answer 1

4
$\begingroup$

With this question I would cast it in a more modern light, namely combinatorial classes as introduced by Flajolet and Sedgewick in Analytic Combinatorics. They define the set operator applied to a combinatorial class $\mathcal{C}$ as follows:

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{G} = \textsc{SET}(\mathcal{C}) = \sum_{k\ge 0} \textsc{SET}_{=k}(\mathcal{C}).$$

Note that this operator includes $\textsc{SET}_{=0}(\mathcal{C})$ which is the empty set of size zero.

This gives the generating function for $\textsc{SET}(\mathcal{C})$

$$\sum_{k\ge 0} \frac{C(z)^k}{k!} = \exp C(z).$$

Now $\mathcal{G}$ and $\mathcal{C}$ are in a set-of relation but $\mathcal{G}$ may or may not include the empty graph. In the latter case we get instead of $\textsc{SET}(\mathcal{C})$ the class $\textsc{SET}_{\ge 1}(\mathcal{C})$ with generating function

$$-1 + \exp C(z).$$

It follows that we have two cases, if $\mathcal{G}$ includes the empty graph we get

$$G(z) = \exp C(z)$$

and if it does not,

$$1 + G(z) = \exp C(z).$$

In your example of $2$-regular graph the EGF is constructed from the set operator $\textsc{SET}$ as documented e.g. at this MSE link and hence it produces the empty graph as belonging to the class of graphs (a graph on no vertices with no edges does indeed have all vertices of degree two) and hence the correction term of one plus is not needed and we find

$$C(z) = \log G(z).$$

We can check this by computing the constant term of $\exp(-z/2-z^2/4)/\sqrt{1-z}$ which is one.

Another example where the correction term is not needed is the class of connected labeled graphs with some number of edges, which was discussed as this MSE link II. It should be clear that connectivity induces a set-of relationship as we may permute the connected components.

$\endgroup$
4
  • 1
    $\begingroup$ Very nice explanation. (+1) $\endgroup$ May 20, 2021 at 20:25
  • $\begingroup$ Thanks, these are classic texts. $\endgroup$ May 20, 2021 at 20:28
  • $\begingroup$ (+1) but I don’t really know anything about combinatorial classes. From your answer I understand that this trick works for 2-regular graphs, but I don’t really see why it should work for any property ! Thanks for the answer and sorry for my ignorance but I work mostly in CS and sometimes end up encountering combinatorics. $\endgroup$
    – SagarM
    May 20, 2021 at 21:07
  • 1
    $\begingroup$ It has to be a property such that if $G$ has the property, then all its connected components do and if all its components have the property, so does $G.$ I recommend the Flajolet & Sedgewick text, combinatorial classes are worth knowing e.g. to compute a wide variety of permutation statistics and their asymptotics. $\endgroup$ May 20, 2021 at 21:39

You must log in to answer this question.

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