Section
Discrete Structures
Graphs and lattice structures for statistical mechanics.
A (simple, undirected) graph is an ordered pair where:
- is a set of vertices (or nodes).
- is a set of edges, where each edge is a 2-element subset .
If , then:
- and are the endpoints of the edge,
- and are adjacent (neighbors), and
- the edge is incident to each of its endpoints.
A graph-vertex-edge is finite if its vertex set is finite. For a simple graph, this implies is finite as well.
If and , then for a simple undirected graph,
Handshaking identity (useful fact). For a finite simple undirected graph,
Fix a positive integer . The integer lattice in dimension is
where denotes the integers.
Elements are often called lattice sites or lattice points.
A finite box (or finite cube) in the integer lattice is a region of the form
where is a nonnegative integer.
This is the cube centered at the origin with side length (in lattice units). Its cardinality is
Let be a finite subset of vertices in a graph. In the lattice setting, take with adjacency given by nearest-neighbor-zd.
Write if and are adjacent.
Outer (external) vertex boundary. The outer boundary of is
These are the vertices outside that are one step away from .
Inner (internal) vertex boundary. The inner boundary is
These are the vertices inside that have at least one neighbor outside.
Edge boundary. The edge boundary (also called the set of cut edges) is
On the integer lattice , two sites are nearest neighbors, written , if they differ by in exactly one coordinate and agree in all others.
Equivalently, using the norm,
where .
A convenient characterization is:
where is the -th standard basis vector.
A directed acyclic graph, or DAG, is a directed graph with no directed cycle. In particular it has no loop. Reachability by a positive-length directed path is then a strict partial order: concatenation gives transitivity, while acyclicity excludes a path from a vertex to itself.
A directed cycle is a directed path , , such that and are distinct. A loop is a cycle of length one.
A directed graph is a pair with . An ordered edge , written , has source and target . This convention allows loops and allows both and ; additional hypotheses can exclude them. There are no parallel copies of an edge when is a set.
A directed path of length in a directed graph is a sequence with for . A length-zero path consists of a single vertex.
Every countable graph with degree at most has a proper -coloring.
A proper vertex coloring of a graph by a color set is a function satisfying
A proper -coloring uses . Some available colors may be unused.
For an indexed family of sets , its intersection graph has vertex set and an edge between distinct labels exactly when
When the sets are supports, this is a support intersection graph. Enlarged supports may be used to account for later localization or differentiation.