The strange logic of random graphs
From MaRDI portal
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.
Recommendations
Cited in
(81)- Thresholds for families of multisets, with an application to graph pebbling
- Existential monadic second order logic on random rooted trees
- First order sentences about random graphs: small number of alternations
- Logical laws for existential monadic second-order sentences with infinite first-order parts
- Existential monadic second order logic of undirected graphs: the Le Bars conjecture is false
- A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences
- Logical limit laws for minor-closed classes of graphs
- The first order convergence law fails for random perfect graphs
- Upper tails for subgraph counts in random graphs
- On the lengths of symmetry breaking-preserving games on graphs
- First-order complexity of subgraph isomorphism via Kneser graphs
- \(\gamma\)-variable first-order logic of uniform attachment random graphs
- On the 4-spectrum of first-order properties of random graphs
- Strictly balanced uniform hypergraphs and generalizations of zero-one law
- \( \gamma \)-variable first-order logic of preferential attachment random graphs
- Pseudofiniteness in Hrushovski constructions
- On existentially complete triangle-free graphs
- Quantifier alternation in first-order formulas with infinite spectra
- Conditional probability logic, lifted Bayesian networks, and almost sure quantifier elimination
- On the convergence of probabilities of first-order sentences for recursive random graph models
- MSO 0-1 law for recursive random trees
- Modular statistics for subgraph counts in sparse random graphs
- The component graph of the uniform spanning forest: transitions in dimensions \(9,10,11,\ldots\)
- Zero-one laws for \(k\)-variable first-order logic of sparse random graphs
- Infinite spectra of first-order properties for random hypergraphs
- Strict superstablity and decidability of certain generic graphs
- On the zero-one 4-law for the Erdős-Rényi random graphs
- Spectra of short monadic sentences about sparse random graphs
- Succinct definitions in the first order theory of graphs
- Monadic second-order properties of very sparse random graphs
- Disproof of the zero-one law for existential monadic properties of a sparse binomial random graph
- Decomposable graphs and definitions with no quantifier alternation
- The complexity of random ordered structures
- A simpler axiomatization of the Shelah-Spencer almost sure theories
- Simple structures axiomatized by almost sure theories
- The first order definability of graphs with separators via the Ehrenfeucht game
- Limit points of spectra for first-order properties of random hypergraphs
- Bounded quantifier depth spectra for random graphs
- Vapnik-Chervonenkis density in some theories without the independence property. I
- A limit law of almost l-partite graphs
- On rational limits of Shelah-Spencer graphs
- On failure of 0-1 laws
- The first-order contiguity of sparse random graphs with prescribed degrees
- Homomorphism-homogeneous graphs
- On the first-order complexity of induced subgraph isomorphism
- Universal zero-one k-law
- Complexity and randomness in the Heisenberg groups (and beyond)
- On the zero-one k-law extensions
- Inevitable randomness in discrete mathematics
- On generic structures with a strong amalgamation property
- Random Graphs, Retractions and Clique Graphs
- Zero-one \(k\)-law
- Short monadic second order sentences about sparse random graphs
- Friendly frogs, stable marriage, and the magic of invariance
- First order probabilities for Galton-Watson trees
- First-order properties of bounded quantifier depth of very sparse random graphs
- How complex are random graphs in first order logic?
- Revolutionaries and Spies on Random Graphs
- Preferential attachment processes approaching the Rado multigraph
- EMSO(FO^2) 0-1 Law Fails for All Dense Random Graphs
- Logical laws for short existential monadic second-order sentences about graphs
- First-order zero-one law for the uniform model of the random graph
- Generating infinite random graphs
- Descriptive complexity of finite structures: Saving the quantifier rank
- Filtration games and potentially projective modules
- Evolving Shelah‐Spencer graphs
- Counting extensions revisited
- Logical limit laws for layered permutations and related structures
- Preface to the special issue of Permutation Patterns 2021 (PP2021)
- Spectrum of FO logic with quantifier depth 4 is finite
- Chemically inspired Erdős-Rényi hypergraphs
- Interview with Joel Spencer
- Logical limit laws for Mallows random permutations
- Logical convergence laws via stochastic approximation and Markov processes
- First order distinguishability of sparse random graphs
- First order complexity of finite random structures
- Zero-one laws for events with positional symmetries
- First-order convergence for 321-avoiding permutations
- Analyticity for rapidly determined properties of Poisson Galton-Watson trees
- The first order definability of graphs: Upper bounds for quantifier depth
- Geography of local configurations
This page was built for publication: The strange logic of random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5939775)
