Here we allow a graph to have both parallel edges and self-loops. Such a graph is sometimes called a pseudograph or a general graph. We distinguish a graph having neither parallel edges nor self-loops as a simple graph; a graph having parallel edges but no self-loops is distinguished as a multigraph. We will only consider graphs whose vertex sets and edge sets are finite. Graphs (but not, later, maps) are allowed to be disconnected.
The most important graph coloring is a coloring of the vertices of a graph in two colors consistent with a rule that no two vertices of the same color may share an edge. Unless otherwise stated, graph colorings are assumed to be vertex colorings, so such a vertex coloring is often simply called a proper bicoloring of the graph; or, still more simply (since there is infrequent need to discuss improper colorings that disobey the rule,) a bicoloring of the graph.
A bicoloring is not always possible. The graph on the left side of the figure above is an example. Any self-loop (the example has two of them) violates the coloring rule that the vertices at the two ends of an edge will be differently colored. A graph whose vertices can be properly two-colored is called bipartite (example in the center of the figure;) a graph that has indeed been colored in such a way is called bicolored. A graph is bipartite if and only if all of its cycles have even length. (Thus, all trees are bipartite since they have only cycles of zero length.)
As it turns out, there are only two ways to bicolor a given bipartite graph—the one option is to swap colors. Nonetheless, given a bipartite graph, we do not yet have a bicolored graph until we actually make this bivariate choice of coloring.
A graph concerns things called vertices and edges, and a relation between them called connection or incidence. We habitually draw dots for vertices and draw line segments for edges. What we seldom notice is that the line segments are doing double duty: representing both the edges and the "connection" relation. Suppose instead we draw black dots and call them "vertices," and draw white dots and call them "edges," and we use line segments purely to represent connection. In this more fastidious kind of graph drawing, the pseudograph as drawn at the left above is meaningless; what we really wanted to express there, is drawn in the proper way on the right side of the figure as a bicolored multigraph.
Recapping, when we drew a pseudograph in this fastidious new way, we ended up with a multigraph that was bicolored: a multigraph having white vertices subdividing the line segments we formerly designated as edges. We will call this new kind of graph drawing a König representation of the graph. It is simple to convert a naive graph drawing to a König representation: just subdivide every edge in the drawing with a white vertex.
Going further, we can liberate ourselves from a world where every white vertex in a König representation is 2-valent. What we need is a generalization of the concept of a graph called a hypergraph. More particularly, we need a hypergraph with multiplicity, what Babaev terms a pseudo-hypergraph. I prefer the term multiset hypergraph.
Definition: A multiset hypergraph is a generalization of the concept of a graph such that every bicolored multigraph is a König representation of a multiset hypergraph.
An edge (or hyperedge) in a multiset hypergraph is allowed to connect to any of its vertices with multiplicity n, where n is any non-negative integer. (Since the connection relation is reciprocal, we may put it the other way around: each vertex is allowed to connect to each of its edges with multiplicity n, where n is any non-negative integer.) We can phrase this in terms of the incidence matrix of the graph, that is, the matrix where rows represent vertices, columns represent edges, and the entries are the multiplicity of connection between each vertex and edge.
Alternate Definition: A multiset hypergraph is a generalization of the concept of a graph such that every matrix of non-negative integers is the incidence matrix of a multiset hypergraph.
A multiset is a generalization of the idea of a set where members are allowed to appear more than once (they may only appear once in a set.)
Sets are familiarly illustrated with Venn diagrams, where overlapping closed curves show set intersection. In a similar way, multisets can be diagrammed with amoeba diagrams, where wiggly, closed, and sometimes self-overlapping curves express the idea of multiple inclusion. Black dots in the amoeba diagram represent vertices. The closed curves represent edges. Overlaps of the curves (edges) only count when they contain a dot (vertex)—the purpose being to count multiplicity of inclusion.
An amoeba diagram of a set hypergraph, shown above with its incidence matrix on the left, has edges that singly include certain vertices. An amoeba diagram of a multiset hypergraph, shown above with its incidence matrix on the right, has edges that multiply include certain vertices. In the following, for brevity, the term "hypergraph" will mean "multiset hypergraph."
We can obtain the König representation of a hypergraph from its amoeba diagram by imagining the amoebas to "deflate," contracting their "legs" to line segments, their "torsos" to white vertices:
In the deflation process, what was formerly the incidence matrix of the hypergraph is rechristened the biadjacency matrix of the König representation.
In the figure below, the simplest hypergraphs are shown as both amoeba diagrams and König representations. They are, left to right: an isolated vertex; an empty edge; 1-, 2-, and 3-brins; two parallel 1-brins; and a classical edge.
Notice that the formerly sharp distinction between a self-loop and a brin ("sprig" in French) was a mirage: a self-loop is just a 2-brin.
A general graph is said to be properly embedded if it lies in a smooth, closed, surface in such a way that edges cross each other only at vertices; and such that all that would remain of the surface if the multigraph's edges were to be deleted, would be a disjoint union of topological disks. For example, the skeletal graph of a tetrahedron can be drawn on the torus in a variety of inequivalent ways, two of which are shown in the figure below:
The embedding on the right is a proper embedding. The embedding on the left is an improper embedding because one of its faces is not a disk.
Definition: A multiset hypergraph is said to be properly embedded in a surface if its König representation is.
It is not always possible to properly embed a given König representation in a given surface. Nonetheless, it is a theorem that every multigraph (in fact, every general graph) has a proper embedding in some surface. Most commonly, the König multigraph can be properly embedded in a spectrum of topologically different surfaces, often it can be properly embedded in multiple inequivalent ways in each.
Definition: A hypermap is a smooth, closed, connected surface taken together with a proper embedding of a König representation of a hypergraph in the surface, considered up to homeomorphism.
By "up to homeomorphism" we mean that we are only interested in these embeddings as topological objects: if two hypermaps can be brought into congruence by a smooth deformation (homeomorphism) of the underlying surfaces, they are, and were always, the same hypermap. Since only a connected graph can be properly embedded in a connected surface, there are, by definition, no disconnected hypermaps. We will also specifically exclude isolated vertices and empty edges from becoming maps, so the smallest and simplest hypermap is an embedding of a 1-brin in the sphere:
What will interest us about hypermaps is their representation as colored maps.
The Walsh representation is simply a drawing of the König representation on the surface. Note the distinction: the König representation represents an abstract hypergraph (i.e., an unembedded hypergraph,) while the Walsh representation represents a hypermap (an embedded hypergraph.) So the figure above is the Walsh representation of a 1-brin in the sphere.
Given any map, there are other maps related to it via map operations. Map operations will be our guide in seeking alternatives to the Walsh representation. Map operations are not defined to operate on colored maps, but a simple principle of color inheritance works well. For example, in the familiar (Poincaré) dual, new faces descend from old vertices, so they should inherit their colors. Map operations and their compositions are written in an abbreviated two-letter functional notation that is self-explanatory. For example, the insertion of vertices at the midpoint of edges (used earlier in constructing the König representation) is the action of the map operation subdivide:
W= Su(M)
where W is the Walsh representation of some ordinary map M. (It must be understood that the new vertices inserted by subdivide are to be colored white.)
The Chess representation is:
X = Du(W),
where the map operation (Poincaré) dual, turns W into a representation with black and white regions representing the hypervertices and hyperedges respectively. New pink vertices represent the hyperfaces. Because the Walsh is bipartite (all cycles have even length) its dual is Eulerian and chess-colorable (all vertices have even valence, and the map is face 2-colorable.) Below are the Walsh representation of a 1-brin on the sphere (left) with its dual, the Chess representation (right.)
The James representation is:
J = Le(W) = Tr(Du(W)) = Du(Ki(W)),
where the newly referenced map operations are leapfrog, truncate, and kis. This gives a 3-regular map with black, white, and pink regions representing hypervertices, hyperedges, and hyperfaces respectively. The James is expressed most simply as the truncation of the Chess representation. Below, for the 1-brin on the sphere, the Chess representation (left) and James representation (right.)
The Belyi triangulation is:
B = Du(Le(W)) = Ki(W),
which gives a triangle-faced map with a proper vertex 3-coloring. The Belyi is dual to the James. Below, the James representation (left) and its dual, the Belyi triangulation (right.)
The Belyi triangulation can just as easily seen as the kis of the König representation—the König representation is triangulated by placing a new vertex in the center of each face and connecting the new vertex to the old, surrounding vertices with lines.
If the surface is oriented, the Belyi triangulation also has a chess coloring (a proper face 2-coloring). Use the orientation of the surface to color each triangular face + or - according to whether its three vertices run black/white/pink counter-clockwise or clockwise.
The Cori representation is:
C = Me(W),
where the newly referenced map operation is medial, gives a 4-regular map with black, white, and pink regions representing hypervertices, hyperedges, and hyperfaces respectively. Below, the Walsh representation (left) and its medial, the Cori representation (right.)
The Quad representation is:
Q = Ra(W) = Du(Me(W)),
where the newly referenced map operation is radial, which gives a quadrilateral-faced map where each quadrilateral has black and white vertices on one diagonal and pink vertices on the other. The quad representation is dual to the Cori. Below, the Cori representation of a 1-brin on the sphere (left) and its dual, the quad representation (right,) having a single quadrilateral face.
No comments:
Post a Comment