Hypergraphs are generalizations of graphs where a (hyper)edge is now a multiset (of any cardinality) of vertices. By contrast, in a simple graph an edge is a unique, cardinality-2 set of vertices. In a multigraph (parallel edges being allowed) uniqueness is no longer required. In a general graph (self-loops being allowed) an edge is a cardinality-2 multiset of vertices. By allowing the multiset of a hyperedge to have any cardinality, hypergraphs make a vast generalization of ordinary graphs: a hyperedge can connect any number of vertices, each with any degree of multiplicity. For example, there are only two graphs on one edge, but an infinity of hypergraphs on one hyperedge.
Surprisingly, when hypergraphs are embedded in surfaces they are easy to draw. For example, in the Walsh representation of hypermaps, they are simply bipartite, ordinary maps, embedded and drawn the same old way, but endowed with a proper 2-coloring of the vertices: the vertices have been colored black or white such that no edge connects two vertices of the same color. On many ordinary maps such a bicoloring is not possible; a map is said to be bipartite if such a bicoloring is possible.
Given an ordinary map, we can make it bipartite, and, in fact, bicolored, by inserting a white vertex in the middle of each edge. (In doing so, we have doubled the number of edges in the graph, and moved deeper into the combinatorial explosion of maps--the illusion that hypermaps are a subset of ordinary maps is just that.) This way of drawing a hypergraph lets us stay in the vocabulary of ordinary graphs if we wish. We just need to keep in mind that the white vertices represent generalized edges, octopi that can connect to any number of vertices with any multiplicity. For example, above is a hypermap expressing the idea that a particular friendship involves Peter, Paul, and Mary... and Peter twice.
In addition to the Walsh representation, there are five more classical representations of hypermaps. Only Walsh, Cori, and James are named for their first proponents, T.R.S. Walsh, Robert Cori, and Lynne D. James. For brevity, I have taken the liberty to call the "canonical triangulation" that arises in the study of Belyi functions,'Belyi'; and the checkerboard coloring lately championed by Bernardi and Fusy, 'Chess'; and what may be termed the 'canonical quadrangulation'--the canonical triangulation less the edges of the underlying bipartite graph, 'Quad'.
The chart above is explained in this earlier post.
Taking Walsh, which is the most intuitive and easiest to talk about with old vocabulary, as the ancestor, the other five are easily described as descendants by map operations. In fact, besides Dual, the only two map operations needed are Medial ('Ambo' in Conway polyhedron notation) and Kis (central triangulation of faces, also called stellation, or omnicapping.) Note: it is an error to use the same color (white) for faces and vertices in the Walsh representation. Once that is corrected (Walsh faces here are pink) all the other representations can receive their coloring by descent. That is, for example, if a face ultimately derives by map operations from a black vertex in Walsh, it is colored black. Both Cori and its dual, Quad, can be seen as diagrammatic of basket weaving, the one, as sparse weaving, the other as dense weaving. In those interpretations, the colors black and white code the same helical handedness.
No comments:
Post a Comment