Problem. The number of semi-strong digraphs on vertices is equal to the number of sequences of pairs of irreducible tournaments and graphs on vertices. While we know how to prove this fact using the recurrences, can we construct a direct bijection between these two families?
Proposition.
where is the Exponential GF of strongly connected digraphs, is the Exponential GF of semi-strong digraphs, is the Exponential GF of irreducible tournaments, and is the Exponential GF of all graphs.
Β
Table of contents
BackgroundPermutationsGraphsEndomorphismsThe naive approach does not workLooking for more sophisticated bijectionsSingle decorated tournamentsAlternative characterisations of semi-strong digraphsA new bijection: constraining Liskovets' decompositionPlaying with exploration processesPlaying with conversionsSummaryList of open questionsAlready known bijectionsSome new fancy bijections
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:
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.
Graphs
This example is again a two-fold way to look at graphs:
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 . If then we draw an edge in the original graph, or not draw otherwise.
Β
Challenge. Why is that?
Pointed derivative : . Distinguishing a vertex in a combinatorial object.
Endomorphisms
The species of endomorphisms has a generating function
and can be expressed as
The naive approach does not work
If we follow the same naive strategy as we did in graphs, then the bijection fails. The naive strategy can be described as follows:
- There are four possible edge combinations for each pair of vertices in a directed graph
- There are also four possible edge combinations in a pair of a tournament and a graph (or in a pair of a tournament and a tournament)
- We could map these four combinations into four combinations in some particular order.
Β
If such a mapping exists, it can be partly reconstructed by looking at semi-strong digraphs with 2 vertices. There are two of them:
At the same time, there are two sequences of :
Β
A naive approach assumes that there is a simple algorithm for forming the sequences and turning the directed edges of a decorated tournament into the edges of a strongly connected digraph by independently looking at pairs of indices.
Β
In this case, let there be an arrow for the first sequence and in the second sequence. Without loss of generality, we assume that there is no further decoration by default.
Therefore, a non-decorated arrow should become an empty arc, and a non-decorated arrow needs to become a double-direction arc. The same applies more generally for indices depending on whether or not.
Β
Then, we proceed to drawing semi-strong digraphs and sequences of decorated irreducible tournaments with three vertices.
There are 4 semi-strong digraphs which are not strongly connected and 18 more strongly connected, which makes it 22 semi-strong digraphs in total.
At the same time, there are 6 sequences of decorated irreducible tournaments which are not irreducible, and 16 more irreducible.
Now, we have a partial correspondence between sequences of decorated tournaments and directed graphs, which looks nice at the beginning:
But already the next decorated tournament cannot be mapped into a semi-strong digraph without modifying other directed edges.
Looking for more sophisticated bijections
It turns out that there are some more bijections that are not independent across pairs of edges. First of such bijections can be traced down to Liskovets' 1969 paper.
Lemma (Liskovets 1969). A digraph is called initially connected if its every node is reachable from the node with label 1. The Graphic GF of initially connected digraphs is equal to Exponential GF of connected graphs:
which is equivalent to saying that the numbers of initially connected digraphs and of connected graphs are connected by a relation
Another alternative way to write the same formula using Hadamard product is
Proof (click to expand).
Consider a connected graph . We shall define a total order by looking at the distance towards the vertex with label 1. Specifically,
Now, whenever there is an edge in the connected graph, we orient it according to the total order between the vertices: if . This ensures that every node is reachable from 1 by directed arcs. Now we add an arbitrary subset of edges for all the pairs . The magical fact is that adding these reciprocal edges does not change the oriented distance from 1 at all (I had a hard time believing that, but take my word for it). Therefore, this construction is reversible.
Β
We can remark that this fact has also been reproven at the end of the conclusion of "The birth of the giant component", [Janson, Knuth, Εuczak, Pittel '1993].
Β
Following his proof, we discovered one more fact with Γlie which also has a simple combinatorial interpretation. It provides epsilon-more insight into the structure of initially connected digraphs. Note that any initially-connected digraph has exactly one source-like component.
Β
Lemma (de Panafieu, Dovgal 2019). Initially connected digraphs with one distinguished vertex are in bijection with digraphs having a unique source-like component where one vertex of that component is distinguished.
Proof (click to expand).
If the distinguished vertex belongs to the only source-like SCC of the initially connected digraph, then it falls in the second class. Otherwise, by switching the labels of the distinguished vertex and the vertex with label 1, we obtain the graph from the second class.
Β
These bijections can teach us that the order can be defined by distances to certain vertices, and moreover, that the order is label-permutation dependent, and not independent over pairs of vertices. However, initially connected digraphs may still seem somewhat an artificial class which is not directly connected with strongly connected digraphs. This is not true, as demonstrated by another bijection by Robinson in 1995.
Β
Lemma (Robinson 1995). Let denote the number of strongly connected digraphs on vertices and let denote the number of digraphs having a unique source and sink such that every node is reachable from the source and such that the sink is reachable from every node. Then, for
There are two ways to prove this formula. The first way is by constructing the Exponential GF of , by specifying digraphs having exactly one source-like and sink-like component, such that both of these components contain exactly one vertex. The proof can be completed by computing the coefficients. Remarkably, this way gives a quite complicated expression for the GF, so this relation looks like magic.
Robinson also gives a direct combinatorial proof. Note that in the original paper, Robinson is using a different terminology. Specifically, what we call sinks and sources, he calls, respectively, the out-nodes and the in-nodes (the same applies to components). In his paper, a sink denotes a vertex reachable from every node of the graph. This means that a non-null digraph may have zero sources and zero sinks, according to his definition.
Proof (click to expand).
When , the source and the sink are distinct. If they are identified, we obtain a strongly connected digraph.
Consider the reverse process. We can choose any of the nodes to split. Then, we have the choice to add or not to add the edge from the source to the sink, which results in a factor of 2. Finally, consider that the sink inherits the label of the original node. Then, there are choices for the label of the additional source node.
Β
Single decorated tournaments
Since has smaller coefficients than , we can prove (with some handwaving) that
for every . This fact is also visible from Wright's recurrence
since and .
This means that it is a priori possible to construct an injection from the set of all decorated irreducible tournaments into the set of all strongly connected digraphs.
Remark (click to expand).
According to Khaydar, if we take for granted that strong digraphs are isomorphic to cycles of decorated irreducible tournaments, then Wright's recurrence can be explained combinatorially. But we cannot take this for granted yet.
Β
Question. Shall we absolutely require that our bijection turns single decorated irreducible tournaments into strong digraphs?
Β
Note that this property is not preserved by default if we use a "naive" bijection between graphs and tournaments. In this case, a single irreducible tournament can fall apart into several connected components. This means that we normally should not attempt to preserve this property while constructing the (in-)bijection (and this is useful information!).
However, if we just try to construct an injection, for fun and by hand, we can quickly realise this is not so obvious as it seems...
Β
Why constructing an injection is not obvious? Let us assume that in a naive way, every irreducible tournament is mapped into a strong digraph under some natural bijection. This is a dangerous path because such a bijection is probably label-permutation-invariant, but let us ignore this bad feeling for a moment. We also have edges of additional colour. Let us say that if an edge of additional colour is present, then we add a reverse edge.
There are 2 irreducible tournaments on 3 vertices; if we add edges of different colour, we get 8+8 = 16 irreducible decorated tournaments, because for every of the 2 irreducible tournaments we can add edges. However, if we interpret the presence of a second colour edge as adding a reverse edge, this results in only 8+7 = 15 strong digraphs, since a full strong digraph can be now obtained in two different ways.
Β
Other interpretations as reversing an edge in the presence of an edge of a different colour may result in breaking the strong connectivity property of a digraph.
Alternative characterisations of semi-strong digraphs
Proposition. A digraph is semi-strong if and only if for every of its nodes, its in-reachable set coincides with its out-reachable set.
Remark about isolated components (click to expand).
A node belongs to an isolated component if and only if its in-dfs component coincides with its out-dfs component.
Β
I don't see if it can be continued anywhere yet. In order to benefit from this definition, we need to find a way to mark in-reachable or out-reachable sets, but I don't see how.
Β
A new bijection: constraining Liskovets' decomposition
According to Liskovets,
We are particularly attracted here by the Hadamard product symbol because it represents a directed graph as a pair. Furthermore, every strongly connected digraph is also initially connected. It still, however, remains tricky for the sets, but we can define a set of initially connected digraphs as a set of digraphs where every weak component is reachable from the vertex with minimal label of this component.
Β
Now, we can make several drawings restricting this isomorphism to sets of strong digraphs.
Explanation
Two more examples include isomorphic digraphs, but due to differences in labels, the resulting underlying tournaments will be different, and not irreducible.
The resulting decorated tournaments look somewhat suspicious to me because I am unable to immediately decompose them into a naturally-looking sequence of decorated irreducible tournaments.
Summary. This bijection is nice and gives some insights, but it needs to be improved. The resulting underlying tournament should either be clearly decomposed into a sequence of irreducible decorated, or be itself irreducible decorated. The problem appears when we convert a connected graph into a tournament, and the outcome is rarely irreducible. Maybe it is possible to change the conversion algorithm at the last step? Maybe we could take into account both outgoing and ingoing edges with respect to 1?
Β
Playing with exploration processes
As a variation of the original method, we could modify the definition of the distance, which is equivalent to modifying the exploration process.
Β
In the directed version, we have which is the oriented distance from the node labelled 1 to the node labelled . However, there is also . An alternative approach would be to assign a new distance which is the shortest among these two
and resolving the conflicts by comparing the labels of the nodes.
This gives some interesting alternatives, but still leads to decorated tournaments that I cannot easily decompose into sequences.
Β
While the above strategy does not completely solve the problem, it feels like an improvement because we have a higher chance to obtain an irreducible tournament if we omit the decorations. This situation was almost never possible to obtain using the previous exploration approach.
Β
We can further challenge our imagination by doing such exotic things as maintaining two edge directions corresponding to two exploration processes, one starting at 1 inwards and another outwards. But having the "surplus" edges looks like a crucial idea which is lost in such an approach.
Β
A hint from the literature (click to expand).
It might be useful to take a look at different exploration processes used in the literature, particularly at the process of Goldschmidt and Stephenson from https://arxiv.org/pdf/1905.05397.pdf
Β
Β
Playing with conversions
Idea. What also seems a new idea is to alter the stage when a digraph obtained by an exploration process is converted into a tournament. We usually erase edge orientations because they can be deduced, and then assign orientations according to inequalities between node labels. This is not the only possible strategy, and maybe other conversion algorithms can provide better decomposition into sequences.
Β
Summary
So far, we tried the following strategies.
- Naive sequencing of decorated irreducible tournaments. This results in non-strongly connected components.
- DFS exploration process from vertex 1 to guide edge directions. Conversely, this approach starts from strong digraphs and aims at constructing sequences of irreducible tournaments. However, the strategies do not seem to lead to a natural decomposition yet.
- We listed some existing bijections between initially connected digraphs, digraphs with one source-like component, strong digraphs and connected graphs. They might turn to be helpful later.
Β
From a high-level overview, there are two important observations.
- Any exploration process on a set of SCC keeps a skeleton of edges, and adds a quasi-arbitrary subset of additional "surplus" edges. These surplus edges might very well be interpreted as the second part of the Hadamard product.
- Any irreducible tournament is a strong digraph, but it also contains a complete set of directed edges.
Β
Question. Is it possible to link the strong connectivity of tournaments with the strong connectivity of digraphs in some smart way?
Β
If it can be linked, it provides a new fresh combinatorial interpretation, because the classical decomposition of tournaments into sequences of irreducibles does not lead to edge removal.
Β
The idea with different conversions is worth further experimentation too.
Β
By using Liskovets' bijection in a more visual way, we can postulate two identities that both relate to irreducible tournaments and families of digraphs:
List of open questions
Note that bijections can be constructed using the un-pointing operation (just as in Liskovetsβ bijection). By using the unpointing, we can simplify cycles into sequences.
Prove the following bijections
Β
- or equivalently,
- or equivalently
Β
Note that and . So, 2, 4 are stronger versions. We are happy with any of the bijections if possible. Number 2 and 3 are very relevant.
Β
Already known bijections
- (Liskovetsβ bijection), equivalent to
- (left to a curious reader as an exercise)
(Click to see the proof)
is the EGF of graphs whose vertices are colored into one of two colors.
Add an extra vertex and connect it to vertices of the first color.
The result is equivalent to a graph with one marked vertex.
- (the same as the previous one)
- or equivalently,
- or equivalently
Β
Some new fancy bijections
- Now, the connected component bijection is reduced to
- in words, irreducible tournaments are isomorphic to bi-colored graphs whose connected components all have both colors
- can we prove it?
Β