Succinct represention of a condensed complete directed graph

Question

I'm working on research in multi-agent reinforcement learning, and in the experiments that I'm running now, my six agents are forming a social order. I've been analyzing these experiments for a while, and I've had the need to express each social order that develops in a succinct way that's easy to read.

Each social order is basically a complete directed graph between 6 nodes, marked by integers between 0 and 5.

While I could represent these graphs as a list of edges or an edge matrix, that will quickly become difficult to read. I settled on the following convention:

# Graph with no cycles:
0 => 4 => 1 => 2 => 5 => 3

# Graph with one 3-cycle:
(1 -> 2 -> 3 -> 1) => 4 => 0 => 5

# Graph with two 3-cycles:
(1 -> 2 -> 3 -> 1) => (0 -> 4 -> 5 -> 0)

# Graph with one 5-cycle:
0 => (1 -> 3 -> 2 -> 1 -> 4 -> 2 | 4 -> 3) => 5

I wrote code that condenses the graph and then displays the SCCs in parentheses. I also wrote the reverse logic, that takes such a textual representation and builds a graph out of it.

I find this representation easy to read, and with gentle modifications it could be used for plotting such graphs.

I have little background in graph theory. Is there already a notation that does what I'm doing here? How do researchers in graph theory notate such graphs?

Answer 1

I don't think there is existing notation of this type, for two reasons.

1. Tournament (i.e. complete directed graphs) are not well-studied - understudied, in my opinion. Compare, for example, what is known for Ramsey's theorem for $2$-colored graphs and the tiny subsection of that article devoted to the corresponding problem for transitive subtournaments of large tournaments - even though that version of the problem is in many ways far more elegant.
2. There is a limited "sweet spot" where this notation makes sense and is required. Too few vertices, and you might as well list out all the edges. But for large $n$, almost all $n$-vertex tournament are strongly connected, and so we don't gain anything from this notation.

The notation that graph theorists would adopt here varies.

For internal computer use that humans don't have to parse, I would use something like the digraph6 format. (Essentially, this is a base64 encoding of the adjacency matrix.)

When making the result human-readable, it's common to give the small graphs names. Again, because tournaments are not well-studied, I don't think there's standard names for small tournaments - but for small ordinary graphs, there is notation like $P_2, P_3, P_4, \dots$ for paths, $C_3, C_4, \dots$ for cycles, $K_1, K_2, K_3, K_4, \dots$ for complete graphs, and so forth. In your case, we would want to name the strongly connected tournaments on $6$ or fewer vertices:

• There is only one option for $3$ vertices, which we could call $C_3$ because it is a directed cycle.
• There is also only one strongly connected $4$-vertex tournament. No name, as far as I know; we could make up $ST_4$ (for "strong tournament").
• There are six $5$-vertex strongly connected tournaments. The lazy way out would be to name these $S_{5,1}, \dots, S_{5,6}$ in some fixed order. Some of these have special names; for example, there's $PT_5$, the Paley tournament on $5$ vertices. In principle, all of them could be given more distinguishing names, but I don't know if they currently have them.
• There are $35$ strongly connected $6$-vertex tournaments. Again, we could call them $ST_{6,1}$ through $ST_{6,35}$...

These are isomorphism classes, so maybe we'd write something like $C_3(0,4,5)$ for the directed cycle with vertices $0$, $4$, and $5$. Already, this is not standard notation, and it would be even less standard if we represented your graphs as something like "$C_3(1,2,3) \to C_3(0,4,5)$" or "$0 \to ST_4(1,4,2,3) \to 5$". But that wouldn't be an unreasonable approach.

This has disadvantages - especially when we get to strongly connected components with $5+$ vertices, there's a lookup step where we need to find out what $ST_{5,6}$ actually is, compared to listing out its edges. The advantage is that we can clearly see when two such representations are isomorphic (whether that's important depends on how much graph theory you want to do with them later). If we just want the isomorphism classes, we can be even more concise and write notation like $C_3 \to C_3$.

(Relatedly, the notation $TT_n$ is reasonably common for the transitive tournament on $n$ vertices.)