Countably Universal H-free Graphs
Rehana Patel, Department of Mathematics an Computer Science, St. John’s College of Liberal Arts and Sciences
Abstract
A graph is a mathematical object that consists of a set of points, called vertices, some of which may be connected by lines called edges. Let H be a fixed finite graph. A graph G is said to be H-free if it does not contain a copy of H as a subgraph. Now, a class of countable graphs is said to have a countably universal member if there is a graph U in that class into which every other member of the class can be embedded. The general question is whether such a countably universal graph U exists for the class of countable H-free graphs. In a 1999 paper, Cherlin, Shelah and Shi provided a model-theoretic condition that guarantees the existence of a countably universal H-free graph, and used it to show the existence of countably universal (K_n + K_3)-free graphs for any n>2, K_n + K_3 being a particular graph on n+2 vertices. We will give a complete description of this infinite family of countably universal (K_n +K_3)-free graphs and explain some of their distinctive graph-theoretic and model-theoretic properties.