A Generalization of Tree Decomposition to Amalgamation Classes of Finite Structures

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 treelike 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 nite structures. Amalgamation classes are classes of nite or countable structures which satisfy speci c properties guaranteeing the existence of a generic model a unique countable structureM such that its substructures are precisely the elements of the class and any isomorphism between two nite substructures of M can be extended to an automorphism ofM. The class of all nite 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