generalized graph



A generalized graph in the sense of HRY is a generalization of the notion of a pseudograph given at graph (see in particular Definition in terms action on a set of half edges). By adding structure like directions for the edges, we can define a wheeled graph which is a generalization of a directed pseudograph. What differentiates a generalized graph from a pseudograph and a wheeled graph from a directed pseudograph is the notion of an “exceptional cell,” which should be thought of as a set of half edges which have no vertices.

A generalized graph can be visualized as a set of vertices with half edges attached to them, a rule for attaching half edges to glue the vertices together, and potentially some half edges (flags) that are attached to only one or zero vertices. For instance, a particularly simple generalized graph is one with no vertices and one edge.


The following is Definition 2.2 of HRY:


A generalized graph GG is a finite set Flag(G)Flag(G) with:

  • a partition of Flag(G)= αAF αFlag(G)=\coprod_{\alpha\in A} F_\alpha into cells with AA finite,

  • a distinguished partition subset F ϵF_\epsilon called the exceptional cell,

  • an involution ι\iota satisfying ιF ϵF ϵ\iota F_\epsilon\subseteq F_\epsilon,

  • and a free involution π\pi on the set of ι\iota-fixed points of F ϵF_\epsilon.

Given a generalized graph GG, Definition 2.3 of HRY gives some useful terminology:

  1. The elements of Flag(G)Flag(G) are called flags. A flag in a non-exceptional (resp. exceptional) cell is called an ordinary flag (resp. exceptional flag).
  2. Call GG an ordinary graph if F ϵF_\epsilon is empty.
  3. Each non-exceptional partition subset F αF ϵF_\alpha\neq F_\epsilon is called a vertex. The set of vertices is denoted by Vt(G)Vt(G). An empty vertex is an isolated vertex. A flag in a vertex is said to be adjacent to or attached to that vertex.
  4. An ι\iota-fixed point is a leg of GG. The set of legs is denoted by Leg(G)Leg(G). An ordinary leg (resp. exceptional leg) is an ordinary (resp. exceptional) flag that is also a leg. For an ι\iota-fixed point xF ϵx\in F_\epsilon, the pair {x,πx}\{x,\pi x\} is called an exceptional edge.
  5. A 2-cycle of ι\iota consisting of ordinary flags is called an ordinary edge. A 2-cycle of ι\iota contained in a vertex is a loop. A vertex that does not contain any loop is called loop free. A 2-cycle of ι\iota contained in the exceptional cell is called an exceptional loop.
  6. An internal edge is any 2-cycle of ι\iota. An edge is an internal edge, an exceptional edge, or an ordinary leg. The set of edges of GG (resp. internal edges) is denoted Edge(G)Edge(G) (resp. Edge_i(G))$.
  7. An ordinary edge e={e 0,e 1}e=\{e_0,e_1\} is said to be adjacent to or attached to a vertex vv if either e 0e_0, e 1e_1 or both are adjacent to vv.

Extra Structure

There are a number of important structures that a generalized graph can possess which will be useful in using them to describe . The following is again from HRY:


Suppose GG is a generalized graph. Fix a (possibly infinite) set of colors 𝒞\mathcal{C}.

  1. A coloring of GG is a function Flag(G)κ𝒞Flag(G)\overset{\kappa}\to \mathcal{C} that is constant on orbits of ι\iota and π\pi.

  2. A direction for GG is a function Flag(G)δ{1,1}Flag(G)\overset{\delta}\to \{-1,1\} such that

    • if ιxx\iota x\neq x, then δ(ιx)=δ(x)\delta(\iota x)=-\delta(x),
    • and if xF ϵx \in F_\epsilon, then δ(πx)=δ(x)\delta(\pi x)=-\delta (x).
  3. For GG with direction, an input (resp. output) of a vertex vv is a flag xvx\in v such that δ(x)=1\delta(x)=1 (resp. δ(x)=1\delta(x)=-1). An input (resp. output) of GG is a leg xx such that δ(x)=1\delta(x)=1 (resp. δ(x)=1\delta(x)=-1). For uVt(G){G}u\in Vt(G)\cup \{G\}, the set of inputs (resp. outputs) of uu is written in(u)in(u) (resp. out(u)out(u)).

  4. A listing for GG with direction is a choice for each uVt(G){G}u\in Vt(G)\cup \{G\} of a bijection of pairs of sets

    (in(u),out(u))l u({1,,|in(u)|},{1,,|out(u)|}). (in(u),out(u))\overset{l_u}\to(\{1,\ldots,|in(u)|\},\{1,\ldots,|out(u)|\}).

Thus, using these properties, we can model and with generalized graphs. See there and for more.


  • , and . Infinity Properads and Infinity Wheeled Properads, Lecture Notes in Mathematics, 2147. Springer, Cham, 2015. (arxiv version)

  • . Graphs, hypergraphs, and properads, arXiv:1407.3744.

Last revised on July 18, 2016 at 05:26:48. See the history of this page for a list of all contributions to it.