Sandbox:DavidKohler/Relativized Alon Conjecture/Directed graph

In our work, a directed graph is the most fundamental object. Our notion of graph is built upon it.

Definition

A directed graph or digraph is a tuple G = (V_G, E_G, t_G, h_G) where V_G and E_G are disjoint sets and t_G and h_G are maps:

V_G is called the vertex set and its elements are the vertices,
E_G is called the (directed) edge set and its elements are the edges,
t_G: E_G → V_G is the tail map and
h_G: E_G → V_G is the head map.

Example

To do.

Basic terminology

The tail of a directed edge e is the vertex t_G(e),
The head of a directed edge e is the vertex h_G(e),
A directed edge e is called a self-loop if its tail and head are the same vertex.

Morphisms

Let G and H be two directed graphs, a morphism of directed graph φ: G → H is a pair (φ_V, φ_E) where φ_V: V_G → V_H is a map of vertices and φ_E: E_G → E_H is a map of edges satisfying

h_H φ_E = φ_V h_G
t_H φ_E = φ_V t_G

With this notion of morphisms, directed graphs form a category.

Adjacency

The head and tail vertices of an edge are said to be adjacent. Adjacency relationships in a graph are captured by an adjacency matrix. Given an ordering {v₁, ..., v_n} of the vertices, the corresponding adjacency matrix is the n×n matrix A_G whose i, j coefficient is the number of directed edges e whose tail is the vertex v_i and whose head is the vertex v_j.

The eigenvalues of the adjacency matrix, which are independent of the choice of an ordering of the vertices, are called the graph eigenvalues and are one of the main object of study of this work.

In the litterature

As can be seen on Wikipedia, there are several variations on the definitions of graphs. For some authors, our definition is a multigraph or a pseudograph (some allow loops, some do not). In our language, what is commonly referred to as a graph is a simple undirected graph.

Also quivers.