EXISTENTIALLY CLOSED PROPERTY IN DIRECTED INFINITE GRAPHS

Abstract

Graph theory abounds with applications inside mathematics itself, and in computer science, and engineering. One direction of research within graph theory is the topic of infinite graphs, which is the focus of this thesis. We review results on existentially closed (or e.c.) graphs and directed graphs. Properties of e.c. graphs, including isomorphism results, universality, and connections with probability are discussed. We develop new results in infinite random directed graphs. We first give the definition of two types of directed graphs used in our thesis. We define directed e.c of two types I and II. We explore the properties of such graphs. We review the LARG model for random geometric graphs, and the definition of δ-g.e.c. We recall the infinite random one-dimensional random geometric graph and summarize its properties. We then extend our study to directed g.e.c. graphs. We first define δ-d.g.e.c. graphs of types I and II. We define directed random graphs with probabilities for an edge of either directions between two vertices. We find that with probability 1, directed random graphs are of directed e.c. of type I or type II. Then we define the directed LARG graphs, the DLARG model. We show that DLARG graphs are linked to directed random graphs of the same threshold. The final topic focuses on directed geometric e.c. graphs with asymmetric thresholds of influence. We characterize when such graphs are isomorphic, and study the ratio of the radii of intervals and connect this with limits of the graph distance.