<aside> 💡 Problem. The number of semi-strong digraphs on $n$ vertices is equal to the number of sequences of pairs of irreducible tournaments and graphs on $n$ vertices. While we know how to prove this fact using the recurrences, can we construct a direct bijection between these two families?

</aside>

Proposition.

$$ e^{S(z)} = \dfrac{1}{1 - I(z) \odot G(z)} $$

where $S(z)$ is the Exponential GF of strongly connected digraphs, $e^{S(z)}$ is the Exponential GF of semi-strong digraphs, $I(z)$ is the Exponential GF of irreducible tournaments, and $G(z)$ is the Exponential GF of all graphs.

Table of contents

Background

First of all, it is useful to recall already existing bijections of similar nature.

Permutations

The exponential generating function of permutations can be expressed as a set and a sequence:

$$ e^{\mathsf{CYC}(z)} = \dfrac{1}{1 - z} $$

<aside> ☝ The expression on the left preserves the automorphism structure of a permutation, which means that it is invariant under relabelling. On the other hand, the expression on the right is not invariant under relabelling because it requires a specific algorithm to construct the permutation from a sequence of labels.

</aside>

Graphs

This example is again a two-fold way to look at graphs:

$$ e^{C(z)} = \dfrac{1}{1 - I(z)} $$

and again, the left-hand side expression is invariant under the permutation of labels, while the expression on the right is not. The sequence of tournaments is linked by drawing all the directed edges from the left to the right, but a priori, this is not the only possible way to combinatorially describe a sequence.

Here, the tournament can be formed from a graph by independently looking at each directed edge $i \to j$. If $i < j$ then we draw an edge $i -j$ in the original graph, or not draw otherwise.