A homogeneous graph is a graph $G$ such that any isomorphism between two finite induced subgraphs of $G$ can be extended to an automorphism of $G$. This property implies a very high degree of symmetry within the graph, meaning that, in a strong sense, "locally, the graph looks the same everywhere."
Characteristics
The definition of a homogeneous graph implies several key properties regarding its symmetry:
- High Automorphism Group Activity: The automorphism group of a homogeneous graph is generally very large and acts transitively on various types of subgraphs.
- Local-Global Principle: The local structure of the graph strongly dictates its global structure. If two finite parts of the graph (as induced subgraphs) appear identical, then there exists a symmetry of the entire graph that maps one part onto the other.
- Vertex Transitivity: All vertices in a homogeneous graph are structurally indistinguishable; for any two vertices $u$ and $v$, there exists an automorphism of $G$ that maps $u$ to $v$.
- Edge Transitivity: If a homogeneous graph contains edges, then all edges are structurally indistinguishable; for any two edges $e_1$ and $e_2$, there exists an automorphism of $G$ that maps $e_1$ to $e_2$.
Finite Homogeneous Graphs
The set of finite homogeneous graphs is quite restricted and has been completely classified by R. G. Woodrow and L. Lachlan. A finite graph $G$ is homogeneous if and only if it belongs to one of the following categories:
- It is a disjoint union of complete graphs of the same size. For example, $kK_n$ (a graph consisting of $k$ disjoint copies of the complete graph $K_n$).
- Its complement is a disjoint union of complete graphs of the same size. This means the graph itself is a complete multipartite graph where all parts have the same size, such as $K_{n,n,\dots,n}$.
Examples of finite homogeneous graphs:
- Complete graphs ($K_n$): A graph where every pair of distinct vertices is connected by an edge. Any permutation of vertices is an automorphism.
- Empty graphs ($\bar{K}_n$ or $nK_1$): A graph with $n$ vertices and no edges. Any permutation of vertices is an automorphism.
- Disjoint unions of equal-sized complete graphs: For instance, $2K_3$ is a graph composed of two separate triangles.
- Complete multipartite graphs with equal-sized parts: For instance, $K_{n,n}$ (a complete bipartite graph where both parts have $n$ vertices) is homogeneous.
Infinite Homogeneous Graphs
The study of infinite homogeneous graphs is closely tied to Fraïssé's theory, a branch of model theory. An infinite homogeneous graph can often be constructed as the Fraïssé limit of a suitable class of finite graphs.
- The Rado Graph (or Random Graph $R$): This is the most famous example of an infinite homogeneous graph. It is unique (up to isomorphism) among countable graphs with the property that for any two finite disjoint sets of vertices $A$ and $B$, there exists a vertex $v$ that is adjacent to all vertices in $A$ and to no vertices in $B$. The Rado graph is also universal (it contains every finite or countable graph as an induced subgraph) and homogeneous.
- Other examples include the infinite complete graph $K_{\aleph_0}$ and the infinite empty graph $\bar{K}_{\aleph_0}$.
Related Concepts
- Automorphism: A permutation of the vertices of a graph that preserves adjacency. Homogeneous graphs possess particularly rich automorphism groups.
- Fraïssé Limit: A central concept in model theory, referring to a unique (up to isomorphism) countable homogeneous structure that serves as a "limit" for a given class of finite structures (e.g., finite graphs).
- Ultrahomogeneous Graph: This term is sometimes used interchangeably with "homogeneous graph." In some contexts, it can refer to structures where isomorphisms between finite substructures (not necessarily induced) can be extended. For graphs, where "subgraph" often implies induced subgraph in this context, the terms largely overlap.
- Vertex-Transitive Graph: A graph where every vertex "looks the same" in the sense that for any two vertices $u$ and $v$, there exists an automorphism mapping $u$ to $v$. All homogeneous graphs are vertex-transitive.
- Edge-Transitive Graph: A graph where every edge "looks the same" in the sense that for any two edges $e_1$ and $e_2$, there exists an automorphism mapping $e_1$ to $e_2$. All homogeneous graphs with at least one edge are also edge-transitive.
Applications
Homogeneous graphs are fundamental objects in:
- Model Theory: They play a crucial role in the study of countable structures and Fraïssé theory, providing canonical examples of highly symmetric structures.
- Structural Graph Theory: They offer extreme examples of symmetry, which helps in understanding the boundaries and possibilities of graph structures.
- Universal Algebra and Logic: Their properties often lead to insights in related fields of mathematics where highly symmetric or "generic" objects are investigated.