EXISTENTIALLY CLOSED PROPERTY IN DIRECTED INFINITE GRAPHS
MetadataShow full item record
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 inﬁnite 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 inﬁnite random directed graphs. We ﬁrst give the deﬁnition of two types of directed graphs used in our thesis. We deﬁne 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 deﬁnition of δ-g.e.c. We recall the inﬁnite random one-dimensional random geometric graph and summarize its properties. We then extend our study to directed g.e.c. graphs. We ﬁrst deﬁne δ-d.g.e.c. graphs of types I and II. We deﬁne directed random graphs with probabilities for an edge of either directions between two vertices. We ﬁnd that with probability 1, directed random graphs are of directed e.c. of type I or type II. Then we deﬁne the directed LARG graphs, the DLARG model. We show that DLARG graphs are linked to directed random graphs of the same threshold. The ﬁnal topic focuses on directed geometric e.c. graphs with asymmetric thresholds of inﬂuence. 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.