Search for small alternating planar graphs General forum

155 replies. Last post: 2015-05-30

Reply to this topic Return to forum

Search for small alternating planar graphs
  • Ingo Althofer at 2008-02-02

    Hello everybody,

    a planar graph is called alterning when it has

    * no pair of neighboring vertices with the same degree
    and
    * no pair of neighboring faces with the same number of sides.

    The smallest alternating planar graph I know
    has 25 vertices and 25 faces (the outer face is also
    in the count). It was constructed by two math students
    from Jena university: Katrin Nimczick andLisa Schreiber.

    A picture of it can be seen under
    [http://www.althofer.de/alternating-planar-graphs.html]

    For me it would be a big surprise when there were
    no other alternating planar graphs with less then
    25 vertices and 25 faces.

    Ingo Althofer

  • Ingo Althofer at 2008-02-02

    Sorry for the misspell:

    It should be “alternating” and not alterning.

    Ingo

  • wccanard at 2008-02-02

    How about the empty graph? :-) [duck]

  • wccanard at 2008-02-02

    And how about you ask in a place like sci.math.research? That might be a better place for a question like this.

  • wccanard at 2008-02-02

    Final comment: are you disallowing vertices of degree 2? If not then here’s an example with fewer faces (but more vertices): take a cube, chop off all the edges (so we have six octagon faces and 8 triangles) and now put a vertex in the middle of each side of each triangle. Now we have six 12-gons and eight hexagons; now flatten it out.

  • wccanard at 2008-02-02

    typo: chop off all the CORNERS! [not edges]

  • wccanard at 2008-02-02

    groan need a vertex in the middle of each edge, not just the triangle edges. So resulting thing is six 16-gons and eight hexagons. I think I’m OK now though.

  • wccanard at 2008-02-02

    ooh---better example (and one that works): start with a cube, and cut off the corners so much that you end up with one of those shapes with 6 square faces and 8 triangle faces. Now put a new vertex in the middle of each edge. How about that? I think this has 6 octagons, 8 hexagons and 36 vertices?

  • Tasmanian Devil at 2008-02-02

    Nice problem. The web page states that each vertex must have degree at least 3 and each face must have at least 3 sides.

  • wccanard at 2008-02-02

    Aah. I didn’t look at the web page, just the description above, where these extra conditions have carefully been removed :-)

    I am no graph theorist, but it wouldn’t surprise me if there were standard databases of graphs nowadays online and one could just write a little computer script to check through them to see if one could find smaller examples.

  • Tasmanian Devil at 2008-02-02

    There is the program “plantri” available online that generates planar graphs. A good C-programmer could modify it to search for alternating planar graphs.

  • Ingo Althofer at 2008-02-02

    Thanks to wccanard and the Tasmanian devil for all
    the quick feedback. And e few comments:

    wcc proposed:
    > how about you ask in a place like sci.math.research?
    > That might be a better place for a question like this.

    In principle you are right, and I may ask there later,
    too. However, in mind I have the use of “nice” alternating
    planar graphs for a new board game mechanism. Knowing
    this, LG players may be especially motivated to look
    for small apg’s.

    wcc:
    > are you disallowing vertices of degree 2?

    Right. When you allow vertices of degree 2 (and not
    faces of degree 2) you can build examples for instance
    with 6 vertices and 4 faces: one square with two triangles
    added at two neighboring sides.


    Tasmanian Devil proposed:
    > There is the program “plantri” available online that generates
    > planar graphs. A good C-programmer could modify it to search
    > for alternating planar graphs.

    Thanks for the hint.

    Ingo.

  • Ingo Althofer at 2008-02-06

    New record holder is Frank Schneider,
    the chess programmer. His solution (by
    computer search) has 17 vertices and 17
    faces. See under

    http://f23.parsimony.net/forum50826/messages/178269.htm

    Ingo.

  • Tasmanian Devil at 2008-02-06

  • Tasmanian Devil at 2008-02-06

    In view of Euler’s formula, maybe it is more elegant to ask for the minimal value of the number of edges than for the number of vertices plus the number of faces?

    Minimizing the number of vertices and minimizing the number of faces are of course dual problems.

    So we could ask for alternating graphs with the minimal number of vertices or the minimal number of edges.

    Is there an infinite alternating graph?

    Is there an infinite alternating graph where each vertex has degree 3, 4 or 5 and each face has 3, 4 or 5 sides?

    Are there infinitely many alternating graphs where each vertex has degree 3, 4 or 5 and each face has 3, 4 or 5 sides? Do they become more and more numerous as we increase the total number of vertices?

  • wccanard at 2008-02-06

    “Is there an infinite alternating graph?” The question doesn’t quite make sense to me because you have to deal with regions with infinitely many sides. Here is a construction of arbitrarily large alternating graphs: take your beautiful pentagon above, and label the top left hand vertex A, and then go clockwise A,B,C,D,E labelling the outer vertices. Now glue BC for one pentagon to ED for another [so you have vertices of degrees 6 and 8 in the new construction]. Make a chain of 100 pentagons that way; if I’ve got it right this will give rise to a large alternating graph. I leave it to you to decide whether the “limit” of this construction is alternating.

  • wccanard at 2008-02-06

    Clarification! Glue B to D and C to E!

  • Tasmanian Devil at 2008-02-06

    Yep, I guess that works! Thanks!

    I studied the drawing and found a more symmetric representation that I will post shortly.

  • Tasmanian Devil at 2008-02-06

    Your concern about faces with infinitely many sides is supporting argument for my "3-4-5"restrictions above. :)

  • Tasmanian Devil at 2008-02-06

    a supporting argument even

  • Ingo Althofer at 2008-02-06

    That looks fantastic, you Tasmanian Devil, you!
    Thanks a lot for the drawings.

    It is a pity that I have to do administration work
    the whole night now...

    Ingo.

  • Ingo Althofer at 2008-02-06

    I am no completely sure, but it seems to
    me that the graph of Frank Schneider is
    self-dual.

    Ingo.

  • FatPhil at 2008-02-07

    Amazing work, Jan! Bravo!

  • Tasmanian Devil at 2008-02-07

    Thanks, but there was nothing to it, just recreation.

  • FatPhil at 2008-02-07

    Yours isn’t isomorphic to Frank’s, so I wonder how many solutions there are.

  • Tasmanian Devil at 2008-02-07

    Um, yes it is, I haven’t found any on my own.

  • wccanard at 2008-02-07

    @phil: he’s moved the point at infinity. I find that considering the pentagons helps me orient myself.

  • FatPhil at 2008-02-07

    Doh! One of these days I’ll learn to count up to 4!
    So bravo Frank! Tas – you’re nearly as useless as I am :-P

  • Tasmanian Devil at 2008-02-07

    I know – don’t tell the principal.

  • Ingo Althofer at 2008-02-07

    Tasmanian Devil wrote:
    > Thanks, but there was nothing to it, just recreation.

    Thanks again for the nice drawings. I had such a good
    sleep with the knowledge that the graph is so beautiful.

    Question: How did you generate the drawings?
    By hand ,
    or fully automatically (with what software?),
    or computer-aided in some way?

    Best regards, Ingo

  • Tasmanian Devil at 2008-02-07

    I drew it on paper looking at Frank’s definition, then drew it with Paint, then noticed the symmetry of the quadrangles, re-drew it several times on paper, then drew it with Paint again.

    I believe I have a proof that for alternating graphs for which all vertices have degree 3, 4 or 5, and all faces have 3, 4 or 5 sides, the number of vertices must be equal to the number of faces. This is not true for alternating graphs in general (in view of wccanard’s construction). I can post the proof if you like.

  • Gregorlo at 2008-02-07

    paint? that’s really low-tech! :P

  • Ingo Althofer at 2008-02-07

    > I drew it on paper looking at Frank’s definition,
    > then drew it with Paint, then noticed the
    > symmetry of the quadrangles, re-drew it several
    > times on paper, then drew it with Paint again.

    Thx. Before your pictures came, I had the idea to enter
    the graph into computer geometry software Cinderella
    (which allows vertices to be moved around, all connections
    simply following).

    > I believe I have a proof that for alternating graphs
    > for which all vertices have degree 3, 4 or 5, and all
    > faces have 3, 4 or 5 sides, the number of vertices
    > must be equal to the number of faces.

    That sounds interesting.
    Please, post it.

    > This is not true for alternating graphs in general (in
    > view of wccanard’s construction).

    And it is also not true for arbitrary planar graphs with
    restrictions 3, 4, 5 for vertices and faces.

    Ingo.

  • Ingo Althofer at 2008-02-07

    Gregorio:
    > paint? that’s really low-tech! :P

    lowtech or not – paint is fantastic. You can
    manipulate each single pixel very easily.
    paint is my first choice when doing graphics.

    Ingo

  • wccanard at 2008-02-07

    I’ll remark that my construction (glueing pentagons together) produces graphs with different numbers of vertices than faces, but some vertices have degree 8. On the other hand the original example of an alternating graph has vertices and faces of degree 6 but also the same number of vertices as faces. Can you squeeze 6 into your proof Tasmanian Devil?

  • Tasmanian Devil at 2008-02-07

    We call a graph (3,4,5)-alternating if it satisfies the following conditions:

    -it is planar
    -each vertex has degree 3, 4 or 5
    -each face has 3, 4 or 5 sides
    -any two adjacent vertices have different degree
    -any two adjacent faces have different number of sides

    Theorem: If G is a (3,4,5)-alternating graph, then the number of vertices of G is equal to the number of faces of G.

    Proof: Suppose G is a (3,4,5)-alternating graph. Let vi denote the number of vertices of degree i, and let fj denote the number of faces with j sides.

    Summing the edges over the vertices shows that the total number of edges is (3v3+4v4+5v5)/2, while summing over the faces shows that it is (3f3+4f4+5f5)/2. So we have

    (1) (3v3+4v4+5v5)/2 = (3f3+4f4+5f5)/2

    Euler’s formula gives

    2(v3+v4+v5) + 2(f3+f4+f5) = (3v3+4v4+5v5)/2 + (3f3+4f4+5f5)/2

    which simplifies to

    (2) v3 + f3 = v5 + f5 + 8

    The rest of the proof is based on counting (i, j)-combinations, that is, the number of instances of a vertex of degree i belonging to a face with j sides. For example, each vertex of degree 3 must belong to a triangle, a quadrangle and a pentagon, and eacg triangle must have one vertex of each degree (3, 4 and 5). So we see that the number of (3, 3)-combinations must be equal to v3, but it must also be equal to f3, so we can deduce that

    (3) v3 = f3

    Counting (3, 5)-combinations show that

    (4) f5 <= v3

    while a dual argument (counting (5, 3)-combinations) shows that

    (5) v5 <= f3

    Combining (1), (2), (3), (4) and (5) gives us five possibilities:

    v5 = v3 - 8, f5 = v3
    v5 = v3 - 6, f5 = v3 - 2
    v5 = v3 - 4, f5 = v3 - 4
    v5 = v3 - 2, f5 = v3 - 6
    v5 = v3, f5 = v3 - 8

    Let ai denote the number of vertices of degree 5 that belong to exactly one face with i sides (and two of each of the other two types). Counting (5, 3)-combinations shows that

    a3 = 2v5 - v3, a4 + a5 = v3 - v5

    The number of (5, 5)-combinations is a5 + 2(v5 - a5) = 2v5 - a5. A dual argument show that it is also equal to 2f5 - b5 where bj denotes the number of pentagons with exactly one vertex of degree j. So we have

    (6) a5 – b5 = 2(v5 - f5)

    But since 0 <= a5 <= v3 - v5 and 0 <= b5 <= f3 - f5, this is only possible if v5 = f5 = v3 - 4. In particular, if v5 = v3 - 2 or v5 = v3, a5 is at most 2, making (6) impossible. If v5 = v3 - 6 or v5 = v3 - 8, we can look at b5 instead: it is at most 2, again making (6) impossible. Of course, (1) now also gives v4 = f4 and the result follows.

  • Tasmanian Devil at 2008-02-07

    wccanard, I am afraid the argument falls apart if I try to include 6.

    Gregorio: I know, I also use Turbo Pascal 4.0 to explore mathematical problems. :p

  • Tasmanian Devil at 2008-02-07

    There is a “+ 4” missing in Euler’s formula

  • wccanard at 2008-02-07

    Another remark: let’s say the “degree” of an alt. graph is the max of the degrees of the vertices and the sides of the faces. By definition the degrees of vertices and sides of faces all must be 3 or more, so T.Devil is talking about alternating graphs of degree 5. TD says that they always have the same number of vertices as faces. Are deg 5 alternating graphs always self-dual??

  • Tasmanian Devil at 2008-02-07

    (6) a5 - b5 = 2(v5 - f5)

  • FatPhil at 2008-02-07

    Hoorah – I am now officially (OK, that’s also self-appointed) the single most useless contributor to this thread!

  • wccanard at 2008-02-07

    @Tas: very nice! You in fact prove that v_n=f_n for n=3,4,5, which is further evidence for the question as to whether they’re always self-dual. I didn’t even check whether the 17-example was self-dual though.

  • Tasmanian Devil at 2008-02-07

    Yes, Frank’s graph is self-dual, but I think it is too early to guess that this is always the case.

    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).

  • Gregorlo at 2008-02-07

    phil, my usefulness is approximately equals to your4s ;)

    @ingo: i was being ironic :)

  • Ingo Althofer at 2008-02-08

    Tasman-Jan,

    thx for presenting the proof. This evening, in the train
    home to family, I will hopefully find time to
    go through it step by step.


    *************************
    @Gregorio:
    > i was being ironic :)

    Good hint. But believe me or not: there are crowds
    of people out who really believe that old software
    can not be good.

    Ingo.

  • Tasmanian Devil at 2008-02-08

    I should mention that (1) and (3) gives that v5 - f5 must be divisible by 4.

  • Gregorlo at 2008-02-08

    @ingo: being low-tech is not necesarily a bad thing :)

  • Ingo Althofer at 2008-02-08

    Tasmanian Devil wrote:
    > I should mention that (1) and (3) gives
    > that v5 – f5 must be divisible by 4.

    Hmm, a joke?
    In your proof one of the statements is v5 = f5.

    In the train, I checked the proof. At the end,
    it took me some time to verify the steps, but
    all is ok.

    Maybe it would be a more natural formulation to state
    in the theorem that
    v3=f3, v4=f4, and v5=f5;
    and only as a corollary that number of vertices = number of faces.

    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.
    If true, this would be one more small step
    in direction of self-duality.

    And a bold open question:
    Is it true that every (3,4,5)-alternating graph is not
    only self-dual, but also antipodal?
    (Meaning of “antipodal”: You can span the graph
    on a sphere in such a way, that on the opposite side of
    each vertex with arbitrary degree k there is a face with
    k sides.)
    The Schneider graph is antipodal.

    Ingo

  • Tasmanian Devil at 2008-02-08

    >> I should mention that (1) and (3) gives
    >> that v5 – f5 must be divisible by 4.

    > Hmm, a joke?
    > In your proof one of the statements is v5 = f5.

    He he, true...but I meant that it should be inserted into the proof when I get only 5 cases and not v5 = v3 - 7, f5 = v3 - 1 and so on. Alternatively, the last step that narrows it down to one case also works without applying this result.

    > In the train, I checked the proof. At the end,
    > it took me some time to verify the steps, but
    > all is ok.

    Good – maybe we will see an update of your web page soon? ;-)

  • Ingo Althofer at 2008-02-09

    My web page on alternating planar graphs
    is updated. Watch at

    http://www.althofer.de/alternating-planar-graphs.html

    and/or have a nice weekend.
    Ingo.

  • Ingo Althofer at 2008-02-09

    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).

  • Tasmanian Devil at 2008-02-09

    > 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.

  • Ingo Althofer at 2008-02-09

    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...

  • Tasmanian Devil at 2008-02-09

    > PS: Indipendently I will ask Frank Schneider to modify his program
    > to find more (3,4,5)-graphs...

    That would be very interesting!

  • wccanard at 2008-02-09

    @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})?

  • Tasmanian Devil at 2008-02-09

    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.

  • wccanard at 2008-02-09

    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?

  • Tasmanian Devil at 2008-02-09

    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.

  • wccanard at 2008-02-09

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

  • Ingo Althofer at 2008-02-10

    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

  • Tasmanian Devil at 2008-02-10

    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.

  • wccanard at 2008-02-10

    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.

  • Tasmanian Devil at 2008-02-10

    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).

  • Tasmanian Devil at 2008-02-10

    21 vertices

  • wccanard at 2008-02-10

    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.

  • Tasmanian Devil at 2008-02-10

    22 vertices

  • wccanard at 2008-02-10

    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.

  • wccanard at 2008-02-10

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

  • wccanard at 2008-02-10

    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?

  • Tasmanian Devil at 2008-02-10

    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.

  • Tasmanian Devil at 2008-02-10

    23 vertices

  • wccanard at 2008-02-10

    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?

  • Tasmanian Devil at 2008-02-10

    24 vertices

  • Ingo Althofer at 2008-02-10

    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.

  • Tasmanian Devil at 2008-02-10

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

  • Ingo Althofer at 2008-02-10

    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.

  • Ingo Althofer at 2008-02-10

    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.

  • Ingo Althofer at 2008-02-10

    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.

  • wccanard at 2008-02-10

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

  • Tasmanian Devil at 2008-02-10

    25 vertices

  • wccanard at 2008-02-10

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

  • Tasmanian Devil at 2008-02-10

    26 vertices

  • Tasmanian Devil at 2008-02-10

    27 vertices

  • Tasmanian Devil at 2008-02-10

    28 vertices

  • wccanard at 2008-02-10

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

  • Tasmanian Devil at 2008-02-10

    29 vertices

  • Tasmanian Devil at 2008-02-10

    30 vertices

  • Ingo Althofer at 2008-02-11

    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.

  • Ingo Althofer at 2008-02-11

    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

  • FatPhil at 2008-02-11

    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?

  • Ingo Althofer at 2008-02-11

    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.

  • Ingo Althofer at 2008-02-11

    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.

  • wccanard at 2008-02-11

    @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].

  • Tasmanian Devil at 2008-02-11

    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.

  • Tasmanian Devil at 2008-02-11

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

  • Ingo Althofer at 2008-02-11

    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).

  • Ingo Althofer at 2008-02-11

    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.

  • Tasmanian Devil at 2008-02-11

    > (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.

  • Ingo Althofer at 2008-02-12

    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

  • Tasmanian Devil at 2008-02-12

    > (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).

  • wccanard at 2008-02-12

    “Yes, he needs to start some games”: this was put in a year or so ago by Richard, to stop spam. The idea was that it was probably harder to write code for spambots if they also had to be able to play a passable game of hex :)

    The infinite graph: perhaps a way of making your question meaningful is to ask for a locally finite tiling of R^2 [so every point in R^2 has to be either a vertex, or on a piecewise smooth edge with finite length, or in a polygon with finite area and piecewise smooth edges blah blah blah] and which has the right local properties. Then you don’t have to worry about infinite regions or “dot dot dots” in the middle of graphs. My guess is that this is what you implicitly mean. So, for example, my infinite glueing of pentagons above wouldn’t count above because it can’t immediately be tweaked to cover all of R^2.

    It wouldn’t surprise me if one could take one of the examples above, arrange it so it has a square as a boundary, and then tile the plane with squares in the obvious way and put a copy of the graph into the square in a sufficiently clever way (the issue is the orientation) that gives an example of an infinite graph with a global bound (16 or so) on the degrees of the vertices. But I didn’t try this yet, and it might not work. A good exercise :
    ) It won’t give a 3,4,5 tiling though.

  • Tasmanian Devil at 2008-02-12

    I don’t find an "R^2-covering non-(3,4,5)"graph all that appealing; I like that the (3,4,5)-restriction forces it to be R^2-covering. ;)

  • Tasmanian Devil at 2008-02-12

    Btw, I am having some serious problems with my PC at home (currently I have hooked up my old laptop in order to get online), so the ggb-files for the drawings may be lost.

  • Tasmanian Devil at 2008-02-13

    31 vertices

  • Carroll at 2008-02-13

    Take Tas example


    Numbering the outer sides of the square boundary with the number of sides of the corresponding face, is not :

    --5---4--
    3 3 3
    --4---5--
    3 3 3
    --5---4--

    a desired tiling (each of the four squares is Tas figure straight or mirror)?

    29 vertices


  • Carroll at 2008-02-13

    I try again, you need two numbers to show a triangle is not touching another one and so on :


    --5----3--
    3 35 4
    --4----3--
    --3----4--
    4 53 3
    --3----5--

  • Tasmanian Devil at 2008-02-13

    32 vertices

  • wccanard at 2008-02-13

    @Carroll: what are you trying to do? Tile R^2? Did you check there are no corners of squares which are adjacent and have the same degree? I think you have to explicitly say which way round you are putting the square: the two outside triangles have outer vertices of different degrees. Am I making any sense? When you glue the squares together the oudside vertices suddenly get big random degrees and you have to make sure there is no problems there.

  • Tasmanian Devil at 2008-02-14

    When trying to tile R^2 with equal tiles, I’ve thought of a possible approach but not gotten very far yet. The average corner angles of triangles, quadrangles and pentagons are 60, 90 and 108 degrees respectively. The sum of the angles around a given vertex in the plane must be 360 degrees. The angles will in general not actually be 60, 90 or 108, but by replacing all angles in any face by their average, the average over the vertices will be the same.

    In other words, a tile must consist of vertices such that the sum of (180 – 360 / (n-2)) over the number of sides of the faces is 360 on average.

    There are r vertices of degree 3 and r – 4 of degree 5, of which all but 4 belong to one triangle, two quadrangles and two pentagons. The averaged angle sum for the vertices of degree 3 is 60 + 90 + 108 = 258 degrees, and for almost all vertices of degree 5 it is 258 + 90 + 108 = 456 degrees. So their average is 357 degrees.

    Now let’s look at the averaged angle sum for the possible types of vertices of degree 4.

    Faces / Averaged angle sum
    (3,3,4,4) / 300
    (3,3,4,5) / 318
    (3,3,5,5) / 336
    (3,4,4,5) / 348
    (3,4,5,5) / 366
    (4,4,5,5) / 396

    Based on this one could work out possible combinations that could be the vertices of a tile. And one would have to keep in mind that the number of vertices of degree 4 should be between 1 and 1.5 times the number of vertices of degree 3.

    I don’t have time to work more on this for a few hours now.

  • Carroll at 2008-02-14

    @wccanard: yes that is what I want to do,

    let use only Tas 29 figure with rotations (no mirror), one copy can be represented like this :


    -------
    |4 3 5|
    |5 5|
    |5 3 3|
    -------
    where central number is number of edges of external faces and corner number is degree of corner vertices.

    Having four copies glued together we get different degrees for adjacent vertices (sum of degrees minus 4) :

    3 4 5 5 3 4
    -------------
    3|4 3 5|5 5 3|4
    |5 5|3 3|
    5|5 3 3|4 5 5|
    -------------
    5|5 5 3|4 3 5|
    |3 3|5 5|
    3|4 5 5|5 3 3|4
    -------------
    3 4 5 5 3 4

    let me know if I still missed something

  • Tasmanian Devil at 2008-02-14

    I am afraid I haven’t studied Carroll’s idea but I would like to ask:

    Is it possible to tile the plane with triangles, quadrangles and pentagons subject to the following restrictions?

    The vertices of each triangle have degrees 3, 4 and 5
    The vertices of each quadrangle have degrees 3, 5, 4 and 5 in that order
    The vertices of each pentagon have degrees 3, 4, 5, 4 and 5 in that order (clockwise or counter-clockwise)
    The faces of each vertex of degree 3 have 3, 4 and 5 sides
    The faces of each vertex of degree 4 have degree 3, 5, 4 and 5 in that order
    The faces of each vertex of degree 5 have degree 3, 4, 5, 4 and 5 in that order (clockwise or counter-clockwise)

  • wccanard at 2008-02-14

    @Carroll: Looks good to me!

    @Tas: Carroll has tiled the plane with faces of degrees 3, 4, and 5, but a positive proportion of his vertices have degree 20.

    @Tas again: why are you putting these extra constraints on the pentagons etc?
    For example in your earlier post you said that “almost all” vertices of degree 5 meet only one triangle. I don’t really know what you mean. In any chain of triangles the degrees of the vertices joining the chain together are 4,5,4,5,4,...
    Last thing: did you work out the average angle sum at a vertex in the configuratio you suggest in the post just above? If it’s not 360 then probably you’re already dead. Or did you rig it so that it was 360?

  • wccanard at 2008-02-14

    One last thing: I think that probably the time has come to break the news to this thread that a polygon with 4 sides is called a “quadrilateral” (in British English, at least...). My old school had a quadrangle, which did have 4 sides, but I think that the typical quadrangle is big enough to park a car in.

  • Tasmanian Devil at 2008-02-14

    The average of the sums for the vertices of degree 4 must lie in [364, 366], and the simplest thing would then be to have all of the type (3,4,5,5) for which the sum is 366. With equally many vertices of degree 3, of degree 4 and of degree 5 of the types described above, the average for all is 360. So I am wondering if we can do a tiling with only these elements. Otherwise things seem to get pretty complicated.

    It is part of the proof that there are r-8 vertices of degree 5 that only meet one triangle and only 4 others that meet two triangles. If this contradicts arbitrary amounts of chains of triangles, well, then there can’t be too many chains of triangles.

  • Carroll at 2008-02-14

    @wccanard: degrees of vertices are 3,4,5,10 and 16, I’ll try to post a drawing.
    Would you say it is an infinite alternating planar graph? Or does the problem lie on the external missing face? What if we tile a sphere or a torus?

  • Tasmanian Devil at 2008-02-14

    It seems that you have constructed an infinite alternating planar graph, but the focus is currently on (3,4,5)alternating graphs. ;) It’s not planar if you tile a torus.

  • Ingo Althofer at 2008-02-14

    I am sorry to tell you that I have to leave this
    interesting thread (now centering around alternating
    tilings of the plane) for some time.
    Semester is over (tomorrow are the last classes),
    and a non-planar island is waiting, where I will
    stay “isolated” for three weeks, only with my
    wife and the volcano. No internet, no email.
    I hope to be back in the wired world around March 10.

    Keep busy, Ingo.

  • Tasmanian Devil at 2008-02-14

    Enjoy your vacation!

  • Carroll at 2008-02-14

    Yes thanks for these interesting ideas, have a good time!

    @Tas: how do you duplicate objects (many polygons at a time) in Geogebra?

  • Tasmanian Devil at 2008-02-14

    I don’t know; I draw one line at a time...

  • ypercube ★ at 2008-02-15

    Enjoy your vacation in the torus island, Ingo :)

    (got you, FatPhil and Gregorio ;)

  • Carroll at 2008-02-15

    Here is the tile:

  • Tasmanian Devil at 2008-02-17

    OK I found an infinite (3,4,5)alternating graph. It’s so simple it’s almost boring. ;)


  • FatPhil at 2008-02-17

    Nope, too interesting, it’s askew and contains irregular shapes. This is the correct boring rendering of its tile:


    -------
    / \
    / \
    / \
    --------------+
    \ / /
    \ / /
    \ / /
    -------

  • Tasmanian Devil at 2008-02-17

    He he, very nice! I mean very boring!

  • wccanard at 2008-02-17

    We know there are the same number of triangles and pentagons in any tiling, and have upper and lower bounds for the number of quadrilaterals, but the lower bound is attained here, right? Can one get the upper bound? e.g. find a tile with 3 quadrilaterals, 2 triangles and 2 pentagons? Given the simplicity of the tile above this doesn’t seem out of the question.

  • wccanard at 2008-02-17

    PS if Ingo is trying to make a game based on this, then the above infinite tiling might make a fine board :-)

  • Tasmanian Devil at 2008-02-17

    Yes, the lower bound is attained here. But again, if we try to change anything, we have to take the average angles and things into consideration, and things get complicated very quickly.

    In order to find the last tiling, I not only restricted myself to the 3-5-4-5 quadrilaterals, but I also put restrictions on the orientations of triangles and pentagons as well as vertices of degree 3 and 5. Turned out that if the orientation of each one was to be fixed, there was essentially only one possibility, namely the one I have shown.

    The “most interesting open problem” on alternating graphs seems to keep changing; I guess now it’s how close to 3/2 we can make (v4+5)/r for (3,4,5)alternating graphs? :)

  • Tasmanian Devil at 2008-02-17

    If a tile attains the upper bound, the averaged angle sum of the quadrilaterals must be 364. It is in fact possible to achieve this with only three quadrilaterals: (3, 4, 5, 4), (3, 4, 5, 4) and (4, 5, 4, 5).

  • Tasmanian Devil at 2008-02-17

    (3,4,3,4), (4,5,4,5) and (4,5,4,5) could also work.

  • wccanard at 2008-02-17

    I think I have a tile with the required properties. 2 triangles, 3 quadrilaterals (with 3454,3454,4545) and two pentagons.

    The bad news is that I have it drawn on a piece of paper and have got a lot of housework to do, so I’m not going to spend 20 minutes making a PDF :-)

    OK so let me describe it and someone else can draw it. Sorry. The basic idea is the standard tessellation of the plane with regular octagons and squares. The trick is that I’ll make the octagon with two of the basic hexagon tiles above (deformed appropriately, of course, so the octagon is regular but the hexagons aren’t). That gives me 2 triangles, 3 quadrilaterals and two pentagons, but one quadrilateral is “different” to the other two (the one not in the octagon) and that’s the 4545 one.

    OK so here’s a bit more detail. Take a regular octagon. Label the vertices ABCDEFGH, with A at about 1 o’clock, B at 2 o’clock, C at 4 o’clock and so on, up to H at 11 o’clock. Now draw CH, HD and DG and let the midpoints be X,Y,Z; now draw the line XYZ. If I got it right, and you got it right, that has chopped up the octagon into 2 pentagons, 2 quadrilaterals and 2 triangles.

    Now put a square on top; that’s the tile!

    WARNING: we need to flip some of them over before they tessellate correctly. Take the octagon and square that we’ve made, and now pile infinitely many on top of each other. That’s a strip.

    Now flip that strip in a mirror with the axis of symmetry being up-down.
    That’s the second strip. Fit 'em together. Now flip again (back to the
    original state) for the 3rd strip. If the squares not in the octagons
    have got vertices of degrees 4,5,4,5 then you’re doing it right.

    That’s it! Sorry again for the verbal description...

    wcc

  • FatPhil at 2008-02-17


    -----
    | |
    | |
    | |
    H+-----+A
    /|\ \
    / \ \ \
    / | \ \
    / | \ \
    / \ \X \
    G+ | + B
    |\ | / \ |
    | \ \ / \ |
    | \ +Y \ |
    | \ / \ \ |
    | \ / | \|
    F
    Z | +C
    \ \ \ /
    \ \ | /
    \ \ | /
    \ \ \ /
    \ \|/
    E
    -----+D

  • Tasmanian Devil at 2008-02-17

    BRAVO!

  • wccanard at 2008-02-18

    Thanks guys :) You’ve certainly drawn what I was thinking, so if it’s not a correct 3,4,5 tiling then the error is mine not yours.

    Both the hexagon and the octagon+square give infinite tilings of the plane but I suspect that you can regard them as finite tilings too. The octagon+square can be regarded as a finite tiling of a torus, which means that TD’s fundamental formulae will not quite apply; V-E+F will be 0. I don’t know if that changes TD’s expectations for a tiling; the plane gives an unramified cover of the torus and one way of doing the maths for a 3,4,5-tiling of the plane would be to consider it as a finite tiling of the torus. Presumably the hexagon tiling also lifts to a finite tiling of the torus too (dim memories of what you get by identifying opposite edges of a hexagon); it’s just harder for me to visualise :
    )

  • Tasmanian Devil at 2008-02-18

    Yes, any tiling that is periodic in two directions can be used for a finite tiling of a torus (just stretch it a bit if necessary) but I am skeptical about torus tilings when we want planar graphs. The Heawood graph is the graph of a tiling of a torus with seven hexagons, but it is not planar.

    I just discovered another interesting property your graph possesses: Its dual is of the second type I “predicted”, with quadrilaterals of the types 3434, 4545 and 4545!

  • wccanard at 2008-02-18

    I understand that a finite graph on a torus might not be a planar graph---I’m not saying that. I’m saying that a finite graph on a torus gives an infinite planar graph simply by pulling back the graph from the torus to its universal covering space, which is the plane. The reason I mentioned it was that it enables one to apply “finite” “3,4,5-techniques” rigorously to the infinite planar graphs above.
    The problem one would have with the naive approach, i.e. drawing a huge circle within an infinite graph and analysing the finite graph that lies entirely within the circle, is that the outer face will have a huge number of faces, so some of your lemmas above (analysing finite 3,4,5-graphs) don’t apply, whereas they will all apply to the finite torus graph when the Euler formula is modified appropriately.

  • Tasmanian Devil at 2008-02-18

    OK :-)

  • Tasmanian Devil at 2008-02-18

    Here’s an alternative rendering:

  • wccanard at 2008-02-18

    That’s lovely!

  • Tasmanian Devil at 2008-02-22

    Back to the finite (3,4,5)-alternating graphs:

    We have seen that there are always exactly four pentagons with two vertices of degree 3. Each of them must either have exactly one vertex of degree 4 or have exactly one vertex of degree 5.

    But how many are there of each type among the four?

    If I counted correctly, each possible combination is represented among the ones that Frank found with at most 26 vertices. So there are no further restrictions.

    Just a minor observation.

  • Tasmanian Devil at 2008-02-28

    With FatPhil’s representation of the first infinite (3,4,5)-alternating graph above, we see that it is a subgraph of the triangular grid. I wondered if we could classify all (3,4,5)-alternating graphs that are subgraphs of the triangular grid, as this seems pretty restrictive. While I am nowhere near a complete classification, I did stumble across a new one while experimenting. The tile looks like this:



    It gives rise to the following graph:

  • wccanard at 2008-02-28

    Does mine fits into a triangular grid?

  • Tasmanian Devil at 2008-02-28

    It seems that it is only possible if we allow some edges to have length 2 units.

  • Tasmanian Devil at 2008-02-29

    Unfortunately (in my opinion), there are infintely many different (3,4,5)-alternating graphs that are subgraphs of the triangular grid. Here is a way to construct infinitely many different ones.

    Each tile is supposed to continue in the same pattern indefinitely to the right and to the left. So we can imagine coming from above in the plane and adding tiles downwards.

    We can get infinitely many different ones simply by adding tiles of the type

    (A)

    and

    (B)

    in any order. My first graph from earlier in the thread is a special case (with all tiles equal).

    If we want to create a graph containing vertices that do not belong to any triangles (a property that neither of my first two graphs has) we can stop at any point and add a tile of the type

    ©

    provided all the subsequent tiles are of the type

    (D)

    Note that these graphs have the property that any two vertices that are neighbours in the grid have different degrees, a property not shared by the graph I gave yesterday.

  • Ingo Althofer at 2008-03-10

    Hello,

    holidays are finished now. In my mailbox
    I found very interesting stuff by Dr. Karl
    Scherer. He has written a program for "Zillions
    of Games" called “Graph Puzzles”. In this program
    he presents the (17,17)Schneider Graph (in a new nice
    drawing) as well as several other alternating planar
    graphs which he found for different numbers of
    vertices/faces.

    As Karl was not aware of this thread some of his graphs
    are isomorphic to ones in this thread. Unfortunately
    Karl cannot post here, as he is not an active player
    on Little Golem :
    (

    A picture of his drawing of the (17,17)-Schneider graph
    may be found on my website, at
    http://www.althofer.de/alternating-planar-graphs.html

    Greetings, Ingo.

  • Tasmanian Devil at 2009-03-02

    OK I don’t know how to say this without sounding conceited, but may I suggest that anyone who is interested in the images I have posted in this thread download them in the near future. My old free web page provider is closing its services in a couple of months and all the contents will be deleted. (My new home page is www.neutreeko.net.)

  • Ingo Althofer at 2013-02-09

    The hot time of “alternating planar graphs” here in LittleGolem’s
    forum was almost five years ago. Now there is new progress:

    Gunnar Brinkmann (U Gent) has shown with massive computer help
    that there is no alternating planar graph with less than 17 vertices;
    and there exist exactly two non-isomorphic such graphs (both with 17
    vertices and 17 faces).

    New drawings of Schneider-17 and Brinkmann-17 can be seen
    here.

    Ingo.

  • Ingo Althofer at 2013-02-09

    Sorry, here comes the
    correct web address .

  • FatPhil at 2013-02-10

    Good stuff!

    How “massive”?

  • Ingo Althofer at 2013-02-11

    Hi Phil,

    you mean the 3d-printed body, right?
    It is somewhat heavier than water.
    It is stable (no problem to throw it from one meter height on solid ground).
    It is thermally stable until 120 degree Celsius.

    The process of printing took almost three hours.
    The cartridges for the 3-d-printer are rather expensive.
    The price for the material in the Schneider-17 is
    between 100 and 150 Euro.

    I have added a new picture making clear the size of the 3d-print.
    Click at the link in my answer above. (Also, now all text on the site
    is in English.)

    Ingo.
    Cheers, Ingo.

  • FatPhil at 2013-02-11

    nope, how massive was the computer effort?

  • Ingo Althofer at 2013-02-11

    I see.

    From a mail by Gunnar Brinkmann:
    > For 17 nodes 18,927,037,827,561 graphs were tested. It took about 214 CPU days.

    Ingo.

    PS: Gunnar Brinkmann asked me to call his graph not Brinkmann-17, but
    Gent-17. (He is at Gent University.) So I did.

  • Hjallti at 2013-02-17

    If I read this I am really sad I have up my request when I was in third year of my university, when I wanted to make my Master-thesis in Graph-theory, but the prof in Louvain for some reason kept me waiting... should have changed university and gone to Gent that year...
    I got my PhD but I would have been much more interested and capable in research in this area I think... :-(

  • Ingo Althofer at 2013-09-13

    Hello, some news. Based on the fact that one
    discoverer of a 17-vertex-apg is Frank Schneider
    (“Schneider” is German and means “taylor”) and that
    Ghent (the city behind apg Gent-17) was/is famous
    for manufacturing and dealing with broadcloth, I
    designed a new board game “Schneider von Gent”.
    The game board is either Schneider-17 or Gent-17.

    Rules and pictures of a prototype can be found
    here.

    Ingo.

    PS: The design is already from March 2013. However, it took
    me a while to set up the website.

  • Ingo Althofer at 2015-05-30

    Hello everybody,
     
    in some cases time is dropping slowly. Finally, a paper has been published in
    “ARS MATHEMATICA CONTEMPORANEA”, Volume 8 (2015).
     
    Title is “Alternating Plane Graphs”.
    Authors are Jan Kristian Haugland (Norway, Karl Scherer (New Zealand), Frank Schneider (Germany),
    Nico van Cleemput (Belgium), and me. The paper includes some ideas from other participants in this
    thread. These participants are mentioned in the acknowledgements.

    The paper (pdf with 27 pages) is freely available at
    <!--  
     -->this place
    .

    Cheers, Ingo.
     

Return to forum

Reply to this topic




Include game board: [game;id:123456] or [game;id:123456;move:20] or [game;id:123456;move:20;title:some text]