Homomorphisms of Edge-Colored Graphs and Coxeter Groups

Noga Alon, T. H. MarshallJournal of Algebraic Combinatorics 1998 · DOI

Introduction

This research establishes a significant link between discrete graph theory and geometric group theory. By investigating the properties of edge-colored planar graphs, the authors derive new bounds for the index of torsion-free subgroups in 3D hyperbolic reflection groups. This work bridges the gap between the combinatorial structure of graphs and the algebraic properties of reflection groups.

Problem Statement

The paper addresses two core questions across different mathematical domains:

  1. Graph Theory: Given a class of graphs (such as planar graphs) where edges are colored with $n$ colors, does there exist a single finite "universal" graph $G_n$ such that every graph in that class can be mapped into $G_n$ via a color-preserving homomorphism?
  2. Group Theory: For Coxeter groups—specifically hyperbolic reflection groups—what is the bound on the index of the smallest torsion-free subgroup? While Selberg’s Lemma guarantees the existence of such subgroups, finding an explicit bound that depends only on rotation orders, rather than the complexity (number of faces) of the fundamental polyhedron, is a significant challenge.

Methodology

The authors employ a sophisticated blend of combinatorial construction and algebraic mapping:

  • Acyclic Colorings: The proof leverages the concept of the acyclic chromatic number—the minimum number of colors needed to color vertices such that no cycle is bicolored. A key starting point is Borodin's theorem, which states that all planar graphs have an acyclic chromatic number of at most 5.
  • Target Graph Construction: The authors construct a specific finite edge-colored graph $G_n$ using $k$-tuples. They prove that any graph with a bounded acyclic chromatic number can be homomorphically mapped into this target. For planar graphs, this results in a universal target graph of finite size.
  • Graph-to-Group Correspondence: A formal relationship is established between homomorphisms of "Coxeter graphs" (which describe the generators and relations of a group) and homomorphisms of the groups themselves into permutation groups. This allows graph-theoretic results to be imported into group theory.
  • Geometric Application: By treating the dual of the edge skeleton of a Coxeter polyhedron as a planar graph, the authors apply their graph-theoretic bounds to the problem of finding torsion-free subgroups in 3D hyperbolic space.

Key Insights

  • The Utility of Acyclic Coloring: The central innovation is the realization that acyclic vertex coloring provides the necessary structure to decompose a complex graph into a collection of forests (trees). Because forests are easily mapped homomorphically into edge-colored complete bipartite graphs, these individual mappings can be "glued" together to handle the entire graph.
  • Planarity as a Constraint: The fundamental polyhedra of 3D reflection groups have skeletons that are planar. This allows the authors to utilize powerful results like the four-color theorem and the five-color acyclic theorem to provide universal bounds that would not necessarily exist for higher-dimensional groups where planarity is lost.
  • Universal Targets: The existence of a finite $G_n$ for all planar graphs is a profound result. It implies that regardless of the number of vertices in a planar graph, its "color structure" is fundamentally constrained enough to fit into a fixed-size template.

Key Results

  • Universal Planar Bounds: For any $n$ colors, there exists a finite graph $G_n$ such that every $n$-edge-colored planar graph maps into it. The minimum number of vertices $\lambda_n$ for such a graph is bounded by: $$n^3 + 3 \le \lambda_n \le 5n^4$$
  • General Acyclic Bounds: For any family of graphs with acyclic chromatic number $k$, the size of the target graph is at most $kn^{k-1}$.
  • Torsion-Free Subgroups: For a 3D hyperbolic reflection group with rotation orders from a set $M$, the index of its smallest torsion-free subgroup is bounded by a constant that depends only on $M$. This provides a qualitative improvement over previous bounds that depended on the number of faces of the underlying polyhedron.

Discussion and Future Work

While the paper provides groundbreaking bounds, several avenues for future research remain. The authors note that their derived bounds (such as $5n^4$) are likely not tight; for instance, in the case of $n=1$, the bound is known to be 4 (from the four-color theorem), yet the general formula yields a much higher value.

Furthermore, the results regarding reflection groups are specifically tied to 3D hyperbolic space because they rely on the planarity of the polyhedron's skeleton. Extending these findings to higher dimensions would require different combinatorial tools, as the underlying graphs would no longer be planar. Finally, while the paper proves the existence of these bounds, the computational complexity of finding specific homomorphisms remains an open question.

Summary updated

BibTeX
@article{alon1998homomorphisms,
  author = {Noga Alon and T. H. Marshall},
  title = {{Homomorphisms of Edge-Colored Graphs and Coxeter Groups}},
  journal = {Journal of Algebraic Combinatorics},
  year = {1998},
  doi = {10.1023/a:1008647514949},
}
Figure