The first order theory of G(n, c∕n). (May 2019)

• Record Type: Journal Article
• Authors: Podder, Moumanti
• Is Part Of: European journal of combinatorics. Volume 78(2019)
• Page Start: 214
• Page End: 235
• Publication Date: 2019-05
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2019.01.008
• Languages: English
• ISSNs: 0195-6698

Abstract

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.