Group Abstract Group Abstract

Message Boards Message Boards

Question about a quoted expression: {x,y} matches {x,x} ?

David Stephenson
Posted 5 years ago

Hello everyone,

I find that I have gotten myself stuck on what I think was a Stephen Wolfram quote, the specifics of which escape me, but which can be roughly paraphrased as:

"..and remember, {x,y} in the rule will match an {x,x} in the hypergraph.."

I can't locate exactly where I might have read that (I've looked}, but I seem to remember that it made little sense to me at the time, and makes even less sense to me now.

If an {x,y} in the rule will match an {x,x} in the hypergraph, then surely an {x,y,z} in the rule should match an {x,x,x} in the hypergraph. And by extension, also a {y,y,y}. And even a {z,z,y}.

I mean, doesn't that imply, if not explicitly state, that any string of vertices in the rule will match any string of vertices in the hypergraph? As in, WTF? (excuse my French)

So at the time, I dismissed it as a "Wolfram compatibility" issue, and continued investigating Wolfram Physics Model rules, hypergraphs, and multi-way graphs. But the problem cropped up again.

Specifically, there is a rule that Stephen Wolfram (et al) mentions in Section 4.1 "Recognizable Geometry", of his white paper entitled, "A Class of Models with the Potential to Represent Fundamental Physics".

As rules go, it's a beaut. When requisitely iterated, it is claimed to resemble a spatial "orbifold" - just what the doctor ordered for someone wanting to build a spatial Universe.

Only thing is, as far as I can tell, the rule doesn't seem to work. It dead ends before the second iteration.

The rule is: {{x,x,y},{x,z,u}}->{{u,u,v},{v,u,y},{z,y,v}}

If we start with the left-hand side as the Initial Condition, as is the custom, then the first iteration will produce the right-hand side (of course) - but only the right-hand side. So far, so good.

But then, where is the {{x,x,y},{x,z,u}} in {{u,u,v},{v,u,y},{z,y,v}} ??

There isn't one. It dead-ends.

If {{u,u,v},{v,u,y},{z,y,v}} is broken out into its component edges, then we can see that:

{u,u} is matched by the {x,x} edge in the rule, and

{u,v} is matched by the {x,y} edge in the rule, and

{v,u} is not matched, and

{u,y} is matched by the {x,z} edge in the rule, and

{z,y} is not matched, and

{y,v} is NOT matched by the {z,u} edge in the rule. - because the v is NOT unique.

There doesn't appear to be any other possible permutations.

So I guess my question is: If it is indeed true that the Wolfram Physics Model considers any {x,x} in the hypergraph to be "matched" by any {x,y} in the rule, then doesn't that essentially negate using unique symbols for vertices at all?

If not, then what exactly are the limitations of this particular.. methodology?

Any response would be appreciated.

BTW, just so you know, I don't currently own a copy of Mathematica. All my current investigations are done using C++ and T-SQL.

Thanks in advance.
POSTED BY: David Stephenson
9 Replies
Sort By:

I must disagree with your first point. When you subdivide an hypergraph into a set of 2-node edges, there is indeed loss of information.

Consider the hypergraph {{1,2,3}{3,4,5}} in the first picture. (Taken form here) hypergraph

It can be subdivided into the following set:

  • {1,2}
  • {2,3}
  • {3,4}
  • {4,5}

Consider instead the hypergraph {{1,2}{2,3}{3,4}{4,5}} in the second picture.

normal graph

Its decomposition is the same, but the two hypergraphs are not isomorphic, hence there was loss of information during the decomposition process. Also from a pattern matching perspective, it is impossible to determine if a pattern matches an hypergraph, when given only its decomposition. For example, the pattern {{x,y,z}{z,u,v}} matches the first graph but not the second one, while {{x,y}{y,z}{z,u}{u,v}} matches the second one but not the first.

Regarding you second point, I am not aware of any reason against your proposal, but I am not an expert of graph theory, nor I have knowledge of Wolfram's motives when he formulated the theory.

All I can say is that your idea seems good to me. I hope that someone with better knowledge on the subject will comment on that.
POSTED BY: Ruggero Valli
POSTED BY: Ruggero Valli
POSTED BY: David Stephenson
POSTED BY: Ruggero Valli

Yes, understanding is "tough" (haughty muffled chortle).. ;)

Because, according to rule 1:

  • the {x,y} edge in the {x,y,x} pattern matches the {u,v} in the target, and
  • the {y,x} edge in the {x,y,x} pattern matches the {v,w} in the target.

Thus, the two edges of the pattern hypergraph (and there are only two) have been matched.

Thus, according to rule 1: {x,y,x} should match {u,v,w}.
POSTED BY: David Stephenson

Hi,

I don't think that the example you made would work. If you find {x,x} on the LHS or RHS of a rule, it can only match to a node connected to itself, not to {u,v} where $u \neq v$. The reverse instead would work, meaning that if you find {u,v} in the LHS of a rule, it would match a {x,x} in the graph.

I can make some examples to clarify:

  1. {{x,y}}->{{x, y}, {y, z}} means: take two nodes (not necessarily different) connected by an arc. Create a third node and connect the second to the third.
  2. {{x,x}}->{{x, x}, {x, z}} means: take a node connected to itself. Create a second node and connect the first to the second.

Rule 1 can match anything that rule 2 can match, but the opposite is not true.

If what you say were true, the two rules would be exactly equivalent, and the way of writing the rules would be extremely redundant.

Actually you could write every LHS using only one letter: {{x,y,z}{y,y,z}} could be written equivalently as {{x,x,x}{x,x,x}} and they would match the same things!

BTW, I edited my previous comment with your amendment. Thank you. It is sad to keep confusing left and right :(
POSTED BY: Ruggero Valli

Actually, I wasn't trying to "make" anything in my last post, I simply asked a single question, to which you gave a wonderfully complete answer. So thank you for that. What fun.

So the pattern-matching rules for the LHS of a Wolfram-compatible rule, as we have previously discussed and agreed upon, are:

  1. {x,y} will match both a {u,u} and a {u,v}.
  2. {x,x} will only match a {u,u}.

So where does that leave the LHS interpretation of something like:

{x,y,x} ?

Specifically, will the above match {u,v,w} ?

  • If it does, then it breaks rule 2 (because u ≠ w), and
  • if it doesn't, then it breaks rule 1 ( {x,y}->{u,v}, {y,x}->{v,w} ).

A fundamental contradiction in the syntax.

Apparently.
POSTED BY: David Stephenson

Hello, sorry for the late reply, I hope it could still be of use.

I think that the problem with your reasoning stands on the assumption that the initial conditions used for the rule {{x,x,y},{x,z,u}}->{{u,u,v},{v,u,y},{z,y,v}} are exactly {{x,x,y},{x,z,u}}, with $x \neq y \neq z \neq u$, because this is not the simplest initial condition for that rule. I think (please correct me if I'm wrong on this) that the examples of rule evolution found on the catalogue always start from the simplest initial condition to which a rule is applicable.

To clarify my point, let me talk about the first rule shown on the page you linked (Recognizable Geometry), namely {{x, y}} -> {{y, z}, {z, x}}.

I copy here the first steps of evolution reported on the page. enter image description here

As you can see, the initial condition is one single node connected to itself. The single node is doing the double job of being both x and y at the same time. Obviously, this initial condition is the simplest to possible state to which the rule is applicable. So, in the first step there is only node 1 (labelled both x and y) connected to itself. The initial state can therefore be written as {{1,1}}.

You can apply the rule and see that in the right hand side there is a new node, z, which is different from node 1, let's call it node 2. Now {y,z} means there is an edge between node 1 and node 2, and {z,x} means there is an edge between node 2 and node 1. Hence the second step, as shown in the picture, can be written {{1,2}{2,1}}

Let's get now to the rule you asked of: {{x,x,y},{x,z,u}}->{{u,u,v},{v,u,y},{z,y,v}}.

You can see that the simplest initial condition is the one in which x,y,z and u are different labels for the very same node (let's call it node 1). The starting point will be the hypergraph {{1,1,1},{1,1,1}}. One node with two triple connections from the node to itself.

In the right hand side there is the new letter v, therefore a new node must appear, let's call it node 2. After applying the rule you get {{u,u,v},{v,u,y},{z,y,v}}, but $x=y=z=u=1$, so the second step looks like {{1,1,2}, {2,1,1}, {1,1,2}}.

Now you see that you can apply the rule again. Just stick the labels x and z to node 1 and y and u to node 2. With this substitution you can write the second step as, for example, {{x,x,y}, {y,x,x}, {x,z,u}}, to which you can apply the rule and go on with the computation.

To summarize, the way to apply the rules, as I understand it, is:

  1. The left hand side of a rule can be matched even if more than one label is attached to the same node.
  2. Initial conditions are chosen to be as simple as possible (e.g. one node connecting to itself is ok).
  3. If a new label appears on the right hand side, it must correspond to a new node.

I hope this helps
POSTED BY: Ruggero Valli

Thanks for the reply. I was beginning to think I was a ghost.

So will an {x,x} in the LHS of a Wolfram-compatible rule match a {u,v} in the target hypergraph, assuming that u is distinct from v?

BTW, your rule "3" requires amendment. To wit:

"If a new label appears on the left hand side" s/b "If a new label appears on the right hand side".

I have been called a grammar Nazi. Recently. Guilty as charged.
POSTED BY: David Stephenson
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard