ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

1. Logic

1991 MS Classification: 3,5 Shi, Niandong, East Stroudsburg University of Pennsylvania, USA; Cherlin, Gregory, Rutgers University, USA: Shelah, Saharon, Hebrew University, Israel Universal graph problem and model theory A universal graph of a class of graphs is the one in which all other graphs in the class are embeddable. The following problem has been investigated for many years by many mathematicians: give a finite set C of finite connected graphs, does the class G_{C} of countable graphs omitting C contain a universal element? We apply model theoretic methods to the problem and show that to a large extent the question reduces to one of local finiteness of an associated “algebraic closure“ operator. Applications to new examples of universal graphs with forbidden subgraphs and simplified treatments of some previously known cases will be presented.