Existential closure of graphs

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) [English] 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. (Original Version)

Abstract

We study the n-existential closure property of graphs which was first considered by Erdös and Rényi in 1963. A graph G is said to be n-existentially closed, abbreviated as n-e.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 n-e.c. the existential closure number of G, and we denote it by Ξ(G). Despite the fact that there are many graphs that are n-e.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 n-e.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 n-e.c. graphs. In this thesis we focus on two subjects: obtaining 3-existentially closed graphs using graph operations and investigating the n-e.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 n-e.c. graphs from given n-e.c. graphs, and showed that the symmetric difference of two 3-e.c. graphs is a 3-e.c. graph. In 2008 another 3-e.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 3-e.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 3-e.c. given that H itself is a 3-e.c. graph. We then use this operation to construct new classes of 3-e.c. graphs of the form G ⃟ H where G is not necessarily 3-e.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 3-e.c. can have as few as four vertices, which represents an improvement in comparison to when G is required to be 3-e.c. -- As part of an effort to find n-e.c. graphs, Forbes et al. first considered the block intersection graphs of Steiner triple systems, and later McKay and Pike studied the n-e.c. property of graphs arising from BIBDs. We extend the study of the n-existential 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 n-e.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 n-existential closure property of the block intersection graphs of such infinite designs. -- If k is infinite and (t,λ) ≠ (1,1), then for each non-negative 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 n-e.c. for each non-negative 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.

Actions (login required)

View Item