Undip words for bipartite baskets

A bipartite map is a map that admits a two-coloring of the vertices such that no edge connects two vertices of the same color. Bipartite maps have duals that are chess-colorable. The map operations radial, Ra(), ortho, Or(), and bevel, Be(), yield maps that are bipartite when the base map is orientable. Only bevel guarantees that the resultant map is trivalent, that it is hamiltonian if the base map is connected, and that the dual triangulation is eulerian.



The quadrilateral truchet tiles for these map operations can be suitably pre-colored to show that the result is bipartite: in radial, the new vertices can be given the same color; in ortho, the central vertex can be given a different color; in bevel, diagonal pairs of vertices can be given the same color.

Guitter, Kristjansen, and Nielsen in an article on statistical dynamics and 2D quantum gravity, Hamiltonian Cycles on Random Eulerian Triangulations, have, in effect, counted the number of undip words of length 2n that describe bipartite baskets.




The integer sequence of undip words for bipartite baskets, starting {2, 8, 40, 228, 1424... } is cataloged as sequence A116456 in the Online Encyclopedia of Integer Sequences. The sequence for general baskets, starting {2, 10, 70, 588, 5544...} is A005568.

Bipartite undip words include:

synonyms for the theta graph, e.g., ud

synonyms for the digonal prism, e.g., udud

synonyms for the cube, e.g., uunnddpp.

Non-bipartite undip words include:

synonyms for the tetrahedron, e.g., undp

synonyms for cuneane, e.g., uunddupd.