Abstract: In 1963, Erdos and Renyi gave a non-explicit, randomized construction of graphs with an adjacency property. For a positive integer $n$, a graph is $n$-existentially closed (or n-e.c.) if for all disjoint sets of vertices $A$ and $B$ with $|A \cup B| = n$, there is a vertex $z$ not in $A \cup B$ joined to each vertex of $A$ and no vertex of $B$. Until recently, only a few explicit families of n-e.c. graphs were known, such as Paley graphs. Erdos posed a conjecture on the asymptotic minimum order of n-e.c. graphs which is only now receiving attention. The exact minimum orders of n-e.c. graphs are only known for $n = 1$ and $n = 2$.
Using a computer search, a new example of a 3-e.c. graph of order 30 is presented. Previously, no known 3-e.c. graph was known to exist of that order. We give a new randomized construction of vertex-transitive $n$-e.c. graphs, exploiting Cayley graphs.