Cameron D. Hill
A tree decomposition of a graph G is a tree such that each vertex of the tree is a subset of the vertices of G satisfying particular properties. The tree width of a graph comes from its tree decompositions and is a measure of how tree-like the graph is. Many questions which are hard to answer about graphs in general become easy to answer about classes of graphs when their tree width is bounded. It was shown by Seymour and Thomas in 1993 that for a particular game of Cops and Robbers played on graphs, k cops have a winning strategy for the game on the graph G if and only if G has tree width less than k. We generalize tree decomposition, tree width, and the Cops and Robbers game to certain amalgamation classes of finite structures.
Amalgamation classes are classes of finite or countable structures which satisfy specific properties guaranteeing the existence of a “generic model”— a unique countable structure M such that its substructures are precisely the elements of the class and any isomorphism between two finite substructures of M can be extended to an automorphism of M. The class of all finite graphs is an example of a type of amalgamation class called a Fraïssé class. (It is an algebraically trivial Fraïssé class because its generic model, the random (Rado) graph, has no “special” points or finite sets of points.) We show that having a particular kind of independence relation, which we call an abstract free amalgamation relation, on the finite substructures of the generic model of an algebraically trivial Fraïssé class allows a unique decomposition of each finite substructure into components.
Using this decomposition, we are able to define tree decomposition, tree width, and the Cops and Robbers game on elements of an algebraically trivial Fraïssé class with an abstract free amalgamation relation and show that the analogue of Seymour and Thomas's result holds in this setting.
Parnes, Miriam, "A Generalization of Tree Decomposition to Amalgamation Classes of Finite Structures" (2019). Dissertations. 109.
© Copyright is owned by author of this document