July 31st, 2011

beartato phd

(no subject)

Imagine you have a graph with edges colored red, green, and blue where every vertex has exactly one red edge, one green edge, and one blue edge touching it. Here are some sketches of pieces of infinite such graphs that are "periodic in one dimension":

Here's a game you can play with such a graph. Pick a vertex, and move to the (unique) other vertex that is a red edge away. Now move along a green edge. Now blue. Now red, green, blue, etc.

Here's what happens with the three graphs above.

Every point in graph A leads to some kind of cycle. Every point in graph B flies off to infinity, but the ones that go to the left do so in a much more snakey convoluted sort of way. In graph C, there are vertices that fly off to the left and right forever, but also some vertices that go around in loops.

Speaking from an mathematical-aesthetic point of view, B feels to me the nicest of the three, since nothing ever gets trapped in loops, but it has the blemish that it's sort of asymmetric. the two chains of edges stretching across the top and bottom favor the association between the cyclic ordering red-green-blue and the rightward direction. Neither A nor C do this: they have a property that I can formalize like so.

Consider S_3, the permutations the three element set {R, G, B}. Say a local graph isomorphism between one graph and another is one that maps vertices to vertices and edges to edges in a color preserving way, and commutes with translations of the graph by one periodic repetition - this rules out flipping an entire infinite graph around.

Then both graphs A and C have the property
(*) For any odd permutation π1 ∈ S_3, there is an even permutation π0 ∈ S_3, such that π1π0 applied to the graph has a local isomorphism to the original.

and B does not.

Question: is there a connected periodic graph like these that has no cycles in the red-green-blue vertex moving game, and also has property (*)?



Here are some solutions to the Question, I think? I actually lost track of what my demanded symmetry property (*) really means, and I'm not sure if solution (1) has it or not, but I'm pretty sure solution (2) does, and looks nice and symmetric in any event:

Solution 1:

Solution 2:


I came up with a Solution 3, which has somewhat less convoluted paths:

And then a super simple Solution 4, which I don't know how I missed in the first place: It may not technically satisfy (*), but it has as many left-going as right-going paths: