The strange logic of random graphs (Q5939775): Difference between revisions

The fundamental result of this book is that no irrational power of \(n\) is a threshold function of any natural property of graphs of order \(n\). The natural properties are not well defined without a proper definition of the logical language in which properties are expressed. The insightful discussion in this book ties together combinatorics and logic in a thorough treatment of zero-one laws for discrete probabilistic models. A powerful tool that is central in the proofs is the Ehrenfeucht game. Sparse random graphs are in focus throughout the book but also other random structures are discussed that can be handled by the techniques developed here.