So, last time, I kinda left you hanging on the hypergraphs, didn’t I?
I’ve been showing you graphs of nodes and edges, like this one:
where each edge connects two nodes, like this:
And now I’ve shown you hypergraphs of nodes and hyperedges, like this one:
where each edge connects three nodes, like this:
I asked, but didn’t answer, some pretty fundamental questions about hypergraphs.
Questions like: why does a hyperedge involve three nodes? why not one or four or seventeen nodes?
I’m not going to leave you hanging a moment longer. Here are some answers.
A hyperedge can connect any number of nodes: one, two, three, four, seventeen or any other number.
And a hypergraph can include any of these different kinds of hyperedge, or all of them.
Let’s take a look at what this means for Wolfram Physics... and at some of the beautiful hypergraphs it’ll allow us to generate!
An edge by any other name
Let’s start with some terminology.
Those edges that connect two nodes, I’m going to call binary edges:
And those hyperedges that connect three nodes, I’m going to call ternary edges:
From now on, I’m going to by using the words “edge” and “hyperedge” interchangeably.
A binary edge is just a special case of a hyperedge: it’s a hyperedge that connects two nodes.
And a ternary edge is just another special case of a hyperedge: it’s a hyperedge that connects three nodes.
You see what I did there? I referred to a ternary “edge”. Strictly speaking, I should have called it a ternary “hyperedge”. Instead, I used the word “edge”. It’s less sci-fi, but it’s shorter.
And, honestly, who cares? Whether I say “edge” or “hyperedge”, you know what I mean: it’s a relationship between two nodes, or three nodes, or any other number of nodes.
3... 2...
Let’s start with the number one.
If there can be ternary edges involving three nodes and binary edges involving two nodes, can there be unary edges involving only one node?
The numeric notation I introduced last time certainly allows for it: if we can write a ternary edge that involves nodes 1, 2 and 3 as:
{1, 2, 3}
and we can write a binary edge that involves nodes 1 and 2 as:
{1, 2}
then we can certainly write a unary edge that involves a single node 1 as:
{1}
How would we visualize this?
We’ve been visualizing that ternary edge {1, 2, 3} as two arrows and a transparent web between three dots for the nodes:
and we’ve been visualizing that binary edge {1, 2} as an arrow between two dots for the nodes:
so how do we visualize the unary edge {1}?
Well, it’s entirely up to us. Remember that the way I’ve been visualizing binary and ternary edges is arbitrary. I’ve chosen to use dots, arrows and webs:
but I might equally have chosen to use crabs, snakes and bats:
How we visualize a unary edge is arbitrary, too. I’m going to choose to visualize it as a circle around the one node it involves:
Sure, it might have been more fun to visualize the node as a crab and the unary edge as a turtle:
but let’s keep things simple and visualize that unary edge {1} as a circle around the dot for the node:
One is a lonely number
It has to be said that universes of unary nodes aren’t very exciting.
Take this rule:
{x} → {x}, {y}
To apply the rule, we find a node with a unary edge and create a new node with a new unary edge.
No prizes for guessing what happens. If we apply the rule over and over again, it simply creates more and more nodes, each with a unary edge:
→ 
→ 
→ 
→
This is a lonely universe. No node is connected to any other node. That’s no surprise, given that a unary edge involves only one node. To connect one node to another, you need a binary edge.
So unary edges can’t play a role in a complex, connected universe like our own, right?
Mix ‘n’ match
Well, not so fast.
Let’s try a rule that involves both unary and ternary edges:
{x} → {x, y, z}, {y}, {z}
To apply this rule, we find a node with a unary edge, delete that unary edge, create a new ternary edge from that node to two new nodes, and create unary edges for those two new nodes.
Apply this rule over and over, and a branching universe emerges:
You can see how the unary edges do play a role in this more complex, connected universe: the rule will only match a node if it has a unary edge, so those unary edges matter.
This hypergraph includes a mix of hyperedges with different -arities: it includes both unary edges and ternary edges.
Now let’s try a rule that involves binary and ternary edges:
{x, y}, {y, z, u} → {y, x, v}, {w, v, u}, {w, y}, {v, z}
This is a complex rule, but still, I’m going to try to describe it in words. To apply the rule, we find a binary edge from one node, node 1, to another node, node 2, and a ternary edge from that second node, node 2, to two other nodes, nodes 3 and 4; we delete both of these edges; we create two new nodes, nodes 5 and 6; we create two new binary edges, from node 5 to node 3 and from node 6 to node 2; and, finally, we create two new ternary edges, from node 2 to node 1 to node 5, and from node 6 to node 5 to node 4.
And that’s such a mouthful that you might want to see how this rule can be written using the algebraic notation I introduced last time. Take a look at the x’s, y’s and z’s under the graphical representation of the rule above. From now on, I’ll be writing out all rules using this notation, for the algebraically minded.
Apply this rule over and over, and a boxy, branching universe emerges:
Again, this hypergraph includes a mix of hyperedges with different -arities: it includes both binary edges and ternary edges.
Anything goes
You can see where I’m going here.
To repeat the answers I gave above:
A hyperedge can connect any number of nodes: one, two, three, four, seventeen or any other number.
And a hypergraph can include any of these different kinds of hyperedge, or all of them.
Anything goes.
If an edge that involves one node is called a unary edge, an edge that involves two nodes is called a binary edge, and an edge that involves three nodes is called a ternary edge, what do you call an edge that involves an arbitrary number, k, nodes?
A k-ary edge, of course.
You can imagine how we might write a quaternary (or 4-ary) edge as {1, 2, 3, 4} and a quinary (or 5-ary) edge as {1, 2, 3, 4, 5}. I’ll leave it to your imagination as to what we might use beyond dots, circles, arrows and webs (or crabs, turtles, snakes and bats) to visualize these higher -arity edges.
The infinite haystack
So now we’ve generalized Wolfram’s hypergraphs to include hyperedges connecting any number of nodes.
That’s good, right?
Well... I’m not so sure.
Back when we were simulating Wolfram Physics using graphs, we had our work cut out for us determining which rule or rules might be applied to the edges of those graphs to yield our universe. Back in that age of innocence, all those edges were binary edges.
Now that we’re simulating Wolfram Physics using hypergraphs, we really have our work cut out for us determining which rule or rules might be applied to the hyperedges of those hypergraphs to yield our universe. Now, those hyperedges might be unary, binary, ternary or k-ary, where k might be any positive integer.
It seems to me that the number of rules we’ll need to explore to find the rule or rules we’re looking for just got infinitely bigger.