First order theory on $G(n,c{n}^{-1})$

A well-known result of Shelah and Spencer tells us that the almost sure theory for first order language on the random graph sequence $\left{G(n, cn^{-1})\right}$ is not complete. This paper proposes and proves what the complete set of completions of the almost sure theory for $\left{G(n, c n^{-1})\right}$shouldbe\mathrm{.}Thealmostsuretheory$T$ consists of two sentence groups: the first states that all the components are trees or unicyclic components, and the second states that, given any $k\in \mathbb{N}$ and any finite tree $t$, there are at least $k$ components isomorphic to $t$. We define a $k$-completion of $T$ to be a first order property $A$, such that if $T+A$ holds for a graph, we can fully describe the first order sentences of quantifier depth $\le k$ that hold for that graph. We show that a $k$-completion $A$ specifies the numbers, up to “cutoff” $k$, of the (finitely many) unicyclic component types of given parameters (that only depend on $k$) that the graph contains. A complete set of $k$-completions is then the finite collection of all possible $k$-completions.