nLab semi-graph

Introduction

A semi-graph is like a graph (more precisely, an undirected, simple graph, possibly with loops) but where certain edges may be ‘open’ or ‘half-open’: they may have a vertex at only one end, or at neither end. As usual, edges can only be joined at vertices. A vertex is typically indicated by a solid dot (possibly with a label), an end of edge without a vertex is typically indicated by a hollow dot (never with a label).

Here is a quick example, which has one edge without any vertices, and two edges with only one vertex.

Preliminaries

Throughout this page, we pick a set with exactly one element, and denote it $1$.

Details

The following definition follows Mochizuki2006.

Definition

A semi-graph consists of a set $V$, a set $E$ whose elements are sets with exactly two elements, and, for every element $e$ of $E$, a map $\zeta_{e}: e \rightarrow V \sqcup 1$.

Terminology

Let $G$ be a semi-graph. A vertex of $G$ is an element of $V$. An edge of $G$ is an element of $E$. An edge $e$ of $G$ abuts to a vertex $v$ of $G$ if $v$ belongs to the image of $\zeta_{e}$. We refer to an element of an edge $e$ of $G$ as a branch of $e$.

Remark

In particular, every edge of a semi-graph has exactly two branches, but it is possible that neither, both, or only one of the branches abuts a vertex. Thus we think of an edge $e$ as subdivided into two branches $b_{1}$ and $b_{2}$, and do not think of the meeting point as a vertex of the graph; but always consider the other end of each branch as a vertex, either ‘closed’ (the branch maps to an actual vertex of $G$ under $\zeta_{e}$) or ‘open’ (the branch maps to $1$ under $\zeta_{e}$).

References

• Semi-graphs of anabelioids, Shinichi Mochizuki, Publ. Res. Inst. Math. Sci., 42, No. 1, 221-322 (2006). paper Zentralblatt review