Find a concept
Start typing to search the mathematical index.
Section
Graphs and lattice structures for statistical mechanics.
See the ergodic theory reading paths for the surrounding constructions and theorems.
A (simple, undirected) graph is an ordered pair where:
If , then:
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.
The degree of a vertex in a simple undirected graph is
It counts the neighbors of . The degree may be infinite.
If has positive upper Banach density, then for every there exist integers and such that
In particular, the conclusion holds for a subset of with positive ordinary upper density. This is Szemerédi's theorem.
Ergodic theory studies measure-preserving dynamics through invariant events, time averages, recurrence, and mixing. These reading paths connect its probability foundations with Koopman representations, operator algebras, and arithmetic examples.
For the regularity and domain questions behind Lie-group generators, see Smooth and distribution vectors: a reading path.