From Homomorphisms to Graph Amalgamations: An Expanded Survey

 


From Homomorphisms to Graph Amalgamations: An Expanded Survey

This article traces our journey through algebraic and topological maps, the versatile notion of amalgams, and their powerful graph‐theoretic incarnation. We begin with structure‐preserving homomorphisms and topological arcwise connectedness, introduce the classical and dental senses of amalgams, then delve into graph amalgamation, contrast it with edge contraction, and conclude with a hands‐on cluster‐contraction example.

1. Algebraic Homomorphism

A homomorphism is a map between two algebraic structures that preserves the defining operations. Formally, for algebraic systems ((A,\mu_A)) and ((B,\mu_B)) of the same signature, a function [ f: A \to B ] satisfies [ f\bigl(\mu_A(a_1,\dots,a_k)\bigr) =\mu_B\bigl(f(a_1),\dots,f(a_k)\bigr) ] for all (a_1,\dots,a_k\in A).

Common instances include:

  • Group homomorphism: (f(g\cdot h)=f(g)\cdot f(h)), implying (f(e_A)=e_B) and (f(g^{-1})=f(g)^{-1}).
  • Ring homomorphism: (f(a+b)=f(a)+f(b)) and (f(ab)=f(a)f(b)); units may be required to map to units.
  • Linear map: a homomorphism of vector spaces over a field (K) satisfying additivity and (f(c,x)=c,f(x)) for (c\in K).

2. Topological Arcwise Connectedness

A topological space (X) is arcwise connected (or path‐connected) if for every pair (p,q\in X), there exists a continuous map (an arc) [ \gamma\colon [0,1]\to X \quad\text{with}\quad \gamma(0)=p,;\gamma(1)=q. ] In Hausdorff spaces, arcwise connectedness coincides with path connectedness.

Example of an arc: in (\mathbb R^2), the straight‐line segment [ \gamma(t)=\bigl((1-t)x_1 + t x_2,,(1-t)y_1 + t y_2\bigr) ] connects points ((x_1,y_1)) and ((x_2,y_2)).

3. Classical and Dental Amalgams

An amalgam generally denotes a blend or composite formed by combining different elements. In chemistry and metallurgy, it refers to an alloy of mercury with another metal, widely used in dental fillings.

While evocative, these senses foreshadow the more abstract notion of merging structures with preservation of constituent relations.

4. Graph Amalgamation

A graph amalgamation collapses vertices of a graph (G) while keeping a one‐to‐one correspondence of edges to produce a smaller graph or pseudograph (H). Concretely:

  • Let (\phi\colon V(G)\twoheadrightarrow V(H)) be a surjection.
  • Let (\psi\colon E(G)\xrightarrow{;\sim;}E(H)) be a bijection.
  • For each edge (e=uv\in E(G)), the edge (\psi(e)) in (H) joins (\phi(u)) and (\phi(v)).
    • If (\phi(u)=\phi(v)), then (\psi(e)) becomes a loop in (H).

Under this “collapse‐and‐rename” procedure, (H) retains the same number of edges but possibly fewer vertices and may admit loops or parallel edges.

4.1 Properties

  • Edge‐colorings and decompositions in (G) carry over to (H) via (\psi).
  • Amalgamation can turn a simple graph into a pseudograph.
  • Useful in studying embeddings: one often amalgamates to reduce genus‐computations.

5. Edge Contraction vs. Graph Amalgamation

AspectEdge ContractionGraph Amalgamation
Vertex mapMerges exactly two vertices per operationCollapses arbitrarily many via (\phi)
Edge correspondenceContracts an edge and “forgets” itMaintains a bijection (\psi) on edges
Typical resultMinor operationQuotient‐style surjection producing pseudograph
RequirementCan introduce parallel edges/loopsPermits loops if (\phi(u)=\phi(v))

A minor arises by selective deletions and repeated edge‐contractions. Equivalently, any minor can be realized as an amalgamation whose vertex‐fibers in (G) are connected subgraphs contracted via spanning trees.

6. Concrete Example: Cluster Contraction on (P_4)

We illustrate by collapsing the path (P_4) into a single edge. Let
[ G = P_4:;1;-;2;-;3;-;4, ] with edges (e_1=(1,2)), (e_2=(2,3)), (e_3=(3,4)).

Define clusters via (\phi):

  • Cluster A: ({1,2})
  • Cluster B: ({3,4})

Choose spanning‐tree edges (e_1) in A and (e_3) in B, then contract them:

   G: 1 — 2 — 3 — 4
       φ
 clusters: {1,2} → A    {3,4} → B
       ↓ contract e₁,e₃
   H: A — B

After contraction, only edge (e_2) remains, now joining vertices (A) and (B). The resulting minor (H) has two vertices and a single edge.

7. Conclusion and Further Directions

This survey has charted the path from algebraic maps and topological paths to the combinatorial ingenuity of graph amalgamation. Key insights include:

  • Homomorphisms and arcs preserve underlying structure—algebraic operations or continuous connectivity.
  • Amalgams, whether metallic or mathematical, fuse elements into a cohesive whole.
  • Graph amalgamation generalizes edge contractions, offering a flexible framework for minors, embeddings, and decompositions.

Beyond these foundations, one may explore forbidden‐minor theorems (e.g., Kuratowski’s planarity criteria), Hamiltonian decompositions via amalgamation, or algorithmic aspects of identifying amalgamation surjections in large networks.

References

  1. Munkres, James R. Topology. 2nd ed. Prentice Hall, 2000.
  2. Rotman, Joseph J. Advanced Modern Algebra. 3rd ed. American Mathematical Society, 2010.
  3. Diestel, Reinhard. Graph Theory. 5th ed. Springer, 2017.
  4. Archdeacon, D., and Richter, R. B. “Graph Amalgamation and Surface Embeddings.” Journal of Graph Theory 15, no. 3 (1991): 245–263.
  5. Robertson, Neil, and Seymour, Paul. “Graph Minors. I–XX.” Journal of Combinatorial Theory, Series B (1983–2004).
  6. Herstein, I. N. Topics in Algebra. Wiley, 1975.

Comments

Post a Comment