Wednesday, April 1, 2015

A bijection between plain-woven baskets and hypermap dual pairs


The facial walk of a hyperface, envisioned here as simple cycle. The black dots are hypervertices, the white dots are hyperedges. In the general case, for example, a facial walk that is a walk around a tree, hypervertices and hyperedges  may appear in the walk with multiplicity greater than one.

The canonical (Eulerian) triangulation places a dot of a third color in the center of the hyperface (inspired by Good n Plenty candy, we'll use pink,) and constructs lines (with multiplicity if needed) to each hypervertex and hyperedge in the facial walk.

The canonical (Eulerian) triangulation of a hypermap is constructed by placing a pink vertex in the center of each hyperface and construction lines (with multiplicity if needed) to each hypervertex and hyperedge in the facial walk.

The canonical triangulation is an Eulerian triangulation, meaning there are an even number of triangles incident to each vertex (whether black, white, or pink.) It is also a tripartite graph, meaning it can be colored in three colors such that no edge connects two vertices of the same color. We are clearly in the possession of one such black-white-pink coloring, but the other five permutations of these colors work just as well. Each color permutation is the canonical triangulation of another hypermap. Here are the six arranged in dual pairs. (Hypermap duals are related by a rotation of black and pink—an interchange of hypervertices and hyperfaces—in their canonical triangulations.)

A six-pack of hypermaps: the six color permutations (Lins trialities) of a hypermap when shown in its canonical triangulation. Black = hyper vertex; White = hyper edge; Pink = hyperface. Canonical triangulations that differ by an exchange of black and pink (hypervertices and hyperfaces) represent dual pairs of hypermaps.

A dual pair of hypermaps becomes a plain-woven basket in this way: re-color the Pink vertices Black, then delete all Black-Black edges. 

Clearly, each hypermap in a dual pair yields the same bicolored, quad-faced map. Given a weaving convention to map Black/White to Left/Right helical-handedness, a bicolored, quad-faced map explicitly describes a plain-woven basket. (Some may prefer the dual representation of a plain-woven basket: a chess-colored 4-regular map.)

Fragments of the three baskets generated by the three dual pairs above.


The inverse mapping (i.e., from a bicolored, quad-faced map to a dual pair of hypermaps) is accomplished in this way: diagonalize every quad by adding a Black-Black edge; there are now exactly two ways to recolor the Black vertices with either Black or Pink that do not result in an edge with two ends of the same color—these two colorings are the canonical triangulations of a dual pair of hypermaps.