We can define an undirected graph $G = (V,E)$ as a binary relation $R_2$ on $V$, where $x R_2 y$ and $y R_2 x$ when $\{x,y\}\in E$.
When we draw these graphs, they seem almost unreasonably useful in visualising all sorts of data, and relationships between data, across a whole spectrum of applications.
My question is, is there a similar use for a graph that is defined by a ternary relation on the set $V$? That is, where a binary relation graph has $x$ and $y$ being connected by a line segment when $\{x,y\} \in R_2$, a ternary relation graph would have $x$, $y$ and $z$ connected by a planar triangle when $\{x,y,z\}\in R_3$ ?
I have tried to find any information at all about this, but I have had no luck. I can't possibly be the first person to ever think about it, so I have to assume that it is not useful at all – and this is why nobody uses them.
There are three arguments against the idea that I can think of:
- Drawing a graph where $\{x,y,z\} \in R_3$ is aesthetically equivalent to one where $\{\{x,y\},\{x,z\},\{y,z\}\} \subseteq R_2$, so you don't really get any extra information:
This is a fair point, and ultimately this is probably how we would have to physically draw it anyway, as we draw lines from point a to point b. But that is not really my question. My question is more, is there a use for visualising ternary relations as planar triangles connecting points at all?
- You can't really compare 3 things at once, so there is no use to the representation:
You can compare three things at once, but you need to use a partial order like $x \succeq y \succeq z$, and doing so is really just doing 3 pairwise comparisons. But what about representing 3-place predicates, such as the English verb "to give"? Alice gives the ball to Bob is a three-way relationship that can't really be represented by a binary relation graph. (But then neither could you represent that exact relationship with an undirected ternary relation graph.. but you can still represent that Alice, Bob and the ball have some mutual relationship that you cant really with a binary relation graph)
- Binary relation graphs are so useful to us because we inhabit a world with 3 spatial dimensions, so we can observe all the information at once by abstracting the information to 2 dimensions; for ternary relation graphs to be useful, we would have to inhabit 4 spatial dimensions, so the information can be abstracted to 3:
This one is grasping a bit, and I know binary relations aren't restricted to 2D graphs, but the relation information in $R_2$ is essentially contained by 1D line segments, whereas the information in $R_3$ is contained by 2D planar triangles; so in much the same as you can eliminate crossing in a 2D planar graph by embedding it in a 3D space, I would imagine you can eliminate crossing in a 3D ternary relation graph by embedding it in a 4D space. And maybe this has some bearing on how easy it is for us to absorb information from it?
Anyway, I tried drawing some, and it seemed weird and didn't seem intuitive in the same way that binary relation graphs are. However, I am not sure if that is just because I am not used to it, or I didn't draw them in the correct way, or they just are not useful at all. Does anyone else have any knowledge of something like this being used for anything?
Note: I have purposefully kept this to undirected graphs only, because I didn't want to complicate things by having to define what "arrows" look like for these planar triangles (I guess in the case of Alice gives the ball to Bob you could have $(Alice,Bob,the\ ball) \in R_3$ and one corner of the triangle being the "head" of the arrrow, that the other two elements "go to"?). But binary undirected graphs are useful enough without considering the case of directed graphs, so my question about the usefulness of their ternary counterpart still stands.
EDIT:
I had a go at trying to draw an example, and this is what I came up with (updated version to show planar triangles instead of just edges):
This is a representation of the ternary relation, based on the English verb "to give" and it is on the set $\{Alice, John, George, Claire, ball, pen\}$ with each element being represented by its initial.
The scenario it is supposed to be representing is:
Alice gives the ball to John
John gives the pen to George
Claire gives the ball to George
George gives the pen to Alice
Alice gives the pen to Claire
I had a go at trying to make it a directed graph. The way it works is the undirected edges connect the object and the person who gives it, and they both point to the person who is receiving the gift.
I dunno, it all seems a bit of a mess to me, but I can't tell if that is because I am not used to looking at information in that way, or I haven't drawn it properly, or because there are too many crossings and it would need to be embedded in a 4 dimensional space to allow the relationships to be seen more clearly.
Anyway, I tried….
EDIT EDIT:
One further question that this poses, is what would $(x,x,x)\in R_3$ or $(x,x,y) \in R_3$ look like? I suppose if $(x,x) \in R_2$ is a self loop, then $(x,x,x) \in R_3$ would also be a self loop. Would that mean that $(x,x,y) \in R_3$ is a regular directed arc?
If we define the directed case to be $(x,y,z) \in R_3$ means $x$ gives $y$ to $z$ (as in there is an undirected edge between $x$ and $y$, and two directed edges $(x,z)$ and $(y,z)$) then $(x,x,y) \in R_3$ would be a single directed edge from $x$ to $y$, $(y,x,x) \in R_3$ would be a single directed edge from $y$ to $x$ and $(x,y,x) \in R_3$ would be an undirected edge between $x$ and $y$?
I guess at that point it is just up to whoever is defining the schema to determine…
Best Answer
The generalization of graph that you are describing is called a hypergraph. If all hyperedges have the same cardinality $k$, it is a $k$-uniform hypergraph. Ternary corresponds to a $3$-uniform hypergraph.