Sandbox:DavidKohler/Relativized Alon Conjecture/Graph

Roughly speaking, we understand graphs as undirected versions of a directed graph. Undirected edges are matched opposite directed edges under some involution.

Definition

A graph or undirected graph is a tuple (G, ι_G), where G = (V_G, E_G, t_G, h_G) is a directed graph and ι_G: E_G → E_G a map satisfying the following conditions:

the map ι_G is an involution, that is ι_G² = id_{E_G} and
the involution commutes the tail and head maps, that is ι_G t_G = h_G ι_G.

Properties

The involution commutes the tail and head maps both sides, that is ι_G h_G = t_G ι_G.
The involution maps self-loops to self-loops.

Basic terminology

An edge or undirected edge consists of a pair of directed edges e and ι_G(e). In other words, the edges of a graph are the equivalence classes of the directed edges under the involution. Given a directed edge e, we call the directed edge ι_G(e) its opposite or paired directed edge.
In the case of self-loops, we call the edge a whole-loop if the involution is pairing two distinct self-loops and we call it a half-loop if the involution is mapping a self-loop onto itself.
When necessary to distinguish the set of edges from the underlying set of directed edges, we denote the underlying set of directed edges by ${\vec {E}}_{G}$ .

Morphisms

Let G and H be two graphs, a morphism or graphs is a morphism of directed graph φ = (φ_V, φ_E) satisfying the additional condition that ι_H φ_E = φ_E ι_G, in other words, morphisms preserve opposite edges. This constitutes graphs as a category.

Whole-loops and half-loops

A longer discussion here, includes incidence, weight in adjacency and homotopy difference of these two cases.

Oriented and labelled graph

An orientation of a graph G is the choice of a directed edge as a representative for each edge (since an edge is an equivalence class of directed edges). Half-loops consist of only one directed edge, so there isn't much to do there and for whole-loops, the choice doesn't make a great difference. It really is in the case of edges with distinct tail and head that the choice of an orientation becomes critical.

Given an oriented graph G, we can assign labels (not necessarily distinct ones) to each oriented edge and we call this an oriented labelled graph. This allows for example to simply describe walks in an oriented graph. When traversing an edge in the opposite direction of its orientation, the label is read as an inverse.