| Popis: |
A well-known result from the 1960 paper of Erdős and Renyi (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. |
Full Text from ScienceDirect