Free Graphs, Maps on Graphs

Maps on Graphs

A map f from one graph to another takes vertices to vertices, and open edges to open edges, such that f respects the initial and terminal vertex of each edge. (A loop maps to a loop, not a path that wanders out along an edge and then back to the same vertex.) When graphs are viewed as cw complexes, f is continuous. As f carries an edge onto an edge, it could compress parts of the edge and expand others; but the ends are fixed. Use a homotopy to make the map linear. Thus, if you only care about the homotopy class of f, it is enough to map vertices and edges. This is more than just a simplicial map. There may be several edges from a to b, and these can be mapped, in different ways, into the various edges that connect f(a) and f(b).

Show, by continuity, that a sequence of points approaching c, inside an edge, cannot map to a sequence of points that approaches a vertex. Only the ends of an edge map to the ends of an edge.

Each edge maps surjectively onto its image edge. This is implied by continuity, and endpoints mapping to endpoints. It's really the intermediate value theorem; you have to cover the whole edge to get from here to there.

Assume f is injective, or bijective, from one edge to another. Plot x,f(x) from 0,0 to 1,1. If f is not strictly increasing then two values of x have the same f(x). (Use the intermediate value theorem again.) Therefore f is strictly increasing, and invertible, on this edge. Apply f to the closed interval, and f takes a compact space onto a hausdorff space bijectively, hence it is a homeomorphism. Therefore f, on a given edge, is injective iff it is bijective, iff it is strictly increasing, iff it is invertible, iff it is a homeomorphism.

If you like category theory, graphs are objects and maps are morphisms. The identity map is the identity morphism. A subcategory assumes f is bijective on each edge. A further subcategory assumes f is linear; thus morphisms are determined by the assignment of vertices and edges to vertices and edges. Unless otherwise stated, this is the category we will be working in.

The star of a vertex is the vertex and the set of edges leaving a vertex. Let f be a map between graphs. We say f is star injective if f(u) = v implies the star at u maps injectively into the star at v. Similarly, star surjective means the star at u maps onto the star at v, and star bijective is star injective and star surjective. If f is star surjective, and v is the initial vertex of a path downstairs, and a preimage u is selected, the path can be lifted. Simply lift each edge in turn. If f is star bijective, the lift is unique. In fact, the preimage of a small enough neighborhood about any vertex or any point on an edge is a disjoint union of homeomorphic copies of that neighborhood, hence the map is a covering space . A hexagon covers a triangle, as does a dodecagon, or an infinite line.

Conversely, any covering space consists of vertices and edges, and the projection is star bijective.

Every graph is locally simply connected, so a simply connected universal cover (tree) can always be built. In fact, we can build a covering space for every subgroup of the fundamental group. This is how the triangle was covered by the hexagon; The subgroup 2Z within Z.

Star Ijective Embeds

If f is a star injective function from H into G, then f embeds π1(H) into π1(G). The idea is simple. Extend H to a covering space G~ over G. Include H into G~, and project G~ onto G. Each step is injective on the fundamental group, hence the composition embeds π1(H) into π1(G).

Constructing G~ is not hard, assuming the preimage of each component is a connected component. Do the following for each component of G. Select base points b~ in H and b in G. Lift all paths of length 1. If a path has no preimage, add a new edge and vertex to H. Now all paths of length 1 lift, and lift uniquely. Do the same for paths of length 2, and 3, and so on, building an ascending chain of graphs. The union is G~, which covers G; and that completes the proof.