The Free Product of Graphs, a Folly of Infinity
Presented by Prof. Wilfried IMRICH
Type: Oral presentation
Track: Keynote lecture
This talk begins with an introduction to infinite graphs, describes main differences to finite graphs, and continues with the free product. The free product G*H of two-connected graphs G and H is a vertex transitive, infinite graph whose blocks are isomorphic to G or H. This product is commutative and associative, but does not have a unit unless one restricts attention to vertex transitive graphs. Furthermore, it is related to the free product of groups. In fact, the free product of groups can be defined via the free product of Cayley graphs. Then we outline how the equivalence of the axiom of choice to the existence of spanning trees in infinite graphs helps to shorten proofs of theorems of Kurosh and Grushko about subgroups of free products of groups. The free product of graphs also allows a structure theorem for vertex transitive, infinite graphs with cut-points. This is useful in the investigation of infinite, vertex transitive median graphs with finite blocks, which is described next. Then the talk takes a short detour to vertex transitive median graphs with two ends and to the characterization of vertex transitive infinite median graphs of polynomial growth as Cartesian products. Finally, the weak Cartesian product of graphs is introduced. Just as the free product, the weak Cartesian product allows the construction of vertex transitive graphs from intransitive constituents. At a first glance these two constructions are unrelated. Nonetheless, they are connected via Graham and Winkler's canonical isometric embedding of graphs into Cartesian products. We explain how how the canonical isometric embedding of the free product G*H of graphs that are not vertex transitive gives rise to a homomorphism of G*H onto a vertex transitive weak Cartesian product of infinitely many copies of G and H.