Re: [math-fun] Aknother knight's surprise?
Oh, sorry, I didn't see that you needed it to be an embedding. It can't be embedded on the torus, since it has 36 vertices, 144 edges and an Euler characteristic of at most: 36 - 144 + 96 = -12 So, if you are to embed it on a surface without crossings, you'll need to have at least seven holes. Sincerely, Adam P. Goucher
----- Original Message ----- From: Fred Lunnon Sent: 04/15/14 11:31 PM To: math-fun Subject: Re: [math-fun] Aknother knight's surprise?
But why is the result an embedding? WFL
On 4/15/14, Adam P. Goucher <apgoucher@gmx.com> wrote:
[...]
Whichever, is there now some way to reverse the previous identification, and lift the embedding back to 36 vertices?
Yes! You implied the existence of such a procedure yourself, when you said "vertices opposite across the torus have all neighbours in common".
Specifically, for every vertex v in the 18-vertex graph, create vertices v_1 and v_2 in the new graph. Then connect u_i with v_j in the 36-vertex graph iff u is connected to v in the 18-vertex graph.
The 36-vertex graph should have 2^18 times more symmetries than the 18-vertex graph, given by the wreath product C_2 wr G, where G is the automorphism group of the 18-vertex graph (as a subgroup of S_18) -- the one you claim (probably correctly) has order 144.
Sincerely,
Adam P. Goucher
Fred Lunnon
On 4/15/14, Fred Lunnon <fred.lunnon@gmail.com> wrote:
On 4/15/14, Fred Lunnon <fred.lunnon@gmail.com> wrote:
I have posted a diagram, showing as much of the symmetry of this graph as planar representation allows, at https://www.dropbox.com/s/aeea6bqlrt23tck/semi_6x6.png Note the 4-fold diagonal coincidences --- whereby hangs another tale entirely!
Ugh --- grotesquely aliased lines --- see instead https://www.dropbox.com/s/8b0stotr8343mq2/semi_6x6.pdf
The external edges obviously form a tour (closed Hamiltonian path); the remaining diagonals also form a tour, isomorphic to the first.
Fred Lunnon [15/04/14]
On 4/14/14, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Since you dispatched 4x4 so readily, perhaps you can manage something about the graph genus 6x6 knight moves on a torus instead?
In the 4x4 case the vertices had valency 4 instead of 8 . The 6x6 case degenerates as well, less predictably: vertices opposite across the torus have all neighbours in common; identification yields 18 vertices and 36 edges and valency 4 immersed on a Klein bottle. The symmetry group has order 144 .
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 4/15/14, Adam P. Goucher <apgoucher@gmx.com> wrote:
Oh, sorry, I didn't see that you needed it to be an embedding. It can't be embedded on the torus, since it has 36 vertices, 144 edges and an Euler characteristic of at most:
36 - 144 + 96 = -12
So, if you are to embed it on a surface without crossings, you'll need to have at least seven holes.
Whoa! ... where does your 96 come from? WFL __________ There exist two distinct planar immersions of the smaller graph with maximal (D_6) symmetry: to accompany the diagram of the first at https://www.dropbox.com/s/8b0stotr8343mq2/semi_6x6.pdf I have posted the second at https://www.dropbox.com/s/gyispnh717ayz86/semi0_6x6.pdf In the latter case, the complement of the exterior tour splits into 3+1 smaller circuits, diagonals skipping 3 unequal intervals (rather than 2). Less elegant perhaps; but 4-circuit faces and 6-circuit zones are more readily discernable. Fred Lunnon
----- Original Message ----- From: Fred Lunnon Sent: 04/15/14 11:31 PM To: math-fun Subject: Re: [math-fun] Aknother knight's surprise?
But why is the result an embedding? WFL
On 4/15/14, Adam P. Goucher <apgoucher@gmx.com> wrote:
[...]
Whichever, is there now some way to reverse the previous identification, and lift the embedding back to 36 vertices?
Yes! You implied the existence of such a procedure yourself, when you said "vertices opposite across the torus have all neighbours in common".
Specifically, for every vertex v in the 18-vertex graph, create vertices v_1 and v_2 in the new graph. Then connect u_i with v_j in the 36-vertex graph iff u is connected to v in the 18-vertex graph.
The 36-vertex graph should have 2^18 times more symmetries than the 18-vertex graph, given by the wreath product C_2 wr G, where G is the automorphism group of the 18-vertex graph (as a subgroup of S_18) -- the one you claim (probably correctly) has order 144.
Sincerely,
Adam P. Goucher
Fred Lunnon
On 4/15/14, Fred Lunnon <fred.lunnon@gmail.com> wrote:
On 4/15/14, Fred Lunnon <fred.lunnon@gmail.com> wrote:
I have posted a diagram, showing as much of the symmetry of this graph as planar representation allows, at https://www.dropbox.com/s/aeea6bqlrt23tck/semi_6x6.png Note the 4-fold diagonal coincidences --- whereby hangs another tale entirely!
Ugh --- grotesquely aliased lines --- see instead https://www.dropbox.com/s/8b0stotr8343mq2/semi_6x6.pdf
The external edges obviously form a tour (closed Hamiltonian path); the remaining diagonals also form a tour, isomorphic to the first.
Fred Lunnon [15/04/14]
On 4/14/14, Fred Lunnon <fred.lunnon@gmail.com> wrote: > Since you dispatched 4x4 so readily, perhaps you can manage > something > about the graph genus 6x6 knight moves on a torus instead? > > In the 4x4 case the vertices had valency 4 instead of 8 . > The 6x6 case degenerates as well, less predictably: vertices > opposite > across the torus have all neighbours in common; identification > yields > 18 vertices and 36 edges and valency 4 immersed on a Klein bottle. > The symmetry group has order 144 . > > Fred Lunnon
As conjectured earlier, the smaller graph (knight moves on 6x6 torus, with opposite vertices identified) is embeddable on the torus. With graph vertices represented by board coordinates [0, 0] -- [2, 5] mod [3, 6] , and moves by lattice edges, the toric embedding is given by grid diagram 02 23 11 05 20 14 02 10 04 25 13 01 22 10 24 12 00 21 15 03 24 05 20 14 02 23 11 05 the extra row and column indicating edge matching. Opposite length-3 edges are directly identified; opposite length-6 edges are identified with a shift of 3 units, angular rotation through \pi. Curiously, successive points in row-major order are separated by knight moves on the grid diagram above, except at 05--10 and 15--20 where end-of-row disrupts the pattern! Fred Lunnon On 4/16/14, Fred Lunnon <fred.lunnon@gmail.com> wrote:
On 4/15/14, Adam P. Goucher <apgoucher@gmx.com> wrote:
Oh, sorry, I didn't see that you needed it to be an embedding. It can't be embedded on the torus, since it has 36 vertices, 144 edges and an Euler characteristic of at most:
36 - 144 + 96 = -12
So, if you are to embed it on a surface without crossings, you'll need to have at least seven holes.
Whoa! ... where does your 96 come from? WFL __________
There exist two distinct planar immersions of the smaller graph with maximal (D_6) symmetry: to accompany the diagram of the first at https://www.dropbox.com/s/8b0stotr8343mq2/semi_6x6.pdf I have posted the second at https://www.dropbox.com/s/gyispnh717ayz86/semi0_6x6.pdf
In the latter case, the complement of the exterior tour splits into 3+1 smaller circuits, diagonals skipping 3 unequal intervals (rather than 2). Less elegant perhaps; but 4-circuit faces and 6-circuit zones are more readily discernable.
Fred Lunnon
----- Original Message ----- From: Fred Lunnon Sent: 04/15/14 11:31 PM To: math-fun Subject: Re: [math-fun] Aknother knight's surprise?
But why is the result an embedding? WFL
On 4/15/14, Adam P. Goucher <apgoucher@gmx.com> wrote:
[...]
Whichever, is there now some way to reverse the previous identification, and lift the embedding back to 36 vertices?
Yes! You implied the existence of such a procedure yourself, when you said "vertices opposite across the torus have all neighbours in common".
Specifically, for every vertex v in the 18-vertex graph, create vertices v_1 and v_2 in the new graph. Then connect u_i with v_j in the 36-vertex graph iff u is connected to v in the 18-vertex graph.
The 36-vertex graph should have 2^18 times more symmetries than the 18-vertex graph, given by the wreath product C_2 wr G, where G is the automorphism group of the 18-vertex graph (as a subgroup of S_18) -- the one you claim (probably correctly) has order 144.
Sincerely,
Adam P. Goucher
Fred Lunnon
On 4/15/14, Fred Lunnon <fred.lunnon@gmail.com> wrote:
On 4/15/14, Fred Lunnon <fred.lunnon@gmail.com> wrote: > I have posted a diagram, showing as much of the symmetry of this > graph > as > planar representation allows, at > https://www.dropbox.com/s/aeea6bqlrt23tck/semi_6x6.png > Note the 4-fold diagonal coincidences --- whereby hangs another > tale > entirely!
Ugh --- grotesquely aliased lines --- see instead https://www.dropbox.com/s/8b0stotr8343mq2/semi_6x6.pdf
The external edges obviously form a tour (closed Hamiltonian path); the remaining diagonals also form a tour, isomorphic to the first.
Fred Lunnon [15/04/14]
> On 4/14/14, Fred Lunnon <fred.lunnon@gmail.com> wrote: >> Since you dispatched 4x4 so readily, perhaps you can manage >> something >> about the graph genus 6x6 knight moves on a torus instead? >> >> In the 4x4 case the vertices had valency 4 instead of 8 . >> The 6x6 case degenerates as well, less predictably: vertices >> opposite >> across the torus have all neighbours in common; identification >> yields >> 18 vertices and 36 edges and valency 4 immersed on a Klein >> bottle. >> The symmetry group has order 144 . >> >> Fred Lunnon
participants (2)
-
Adam P. Goucher -
Fred Lunnon