Sanaei, Asiyeh (2011) Existential closure of graphs. Doctoral (PhD) thesis, Memorial University of Newfoundland.
[English]
PDF (Migrated (PDF/A Conversion) from original format: (application/pdf))
 Accepted Version
Available under License  The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (21MB)


Abstract
We study the nexistential closure property of graphs which was first considered by Erdös and Rényi in 1963. A graph G is said to be nexistentially closed, abbreviated as ne.c., if for each pair (A,B) of disjoint subsets of V(G) with A + B ≤ n there exists a vertex in V(G) \ (A ∪ B) which is adjacent to each vertex in A and to no vertex in B. Accordingly, we call the largest integer n (if it exists) for which a given graph G is ne.c. the existential closure number of G, and we denote it by Ξ(G). Despite the fact that there are many graphs that are ne.c., only a handful of explicit families of graphs with the property have been found.  Recently the property has become a subject of renewed interest and several techniques have appeared in the literature to construct ne.c. graphs. These techniques benefit from design theory, finite geometry, probability theory, matrix theory, as well as computer search over classes of graphs that are likely to contain ne.c. graphs. In this thesis we focus on two subjects: obtaining 3existentially closed graphs using graph operations and investigating the ne.c. property of the block intersection graphs of infinite designs.  In 2001 Bonato and Cameron examined several graph operations to see which operations could be used to construct ne.c. graphs from given ne.c. graphs, and showed that the symmetric difference of two 3e.c. graphs is a 3e.c. graph. In 2008 another 3e.c. preserving graph operation was introduced by Baker et al. We have taken a different approach to the construction of Baker et al. that enables us to relax the requirement that the two graphs considered be both 3e.c. We formulate the construction as the modular graph product denoted by ⃟ and we determine necessary and sufficient conditions for the graph G ⃟ H to be 3e.c. given that H itself is a 3e.c. graph. We then use this operation to construct new classes of 3e.c. graphs of the form G ⃟ H where G is not necessarily 3e.c. The classes that we consider are those for which G is either a complete multipartite graph or a strongly regular graph. The graphs G for which we show that G ⃟ H is 3e.c. can have as few as four vertices, which represents an improvement in comparison to when G is required to be 3e.c.  As part of an effort to find ne.c. graphs, Forbes et al. first considered the block intersection graphs of Steiner triple systems, and later McKay and Pike studied the ne.c. property of graphs arising from BIBDs. We extend the study of the nexistential closure property of block intersection graphs of designs to infinite designs. An infinite t(v,k,λ) design D is a design with an infinitely many points while k, t and λ can be either finite or infinite. The block intersection graph of a design D denoted by GD is a graph with the block set of D as the vertex set and two vertices of GD are adjacent if their corresponding blocks share a point. These graphs have infinite vertex sets and have motivated us to investigate whether we can use the construction to find another construction of the Rado graph (the countably infinite random graph that is known to be ne.c. for all n).  We suppose that t and λ are finite and solve the problem in two cases: when k is finite and when k is infinite. If k is finite, then for such an infinite design D we show that Ξ(GD) = min [special characters omitted] if λ = 1 and 2 ≤ t ≤ k, and 2 ≤ Ξ(GD) ≤ min [special characters omitted] if λ ≥ 2 and 2 ≤ t ≤ k  1. Our results show that block intersection graphs of such infinite designs are different from countably infinite random graphs as n is bounded for the nexistential closure property of the block intersection graphs of such infinite designs.  If k is infinite and (t,λ) ≠ (1,1), then for each nonnegative integer n, we show that there exists a t(v,v,λ) design D such that Ξ(GD) = n. We also show that there exists a t(v,v,λ) design D' such that GD' is ne.c. for each nonnegative integer n. This implies the existence of t(ℵ₀,ℵ₀,λ) designs whose block intersection graphs are isomorphic to the Rado graph. However, if k < v, then Ξ(GD) ≤ min{ℓ,t} where ℓ is the smallest cardinal such that there are ℓ blocks of D whose union is a superset of another block of D.
Item Type:  Thesis (Doctoral (PhD)) 

URI:  http://research.library.mun.ca/id/eprint/6176 
Item ID:  6176 
Additional Information:  Includes bibliographical references (leaves 8388). 
Department(s):  Science, Faculty of > Mathematics and Statistics 
Date:  2011 
Date Type:  Submission 
Library of Congress Subject Heading:  Model theory; Existentially closed groups; Graph theory 
Actions (login required)
View Item 