The first order theory of G(n, c∕n). (May 2019) - Podder, Moumanti
Abstract: A well-known result from the 1960 paper of Erdős and Rényi (1960)[2] tells us that the almost sure theory for first order language on the random graph sequence G ( n, c n − 1 ) is not complete. Our paper proposes and proves what the complete set of completions of the almost sure theory for G ( n, c n − 1 ) should be. The almost sure theory 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 ∈ 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 (which indicates that the property described in sentence A is satisfied by the graph, and for every sentence B in the theory T, the property described by B is also satisfied by the graph), we can fully describe the first order sentences of quantifier depth ≤ 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.