Skip to content
Little GolemMake your next move.

Search for small alternating planar graphs

Public forum discussion.

General

#51 · Ingo Althofer

9 Feb 2008

The definition of "alternating planar graphs"

was motivated by "alternating tilings", which

I found in a book of Karl Scherer. Especially

I love his small solutions for "squaring the square".

Last summer I used Scherer's 21-tiling to

design a variant of "EinStein wurfelt nicht"

without numbers on the stones. Look at

http://www.althofer.de/scherers-race.html

for more details.

Ingo.

PS: One of my plans with alternating planar graphs is

to design nice games for them. In this respect

the self-duality of Frank Schneider's graph is a

great pleasure: player 1 may move on the vertices, and

player 2 on the faces ... (the game is not complete, yet).

#52 · Tasmanian Devil

9 Feb 2008

> A conjecture:

> Let p(i,j) be the number of (i,j)-combinations.

> Then it might hold that

> p(i,j) = p(j,i) for all i,j in 3,4,5.

This is true. We have p(3, j) = v3 and p(i, 3) = f3 for each i, j, and we know that v3 = f3. So it remains to prove that p(4, 5) = p(5, 4). But p(4, 5) = 2b3 + b4 + 2b5 and p(5, 4) = 2a3 + a4 + 2a5, so it suffices to verify that ai = bi for every i, and this is immediate from the proof.

#53 · Ingo Althofer

9 Feb 2008

Hello Jan,

> conjecture: ... p(i,j) = p(j,i) for all i,j in 3,4,5.

> This is true. We have p(3, j) = v3 and p(i, 3) = f3

> for each i, j, and we know that v3 = f3. So it remains

> to prove that p(4, 5) = p(5, 4). But p(4, 5) =

> 2b3 + b4 + 2b5 and p(5, 4) = 2a3 + a4 + 2a5,

> so it suffices to verify that ai = bi for every i, and

> this is immediate from the proof.

Thanks for the proof. It is amazing that it is so short.

Meditating crossway: Would you see a chance that (all) other

steps of generalisation also have such short proofs?

Or even more ambitious:

Having a general way (proof by induction) to get from

"identical number of local structures of diameter t"

to

"identical number of local structures of diameter t+1" (or t + 1/2)

would give a Theorem about self-duality for (3,4,5)-alternating graphs.

The next level would be to look at pattern, consisting of

one face and all vertex degrees (in fixed order) around it -

and to prove equality of this number with "one vertex + all

faces around it"...

Ingo.

PS: Indipendently I will ask Frank Schneider to modify his program

to find more (3,4,5)-graphs...

#54 · Tasmanian Devil

9 Feb 2008

> PS: Indipendently I will ask Frank Schneider to modify his program

> to find more (3,4,5)-graphs...

That would be very interesting!

#55 · wccanard

9 Feb 2008

@ingo: the proof is only so short because TD has done most of the work in the 1st proof :-) Re: induction, it's not immediately clear to me what the correct "next step" is from the local structures---the local structures seem to me to be not entirely local, in some sense: they depend on a vertex in the graph and also a polygon, and the polygon is in some sense not very local; it's just local in the dual graph. Can you formulate a more precise proposal for the next step of the induction after TD's local structures? Should we consider two vertices and two faces perhaps? i.e. an edge? Perhaps that's the next question; an ({a,b},{i,j}) edge being an edge between two vertices of degrees a and b and being the boundary of two polygons of sides i and j? Does the number of ({a,b},{i,j}) equal the number of ({i,j},{a,b})?

#56 · Tasmanian Devil

9 Feb 2008

The proof relies very heavily on the fact that each vertex of degree 3 must belong to a triangle, a quadrandgle and a pentagon (and the dual fact). Once we try to go further, things get more complicated very quickly, so I am not too optimistic about proving more.

#57 · wccanard

9 Feb 2008

Right: somehow you have these local pieces of data which you can sum over, and Euler's formula too, and if you then put severe conditions on the situation (e.g. all vertices, faces have degree 3,4,5) then you might hope that you happen to have "nearly as many equations as variables" so you can hope to draw concrete conclusions. And the moment you move away from this very "tight" situation, e.g. allow hexagons, or try and understand which (3,5) situations are connected to (4,5) situations, suddenly you seem to have far more variables than equations and it becomes hard to say anything concrete other than big equalities involving lots of variables at once. My gut feeling is that non-self-dual (3,4,5) graphs will exist and that again computer search is perhaps a very powerful tool for finding them. I am a number theorist in real life and I've certainly found examples of explicit phenomena involving elliptic curves by grepping through tables of elliptic curves; given that elliptic curves are in some sense more complicated than planar graphs, surely there must be standard tables of planar graphs which are publically and electronically available, and that one could just search through?

#58 · Tasmanian Devil

9 Feb 2008

The problem is that there are too many planar graphs. For example, there are 6,415,851,530,241 polyhedra (3-connected simple planar graphs) with 17 vertices.

#59 · wccanard

9 Feb 2008

Aah, I see! And they're all non-isomorphic? :-)

#60 · Ingo Althofer

10 Feb 2008

Frank Schneider has found "lots" of (3,4,5)-alternating

graphs with his program, for instance:

Solution with 20 vertices.

0: 1, 2, 3, 18,

1: 0, 2, 5, 13, 14,

2: 0, 1, 15,

3: 0, 4, 7, 18, 19,

4: 3, 5, 6,

5: 1, 4, 6, 12,

6: 4, 5, 7, 8, 10,

7: 3, 6, 8, 19,

8: 6, 7, 9,

9: 8, 10, 11, 17,

10: 6, 9, 11,

11: 9, 10, 12, 13, 16,

12: 5, 11, 13,

13: 1, 11, 12, 14,

14: 1, 13, 15,

15: 2, 14, 16, 17,

16: 11, 15, 17,

17: 9, 15, 16, 18, 19,

18: 0, 3, 17,

19: 3, 7, 17,

Border: 19 (3), 7 (4), 8 (3), 9 (4), 17 (5),

Faces:

1: 0, 1, 2,

2: 0, 3, 4, 5, 1,

3: 4, 6, 5,

4: 3, 7, 6, 4,

5: 7, 8, 6,

6: 8, 9, 10, 6,

7: 9, 11, 10,

8: 11, 12, 5, 6, 10,

9: 12, 13, 1, 5,

10: 11, 13, 12,

11: 1, 14, 15, 2,

12: 13, 14, 1,

13: 11, 16, 15, 14, 13,

14: 16, 17, 15,

15: 9, 17, 16, 11,

16: 0, 18, 3,

17: 17, 18, 0, 2, 15,

18: 3, 19, 7,

19: 17, 19, 3, 18,

Number of nodes and faces with degree n:

3: 9 9

4: 6 6

5: 5 5

\*\*\*******************************

Solution with 21 vertices

0: 1, 2, 3, 9,

1: 0, 2, 4,

2: 0, 1, 6, 8, 14,

3: 0, 4, 9,

4: 1, 3, 5, 11, 13,

5: 4, 6, 7, 13,

6: 2, 5, 7,

7: 5, 6, 8, 17, 18,

8: 2, 7, 14,

9: 0, 3, 10, 15, 20,

10: 9, 11, 12, 20,

11: 4, 10, 12,

12: 10, 11, 13, 18, 19,

13: 4, 5, 12,

14: 2, 8, 15, 16,

15: 9, 14, 16,

16: 14, 15, 17, 19, 20,

17: 7, 16, 18, 19,

18: 7, 12, 17,

19: 12, 16, 17,

20: 9, 10, 16,

Border: 10 (4), 12 (5), 19 (3), 16 (5), 20 (3),

Faces:

1: 0, 1, 2,

2: 0, 3, 4, 1,

3: 4, 5, 6, 2, 1,

4: 5, 7, 6,

5: 7, 8, 2, 6,

6: 0, 9, 3,

7: 9, 10, 11, 4, 3,

8: 10, 12, 11,

9: 12, 13, 4, 11,

10: 13, 5, 4,

11: 8, 14, 2,

12: 14, 15, 9, 0, 2,

13: 14, 16, 15,

14: 7, 17, 16, 14, 8,

15: 7, 18, 17,

16: 12, 18, 7, 5, 13,

17: 17, 19, 16,

18: 12, 19, 17, 18,

19: 16, 20, 9, 15,

20: 20, 10, 9,

Number of nodes and faces with degree n:

3: 10 10

4: 5 5

5: 6 6

\*\*\****************************************

Solution with 22 vertices

0: 1, 2, 3, 9,

1: 0, 2, 4,

2: 0, 1, 6, 8, 11,

3: 0, 4, 9, 14, 15,

4: 1, 3, 5, 17,

5: 4, 6, 7, 17, 18,

6: 2, 5, 7,

7: 5, 6, 8, 10,

8: 2, 7, 10,

9: 0, 3, 11,

10: 7, 8, 12, 19, 20,

11: 2, 9, 12, 13,

12: 10, 11, 13,

13: 11, 12, 14, 20, 21,

14: 3, 13, 15, 21,

15: 3, 14, 16,

16: 15, 17, 18, 19, 21,

17: 4, 5, 16,

18: 5, 16, 19,

19: 10, 16, 18, 20,

20: 10, 13, 19,

21: 13, 14, 16,

Border: 16 (5), 19 (4), 20 (3), 13 (5), 21 (3),

Faces:

1: 0, 1, 2,

2: 0, 3, 4, 1,

3: 4, 5, 6, 2, 1,

4: 5, 7, 6,

5: 7, 8, 2, 6,

6: 0, 9, 3,

7: 7, 10, 8,

8: 2, 11, 9, 0,

9: 10, 12, 11, 2, 8,

10: 12, 13, 11,

11: 13, 14, 3, 9, 11,

12: 14, 15, 3,

13: 15, 16, 17, 4, 3,

14: 17, 5, 4,

15: 16, 18, 5, 17,

16: 18, 19, 10, 7, 5,

17: 16, 19, 18,

18: 10, 20, 13, 12,

19: 13, 21, 14,

20: 19, 20, 10,

21: 21, 16, 15, 14,

Number of nodes and faces with degree n:

3: 10 10

4: 6 6

5: 6 6

\*\*\****************************************

Solution with 23 vertices

0: 1, 2, 3, 9,

1: 0, 2, 4,

2: 0, 1, 6, 8, 11,

3: 0, 4, 9, 14, 15,

4: 1, 3, 5, 18,

5: 4, 6, 7, 19, 20,

6: 2, 5, 7,

7: 5, 6, 8, 10,

8: 2, 7, 10,

9: 0, 3, 11,

10: 7, 8, 12, 21, 22,

11: 2, 9, 12, 13,

12: 10, 11, 13,

13: 11, 12, 14, 16, 22,

14: 3, 13, 15,

15: 3, 14, 16, 17,

16: 13, 15, 17,

17: 15, 16, 18, 19, 21,

18: 4, 17, 19,

19: 5, 17, 18, 20,

20: 5, 19, 21,

21: 10, 17, 20, 22,

22: 10, 13, 21,

Border: 21 (4), 10 (5), 22 (3),

Faces:

1: 0, 1, 2,

2: 0, 3, 4, 1,

3: 4, 5, 6, 2, 1,

4: 5, 7, 6,

5: 7, 8, 2, 6,

6: 0, 9, 3,

7: 7, 10, 8,

8: 2, 11, 9, 0,

9: 10, 12, 11, 2, 8,

10: 12, 13, 11,

11: 13, 14, 3, 9, 11,

12: 14, 15, 3,

13: 13, 16, 15, 14,

14: 16, 17, 15,

15: 17, 18, 4, 3, 15,

16: 18, 19, 5, 4,

17: 17, 19, 18,

18: 19, 20, 5,

19: 20, 21, 10, 7, 5,

20: 17, 21, 20, 19,

21: 10, 22, 13, 12,

22: 22, 21, 17, 16, 13,

Number of nodes and faces with degree n:

3: 10 10

4: 7 7

5: 6 6

\*\*\********************************

Solution with 24 vertices.

0: 1, 2, 3, 9, 11,

1: 0, 2, 4,

2: 0, 1, 6, 8,

3: 0, 4, 9,

4: 1, 3, 5, 14,

5: 4, 6, 7, 15, 16,

6: 2, 5, 7,

7: 5, 6, 8, 10,

8: 2, 7, 10,

9: 0, 3, 12, 13,

10: 7, 8, 11, 17, 18,

11: 0, 10, 12, 23,

12: 9, 11, 13, 21, 22,

13: 9, 12, 14,

14: 4, 13, 15, 20, 21,

15: 5, 14, 16,

16: 5, 15, 17, 19,

17: 10, 16, 18,

18: 10, 17, 19, 23,

19: 16, 18, 20, 22, 23,

20: 14, 19, 21,

21: 12, 14, 20, 22,

22: 12, 19, 21,

23: 11, 18, 19,

Border: 11 (4), 12 (5), 22 (3), 19 (5), 23 (3),

Faces:

1: 0, 1, 2,

2: 0, 3, 4, 1,

3: 4, 5, 6, 2, 1,

4: 5, 7, 6,

5: 7, 8, 2, 6,

6: 0, 9, 3,

7: 7, 10, 8,

8: 10, 11, 0, 2, 8,

9: 11, 12, 9, 0,

10: 12, 13, 9,

11: 13, 14, 4, 3, 9,

12: 14, 15, 5, 4,

13: 15, 16, 5,

14: 16, 17, 10, 7, 5,

15: 17, 18, 10,

16: 16, 19, 18, 17,

17: 14, 20, 19, 16, 15,

18: 14, 21, 20,

19: 12, 21, 14, 13,

20: 21, 22, 19, 20,

21: 12, 22, 21,

22: 19, 23, 18,

23: 23, 11, 10, 18,

Number of nodes and faces with degree n:

3: 10 10

4: 8 8

5: 6 6

\*\*\*****************************************

So far no solutions with 18 or 19 vertices.

Cheers, Ingo

#61 · Tasmanian Devil

10 Feb 2008

Wonderful! I will have to take a look at them.

It actually follows from the proof that there is no (3,4,5)-alternating graph with fewer than 17 vertices:

Let r = v3 = f3. So there are r vertices of degree 3, r - 8 vertices belonging to a triangle, two quadrangles and two pentagons, and 4 other vertices of degree 5, and correspondingly for the dual objects. An immediate consequence is that r is at least 8. The number of edges with a triangle on one side is 3r (each triangle contributes 3 and they are all distinct), but can we say something about the number of edges between a quadrangle and a pentagon? Well, each vertex of degree 3 belongs to such an edge, and these r edges are also all distinct (since the other vertex of an edge must have degree different from 3). So there are at least 4r >= 32 edges, which implies that the number of edges must be at least 17.

For larger r, we can get a better estimate of the number of edges than 4r by considering pentagons instead. There are r - 4 pentagons, contributing 5r - 20 edges, and at least r edges between a triangle and a quadrangle for a total of at least 6r - 20 edges. Adding the edges with a triangle on one side and vertices of degree 4 and 5 shows that the number of edges is at most 7r - 20.

#62 · wccanard

10 Feb 2008

note also that Frank's examples show that v_4 can't be determined from v_3 and v_5, which TD was finding theoretically---he was just getting upper and lower bounds for v_4. Can Frank easily check to see if his graphs are self-dual? Isomorphism of planar graphs might be a hard theoretical problem but with so few vertices I bet it's attackable in practice.

#63 · Tasmanian Devil

10 Feb 2008

Here's the one with 20 vertices. This time I used GeoGebra (which also allows you to move vertices so that the edges follow automatically).

#65 · wccanard

10 Feb 2008

Do the 17-example and the 20-examples have large isomorphic subgraphs? It occurred to me that once you draw a pentagon and surround it with triangles and squares there are only a few possibilities for how this can be set up. If people could understand how to "modify" the 17-graph to make a 20-graph, this might be a method for constructing an infinite family by pure thought rather than computation--surgery on the graph. One might hit upon a "move" than can be applied arbitrarily often.

#67 · wccanard

10 Feb 2008

Here's an asymmetry in the first of the two diagrams above. Consider the triangles. All but one of the triangles are connected by vertices, to form a long line, and there is one solitary triangle somewhere near the middle of the picture. Dually, if you consider all the vertices of degree 3 and allow yourself to walk across diagonals of polygons to get from vertex to vertex (the dual notion) then 8 of the 9 degree 3 vertices are connected in a line, and the 9th is isolated. Evidence for self-duality! Also perhaps an indication that there is perhaps a more beautiful planar realisation, with perhaps the isolated triangle as an outer triangle, or one right in the middle perhaps.

#68 · wccanard

10 Feb 2008

[...first of the *three* diagrams above...]

#69 · wccanard

10 Feb 2008

I wonder whether "paths of triangles" is in fact quite a striking way of looking at these things; it follows from the constraints that triangles naturally want to fall into paths like this. Can one get a loop of triangles? Does the triangle configuration give a good isomorphism invariant for the graph?

#70 · Tasmanian Devil

10 Feb 2008

I might as well include my GeoGebra version of the original 17-vertices graph. The reason why some of the dots are black instead of blue is that I used mirroring to make it symmetrical.

#72 · wccanard

10 Feb 2008

Again that last one has a triangle that's not like the others: the top-left-ish one. It's the only one not attached to another triangle by a vertex. Could there be a more symmetric rendering of the graph that somehow uses that fact?

#74 · Ingo Althofer

10 Feb 2008

Thanks for all the pictures and the discussion.

I have to look carefully (for instance it is my impression

that Schneider-20 may be drawn in a way with more symmetries

obvious).

Here come adjacency lists for larger numbers of vetices.

Solution with 25 vertices

0: 1, 2, 3, 9, 11,

1: 0, 2, 4,

2: 0, 1, 6, 8,

3: 0, 4, 9,

4: 1, 3, 5, 14,

5: 4, 6, 7, 21, 22,

6: 2, 5, 7,

7: 5, 6, 8, 10,

8: 2, 7, 10,

9: 0, 3, 12, 13,

10: 7, 8, 11, 22, 23,

11: 0, 10, 12, 19,

12: 9, 11, 13, 15, 17,

13: 9, 12, 14,

14: 4, 13, 15, 16, 21,

15: 12, 14, 16, 17,

16: 14, 15, 18,

17: 12, 15, 18,

18: 16, 17, 19, 20,

19: 11, 18, 20, 23, 24,

20: 18, 19, 21,

21: 5, 14, 20, 24,

22: 5, 10, 23,

23: 10, 19, 22, 24,

24: 19, 21, 23,

Border: 24 (3), 21 (4), 5 (5), 22 (3), 23 (4),

Faces:

1: 0, 1, 2,

2: 0, 3, 4, 1,

3: 4, 5, 6, 2, 1,

4: 5, 7, 6,

5: 7, 8, 2, 6,

6: 0, 9, 3,

7: 7, 10, 8,

8: 10, 11, 0, 2, 8,

9: 11, 12, 9, 0,

10: 12, 13, 9,

11: 13, 14, 4, 3, 9,

12: 12, 15, 14, 13,

13: 15, 16, 14,

14: 15, 17, 18, 16,

15: 12, 17, 15,

16: 11, 19, 18, 17, 12,

17: 19, 20, 18,

18: 20, 21, 14, 16, 18,

19: 21, 5, 4, 14,

20: 5, 22, 10, 7,

21: 22, 23, 10,

22: 23, 19, 11, 10,

23: 19, 24, 21, 20,

24: 23, 24, 19,

Number of nodes and faces with degree n:

3: 10 10

4: 9 9

5: 6 6

\*\*\**************************************

Solution with 26 vertices

0: 1, 2, 3, 9,

1: 0, 2, 4,

2: 0, 1, 6, 8, 11,

3: 0, 4, 9,

4: 1, 3, 5, 15, 21,

5: 4, 6, 7, 15,

6: 2, 5, 7,

7: 5, 6, 8, 10, 14,

8: 2, 7, 10,

9: 0, 3, 11, 23, 24,

10: 7, 8, 12, 13,

11: 2, 9, 12, 25,

12: 10, 11, 13, 18, 25,

13: 10, 12, 14,

14: 7, 13, 16, 17,

15: 4, 5, 16,

16: 14, 15, 17, 19, 21,

17: 14, 16, 18,

18: 12, 17, 19, 20,

19: 16, 18, 20,

20: 18, 19, 22, 23, 25,

21: 4, 16, 22, 24,

22: 20, 21, 23,

23: 9, 20, 22, 24,

24: 9, 21, 23,

25: 11, 12, 20,

Border: 11 (4), 9 (5), 23 (4), 20 (5), 25 (3),

Faces:

1: 0, 1, 2,

2: 0, 3, 4, 1,

3: 4, 5, 6, 2, 1,

4: 5, 7, 6,

5: 7, 8, 2, 6,

6: 0, 9, 3,

7: 7, 10, 8,

8: 2, 11, 9, 0,

9: 10, 12, 11, 2, 8,

10: 10, 13, 12,

11: 7, 14, 13, 10,

12: 5, 15, 16, 14, 7,

13: 4, 15, 5,

14: 16, 17, 14,

15: 17, 18, 12, 13, 14,

16: 16, 19, 18, 17,

17: 19, 20, 18,

18: 16, 21, 22, 20, 19,

19: 4, 21, 16, 15,

20: 22, 23, 20,

21: 21, 24, 23, 22,

22: 9, 24, 21, 4, 3,

23: 9, 23, 24,

24: 20, 25, 12, 18,

25: 25, 11, 12,

Number of nodes and faces with degree n:

3: 11 11

4: 8 8

5: 7 7

***************************************************+

Solution with 27 vertices

0: 1, 2, 3, 10, 11,

1: 0, 2, 4,

2: 0, 1, 6, 9,

3: 0, 4, 8,

4: 1, 3, 5, 8,

5: 4, 6, 7,

6: 2, 5, 7, 9, 14,

7: 5, 6, 8, 23,

8: 3, 4, 7, 12, 26,

9: 2, 6, 10,

10: 0, 9, 11, 13,

11: 0, 10, 12,

12: 8, 11, 13, 19,

13: 10, 12, 14, 15, 17,

14: 6, 13, 15, 23,

15: 13, 14, 16,

16: 15, 17, 18, 21, 22,

17: 13, 16, 18,

18: 16, 17, 19, 20,

19: 12, 18, 20, 25, 26,

20: 18, 19, 21,

21: 16, 20, 22, 24,

22: 16, 21, 23,

23: 7, 14, 22, 24, 25,

24: 21, 23, 25,

25: 19, 23, 24, 26,

26: 8, 19, 25,

Border: 25 (4), 26 (3), 8 (5), 7 (4), 23 (5),

Faces:

1: 0, 1, 2,

2: 0, 3, 4, 1,

3: 4, 5, 6, 2, 1,

4: 5, 7, 6,

5: 3, 8, 4,

6: 8, 7, 5, 4,

7: 6, 9, 2,

8: 9, 10, 0, 2,

9: 10, 11, 0,

10: 11, 12, 8, 3, 0,

11: 10, 13, 12, 11,

12: 6, 14, 13, 10, 9,

13: 14, 15, 13,

14: 15, 16, 17, 13,

15: 16, 18, 17,

16: 18, 19, 12, 13, 17,

17: 18, 20, 19,

18: 16, 21, 20, 18,

19: 16, 22, 21,

20: 14, 23, 22, 16, 15,

21: 23, 24, 21, 22,

22: 24, 25, 19, 20, 21,

23: 25, 26, 19,

24: 26, 8, 12, 19,

25: 7, 23, 14, 6,

26: 23, 25, 24,

Number of nodes and faces with degree n:

3: 11 11

4: 9 9

5: 7 7

\*\*\************************************

Solution with 28 vertices

0: 1, 2, 3, 9,

1: 0, 2, 4,

2: 0, 1, 6, 8, 10,

3: 0, 4, 9,

4: 1, 3, 5, 14,

5: 4, 6, 7, 15, 24,

6: 2, 5, 7,

7: 5, 6, 8, 12,

8: 2, 7, 10,

9: 0, 3, 10, 11, 13,

10: 2, 8, 9, 11,

11: 9, 10, 12,

12: 7, 11, 13, 23, 24,

13: 9, 12, 14, 21,

14: 4, 13, 15, 16, 19,

15: 5, 14, 18, 22,

16: 14, 17, 19,

17: 16, 18, 20, 26,

18: 15, 17, 22,

19: 14, 16, 20, 21,

20: 17, 19, 21,

21: 13, 19, 20, 25, 27,

22: 15, 18, 23, 25, 26,

23: 12, 22, 24, 27,

24: 5, 12, 23,

25: 21, 22, 26, 27,

26: 17, 22, 25,

27: 21, 23, 25,

Border: 23 (4), 12 (5), 13 (4), 21 (5), 27 (3),

Faces:

1: 0, 1, 2,

2: 0, 3, 4, 1,

3: 4, 5, 6, 2, 1,

4: 5, 7, 6,

5: 7, 8, 2, 6,

6: 0, 9, 3,

7: 2, 10, 9, 0,

8: 10, 11, 9,

9: 8, 10, 2,

10: 7, 12, 11, 10, 8,

11: 12, 13, 9, 11,

12: 13, 14, 4, 3, 9,

13: 14, 15, 5, 4,

14: 14, 16, 17, 18, 15,

15: 16, 19, 20, 17,

16: 19, 21, 20,

17: 18, 22, 15,

18: 22, 23, 24, 5, 15,

19: 24, 12, 7, 5,

20: 23, 12, 24,

21: 21, 25, 26, 17, 20,

22: 26, 22, 18, 17,

23: 25, 22, 26,

24: 14, 19, 16,

25: 13, 21, 19, 14,

26: 21, 27, 25,

27: 27, 23, 22, 25,

Number of nodes and faces with degree n:

3: 11 11

4: 10 10

5: 7 7

\*\*\****************************************

Solution with 29 vertices

0: 1, 2, 3, 26,

1: 0, 2, 4,

2: 0, 1, 6, 23, 28,

3: 0, 4, 8,

4: 1, 3, 5, 8, 9,

5: 4, 6, 7,

6: 2, 5, 7, 15,

7: 5, 6, 9, 11, 13,

8: 3, 4, 10, 27,

9: 4, 7, 11,

10: 8, 11, 12, 18, 27,

11: 7, 9, 10, 12,

12: 10, 11, 13,

13: 7, 12, 14, 17,

14: 13, 15, 16,

15: 6, 14, 16, 22, 23,

16: 14, 15, 17, 21,

17: 13, 16, 18, 19, 21,

18: 10, 17, 19, 26,

19: 17, 18, 20,

20: 19, 21, 22, 24, 25,

21: 16, 17, 20,

22: 15, 20, 23,

23: 2, 15, 22, 24,

24: 20, 23, 25,

25: 20, 24, 26, 28,

26: 0, 18, 25, 27, 28,

27: 8, 10, 26,

28: 2, 25, 26,

Border: 2 (5), 0 (4), 26 (5), 28 (3),

Faces:

1: 0, 1, 2,

2: 0, 3, 4, 1,

3: 4, 5, 6, 2, 1,

4: 5, 7, 6,

5: 3, 8, 4,

6: 4, 9, 7, 5,

7: 8, 10, 11, 9, 4,

8: 11, 7, 9,

9: 10, 12, 11,

10: 12, 13, 7, 11,

11: 13, 14, 15, 6, 7,

12: 14, 16, 15,

13: 13, 17, 16, 14,

14: 10, 18, 17, 13, 12,

15: 18, 19, 17,

16: 19, 20, 21, 17,

17: 21, 16, 17,

18: 20, 22, 15, 16, 21,

19: 22, 23, 15,

20: 20, 24, 23, 22,

21: 20, 25, 24,

22: 18, 26, 25, 20, 19,

23: 10, 27, 26, 18,

24: 8, 27, 10,

25: 23, 2, 6, 15,

26: 0, 26, 27, 8, 3,

27: 26, 28, 25,

28: 28, 2, 23, 24, 25,

Number of nodes and faces with degree n:

3: 12 12

4: 9 9

5: 8 8

\*\*\******************************************

Solution with 30 vertices

0: 1, 2, 3, 9,

1: 0, 2, 4,

2: 0, 1, 6, 8, 11,

3: 0, 4, 9, 14, 15,

4: 1, 3, 5, 18,

5: 4, 6, 7, 19, 22,

6: 2, 5, 7,

7: 5, 6, 8, 10,

8: 2, 7, 10,

9: 0, 3, 11,

10: 7, 8, 12, 22, 29,

11: 2, 9, 12, 13,

12: 10, 11, 13,

13: 11, 12, 14, 16, 29,

14: 3, 13, 15, 16,

15: 3, 14, 17,

16: 13, 14, 17,

17: 15, 16, 18, 27,

18: 4, 17, 19, 20, 26,

19: 5, 18, 20,

20: 18, 19, 21, 24,

21: 20, 22, 23,

22: 5, 10, 21, 23,

23: 21, 22, 24, 25, 28,

24: 20, 23, 25,

25: 23, 24, 26, 27,

26: 18, 25, 27,

27: 17, 25, 26, 28, 29,

28: 23, 27, 29,

29: 10, 13, 27, 28,

Border: 13 (5), 16 (3), 17 (4), 27 (5), 29 (4),

Faces:

1: 0, 1, 2,

2: 0, 3, 4, 1,

3: 4, 5, 6, 2, 1,

4: 5, 7, 6,

5: 7, 8, 2, 6,

6: 0, 9, 3,

7: 7, 10, 8,

8: 2, 11, 9, 0,

9: 10, 12, 11, 2, 8,

10: 12, 13, 11,

11: 13, 14, 3, 9, 11,

12: 14, 15, 3,

13: 14, 16, 17, 15,

14: 13, 16, 14,

15: 17, 18, 4, 3, 15,

16: 18, 19, 5, 4,

17: 18, 20, 19,

18: 20, 21, 22, 5, 19,

19: 21, 23, 22,

20: 20, 24, 23, 21,

21: 24, 25, 23,

22: 18, 26, 25, 24, 20,

23: 26, 27, 25,

24: 27, 28, 23, 25,

25: 27, 29, 28,

26: 22, 10, 7, 5,

27: 29, 10, 22, 23, 28,

28: 17, 27, 26, 18,

29: 29, 13, 12, 10,

Number of nodes and faces with degree n:

3: 12 12

4: 10 10

5: 8 8

\*\*\*********************************************

By the way, Frank is somewhat in strain this weekend.

He has to split himself between girlfriend, work and

alternating planar graphs... So, I do want to ask him

immediately to write another algorithm for checking

self-duality.

Ingo.

#75 · Tasmanian Devil

10 Feb 2008

Well, I was hoping the images could help us see if they are self-dual.

#76 · Ingo Althofer

10 Feb 2008

The 21-graph is self-dual. This is rather

easy to check at the picture because in the (almost

symmetric) picture the central vertex (with degree 4)

corresponds to the outer face.

#77 · Ingo Althofer

10 Feb 2008

Each (3,4,5)-alternating graph with an odd

number of vertices has an odd number of

vertices of degree 4, according to Jan's

theorm. So, there might be a typical candidate

for a central vertex (and, if anti-podalitiy

is given) "on the other side" a typical

quadrangle as candidate for the outer face.

Ingo.

#78 · Ingo Althofer

10 Feb 2008

The graph with 23 vertices seems not

to be self-dual. Looking at the

"entities" with degree 4:

The seven vertices with degree 4 are

"connected", via common faces.

To the contrary, the seven faces of degree

4 are not connected via common vertices:

there is one group of 5, and another

"isolated" pair (in the upper left).

Ingo.

#79 · wccanard

10 Feb 2008

@Ingo: I believe you! So the dual gives another example, of course. Well spotted!

#81 · wccanard

10 Feb 2008

That last one has two 5-chains of triangles. Wonder if it has an interesting automorphism?

#85 · wccanard

10 Feb 2008

That last one has a loop of triangles---the first we've seen.

#88 · Ingo Althofer

11 Feb 2008

Thx to Jan for all the instructive drawings.

Frank Schneider found the (3,4,5)-alternating

graphs with a beam search (restricted to

(3,4,5)-graphs, with recognition of "some" symmetries).

Here is, for each n, the node counter where

the (first) alternating graph was found:

20 1,228,596

21 335,601

22 517,888

23 1,238,947

24 2,436,708

25 6,022,224

26 20,513,388

27 14,923,472

28 15,378,112

29 95,679,722

30 44,813,327

I do not claim that these number have a very

specific meaning. Nevertheless they give some

hints:

(i) (3,4,5)-alternating graphs seem to exist for all n >= 20.

(ii) (3,4,5)-alternating graphs are not too frequent, but

also not to seldom.

(iii) Beam search seems to take time exponential in n (or in (n-21))

to find such a graph of order n.

Perhaps there exists some construction which gives a (3,4,5)-

alternating graph of order n (for n >= n_0),

taking only linear (or polynomial) time in n.

Ingo.

#89 · Ingo Althofer

11 Feb 2008

For 42 vertices Frank Schneider found a

(3,4,5)-alternating graph wiht a beam search

with very small branching degree:

A solution with 42 vertices.

Total nodes searched: 312,166,530

0: 1, 2, 3, 8, 12,

1: 0, 2, 4,

2: 0, 1, 6, 11,

3: 0, 4, 8,

4: 1, 3, 5, 9,

5: 4, 6, 7,

6: 2, 5, 7, 11, 16,

7: 5, 6, 9, 10,

8: 0, 3, 10, 14,

9: 4, 7, 10,

10: 7, 8, 9, 15, 16,

11: 2, 6, 12,

12: 0, 11, 13, 17,

13: 12, 14, 15, 18, 23,

14: 8, 13, 15,

15: 10, 13, 14, 24,

16: 6, 10, 17, 25,

17: 12, 16, 18, 19, 26,

18: 13, 17, 19, 21,

19: 17, 18, 20,

20: 19, 21, 22, 27,

21: 18, 20, 22,

22: 20, 21, 23, 28, 31,

23: 13, 22, 24, 25,

24: 15, 23, 25,

25: 16, 23, 24, 26, 31,

26: 17, 25, 27, 38,

27: 20, 26, 28, 39, 40,

28: 22, 27, 29, 33,

29: 28, 30, 32,

30: 29, 31, 32, 35, 36,

31: 22, 25, 30, 37,

32: 29, 30, 33, 34,

33: 28, 32, 34,

34: 32, 33, 35, 40, 41,

35: 30, 34, 36,

36: 30, 35, 37, 38,

37: 31, 36, 38,

38: 26, 36, 37, 39, 41,

39: 27, 38, 40, 41,

40: 27, 34, 39,

41: 34, 38, 39,

Border: 34 (5), 35 (3), 36 (4), 38 (5), 41 (3),

Faces:

1: 0, 1, 2,

2: 0, 3, 4, 1,

3: 4, 5, 6, 2, 1,

4: 5, 7, 6,

5: 0, 8, 3,

6: 4, 9, 7, 5,

7: 8, 10, 9, 4, 3,

8: 10, 7, 9,

9: 6, 11, 2,

10: 11, 12, 0, 2,

11: 12, 13, 14, 8, 0,

12: 13, 15, 14,

13: 15, 10, 8, 14,

14: 10, 16, 6, 7,

15: 16, 17, 12, 11, 6,

16: 17, 18, 13, 12,

17: 17, 19, 18,

18: 19, 20, 21, 18,

19: 20, 22, 21,

20: 22, 23, 13, 18, 21,

21: 23, 24, 15, 13,

22: 24, 25, 16, 10, 15,

23: 23, 25, 24,

24: 25, 26, 17, 16,

25: 26, 27, 20, 19, 17,

26: 27, 28, 22, 20,

27: 28, 29, 30, 31, 22,

28: 29, 32, 30,

29: 31, 25, 23, 22,

30: 28, 33, 32, 29,

31: 33, 34, 32,

32: 34, 35, 30, 32,

33: 35, 36, 30,

34: 36, 37, 31, 30,

35: 37, 38, 26, 25, 31,

36: 38, 39, 27, 26,

37: 39, 40, 27,

38: 40, 34, 33, 28, 27,

39: 36, 38, 37,

40: 38, 41, 39,

41: 41, 34, 40, 39,

Number of nodes and faces with degree n:

3: 15 15

4: 16 16

5: 11 11

#90 · FatPhil

11 Feb 2008

Can you remind me what's so special about {3,4,5} ones? What's wrong with just building one with an arbitrary-sized 'outer' face, say?

#91 · Ingo Althofer

11 Feb 2008

Four days ago Jan (=TD) wrote about (3,4,5)-alternating graphs:

> I tried to work out how big v4 would

> be compared to the others and it seems

> to be between

> 3v5/4 and v3/2 + v5

> (don't take my word for it though).

Asymptotically (with v3 = v5 + 4) this would mean

that always

0.75*v5 <= v4 <=approx. 1.50*v5

When this is still the feeling it might be

interesting to find extreme candidates (with

low or high v4-percentage).

I might try to

convince Frank to modify his beam search (which

constructs candidate graphs from the center to the

"outskirts") to look only for candidates where in

each step of the construction the v4-percentage is

not higher (or not much higher) than 0.75*v5 or

not smaller (or not much smaller) than 1.5*v5.

#92 · Ingo Althofer

11 Feb 2008

FatPhil wrote:

> Can you remind me what's so special about {3,4,5} ones?

For this class we have some theory which helps to

narrow the search.

> What's wrong with just building one with an arbitrary-sized

> 'outer' face, say?

They would be ok, too. And, especially (3,4,5)-graphs

with arbitrary outer face might also allow for quick

searches.

By the way: Are you trying to leave your

self-claimed extremal position in this thread? ;-)

> Hoorah - I am now officially the single most

> useless contributor to this thread!

Gregorio may start another chase on you...

Ingo.

#93 · wccanard

11 Feb 2008

@Phil: I gave a construction earlier on which produced arbitrarily large non-(3,4,5) alternating graphs, simply by taking one of the examples we had and glueing N of them together in a mildly careful way. So in some sense that answered several of the "obvious" questions about such gadgets. On the other hand TD seemed to be half way towards proving a "structure theorem" for the (3,4,5) graphs so they became more interesting; there are still lots of obvious open questions about them, for example whether you can get arbitrarily large ones, and, earlier, whether they were all self-dual [they aren't, even though they necessarily have the same number of n-faces as n-vertices for n=3,4,5].

#94 · Tasmanian Devil

11 Feb 2008

I have improved the bounds on v4. With r = v3, the number of edges is between 6r - 20 and 7r - 20, as I said in a previous post, and it follows that v4 is between r - 5 and 3r/2 - 5.

#95 · Tasmanian Devil

11 Feb 2008

I found that last one on 42 vertices quite difficult to draw nicely. Here's what I've got.

#96 · Ingo Althofer

11 Feb 2008

Jan wrote:

> it follows that v4 is between v3 - 5 and 1.5*v3 - 5.

Hmm.

I looked again at the parameter of the graphs

generated by Frank's beam search. The following

table contains in each line the number n of vertices

and the number of 4-faces, expressed als "r +- something",

where r is the number of 3-faces.

17 r-3

18 ---

19 ---

20 r-3

21 r-5

22 r-4

23 r-3

24 r-2

25 r-1

26 r-3

27 r-2

28 r-1

29 r-3

30 r-2

42 r+1

\*\*\**********************************************

(i) Do you also see the rhythm of length 3?

n = 0 (mod 3), then r-2 (or r-5 or r+1)

n = 1 (mod 3), then r-1 (or r-4)

n = 2 (mod 3), then r-3

(ii) Maybe it is an artefact depending on Frank's

order in the beam search but all values of v4 are

rather "near" at the lower bound (and far away from

the upper bound 1.5*r - 5).

#97 · Ingo Althofer

11 Feb 2008

Frank Schneider mailed to me:

> die Graphen 22, 23, 24, 26, 29, 30, 42 sind "not self-dual",

> die Graphen 17, 20, 21, 25, 27, 28 sind "self-dual".

He has written a tool which generates the dual graphs

and then checks for isomorphy with help of "boost" (whatever boost may be, IA).

Probably Frank will soon also post here,

after I told him that this is possible without

being a member of LittleGolem.

Ingo.

#98 · Tasmanian Devil

11 Feb 2008

> (i) Do you also see the rhythm of length 3?

> n = 0 (mod 3), then r-2 (or r-5 or r+1)

> n = 1 (mod 3), then r-1 (or r-4)

> n = 2 (mod 3), then r-3

This isn't very surprising, since n = v4 + 2r - 4 => v4 - r = n + 4 - 3r == n + 1 (mod 3).

> (ii) Maybe it is an artefact depending on Frank's

> order in the beam search but all values of v4 are

> rather "near" at the lower bound (and far away from

> the upper bound 1.5*r - 5).

That is possible. I noticed, however, that (v4 + 5) / r varies between 1 and 1.4 in the examples, so it's not always closest to the lower bound.

#99 · Ingo Althofer

12 Feb 2008

Here I am the mouth piece of Frank Schneider.

(He registered on LG, and when trying to post, got

the message: "Error: You are not enough trustworthy

for sending messages.") Ingo.

\*\*\*\*\*\*\*\*\*\*\*\* Frank writes *******************:

Hi all,

first many thanks to Ingo for posting the nice challenge and to

TasmanianDevil and wccanard for the proofs and the very nice

diagrams of the graphs!

I just ran some tests with a version of my program, which

favours (or disfavours) vertices of degree 4 when building a

solution. So far, it couldn't find two solutions for the same

N (N=17, 20, .., 27), which differ in v4. That's quite interesting,

although it's probably too early to claim that there is a fixed

relation between N and v3, v4 and v5.

Below are two more (self-dual) (3,4,5)-alternating graphs with 31 (32)

vertices and v4 = r-1 (v4=r4).

17 r-3

18 ---

19 ---

20 r-3

21 r-5

22 r-4

23 r-3

24 r-2

25 r-1

26 r-3

27 r-2

28 r-1

29 r-3

30 r-2

31 r-1

32 r

33

34

35

36

37

38

39

40

41

42 r+1

43

Now the pattern of the v4 looks like v4/r slowly increases with N in which

case it *could* finally hit the bound 1.5*r - 5.

So it becomes more interesting to find out if there is a way to construct

larger (3,4,5)-alternating graphs.

Best, Frank

\*\*\**************************************

Solution found with 60 edges,

31 vertices and 31 faces.

Total nodes searched: 63548392

0: 1, 2, 3, 9, 11,

1: 0, 2, 4,

2: 0, 1, 6, 8,

3: 0, 4, 9,

4: 1, 3, 5, 14,

5: 4, 6, 7, 22, 29,

6: 2, 5, 7,

7: 5, 6, 8, 10,

8: 2, 7, 10,

9: 0, 3, 12, 13,

10: 7, 8, 11, 20, 22,

11: 0, 10, 12, 19,

12: 9, 11, 13, 15, 16,

13: 9, 12, 14,

14: 4, 13, 15, 18, 29,

15: 12, 14, 16, 18,

16: 12, 15, 17,

17: 16, 18, 19, 28,

18: 14, 15, 17,

19: 11, 17, 20, 21, 27,

20: 10, 19, 21,

21: 19, 20, 23, 25,

22: 5, 10, 23, 24,

23: 21, 22, 24,

24: 22, 23, 25, 26, 30,

25: 21, 24, 26,

26: 24, 25, 27, 28,

27: 19, 26, 28,

28: 17, 26, 27, 29, 30,

29: 5, 14, 28, 30,

30: 24, 28, 29,

Border: 24 (5), 26 (4), 28 (5), 30 (3),

Faces:

1: 0, 1, 2,

2: 0, 3, 4, 1,

3: 4, 5, 6, 2, 1,

4: 5, 7, 6,

5: 7, 8, 2, 6,

6: 0, 9, 3,

7: 7, 10, 8,

8: 10, 11, 0, 2, 8,

9: 11, 12, 9, 0,

10: 12, 13, 9,

11: 13, 14, 4, 3, 9,

12: 12, 15, 14, 13,

13: 12, 16, 15,

14: 16, 17, 18, 15,

15: 18, 14, 15,

16: 11, 19, 17, 16, 12,

17: 10, 20, 19, 11,

18: 20, 21, 19,

19: 10, 22, 23, 21, 20,

20: 22, 24, 23,

21: 24, 25, 21, 23,

22: 24, 26, 25,

23: 26, 27, 19, 21, 25,

24: 27, 28, 17, 19,

25: 28, 29, 14, 18, 17,

26: 29, 5, 4, 14,

27: 5, 22, 10, 7,

28: 26, 28, 27,

29: 28, 30, 29,

30: 30, 24, 22, 5, 29,

Number of nodes and faces with degree n:

3: 12 12

4: 11 11

5: 8 8

\*\*\**************************************

Solution found with 62 edges,

32 vertices and 32 faces.

Total nodes searched: 304613301

0: 1, 2, 3, 9,

1: 0, 2, 4,

2: 0, 1, 6, 8, 10,

3: 0, 4, 9,

4: 1, 3, 5, 14,

5: 4, 6, 7, 17, 28,

6: 2, 5, 7,

7: 5, 6, 8, 12,

8: 2, 7, 10,

9: 0, 3, 10, 11, 13,

10: 2, 8, 9, 11,

11: 9, 10, 12,

12: 7, 11, 13, 15, 17,

13: 9, 12, 14, 15,

14: 4, 13, 16, 20, 28,

15: 12, 13, 16,

16: 14, 15, 18, 20,

17: 5, 12, 18, 26,

18: 16, 17, 19, 21, 24,

19: 18, 20, 23, 27,

20: 14, 16, 19,

21: 18, 22, 24,

22: 21, 23, 25, 30,

23: 19, 22, 27,

24: 18, 21, 25, 26,

25: 22, 24, 26,

26: 17, 24, 25, 29, 31,

27: 19, 23, 28, 29, 30,

28: 5, 14, 27, 31,

29: 26, 27, 30, 31,

30: 22, 27, 29,

31: 26, 28, 29,

Border: 17 (4), 18 (5), 24 (4), 26 (5),

Faces:

1: 0, 1, 2,

2: 0, 3, 4, 1,

3: 4, 5, 6, 2, 1,

4: 5, 7, 6,

5: 7, 8, 2, 6,

6: 0, 9, 3,

7: 2, 10, 9, 0,

8: 10, 11, 9,

9: 8, 10, 2,

10: 7, 12, 11, 10, 8,

11: 12, 13, 9, 11,

12: 13, 14, 4, 3, 9,

13: 13, 15, 16, 14,

14: 12, 15, 13,

15: 12, 17, 18, 16, 15,

16: 5, 17, 12, 7,

17: 18, 19, 20, 16,

18: 20, 14, 16,

19: 18, 21, 22, 23, 19,

20: 21, 24, 25, 22,

21: 24, 26, 25,

22: 23, 27, 19,

23: 27, 28, 14, 20, 19,

24: 28, 5, 4, 14,

25: 26, 29, 30, 22, 25,

26: 30, 27, 23, 22,

27: 26, 31, 29,

28: 29, 27, 30,

29: 31, 28, 27, 29,

30: 18, 24, 21,

31: 26, 17, 5, 28, 31,

Number of nodes and faces with degree n:

3: 12 12

4: 12 12

5: 8 8

#100 · Tasmanian Devil

12 Feb 2008

> (He registered on LG, and when trying to post, got

> the message: "Error: You are not enough trustworthy

> for sending messages.")

Yes, he needs to start some games too. :-)

> Now the pattern of the v4 looks like v4/r slowly increases

> with N in which case it *could* finally hit the bound 1.5*r - 5.

So maybe the 21-graph (which is self-dual!) is the only one for which v4 is as small as r - 5?

The 32-graph has the highest value of (v4 + 5)/r so far: 1.41666...

> So it becomes more interesting to find out if there is

> a way to construct larger (3,4,5)-alternating graphs.

Yes (or an infinite one, as I asked for earlier).

Last page