The strange logic of random graphs
From MaRDI portal
Publication:5939775
zbMath0976.05001MaRDI QIDQ5939775
Publication date: 30 July 2001
Published in: Algorithms and Combinatorics (Search for Journal in Brave)
Random graphs (graph-theoretic aspects) (05C80) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Classical first-order logic (03B10)
Related Items (69)
Spectra of short monadic sentences about sparse random graphs ⋮ Bounded quantifier depth spectra for random graphs ⋮ Strictly balanced uniform hypergraphs and generalizations of zero-one law ⋮ Existential monadic second order logic on random rooted trees ⋮ \( \gamma \)-variable first-order logic of preferential attachment random graphs ⋮ Upper tails for subgraph counts in random graphs ⋮ On rational limits of Shelah–Spencer graphs ⋮ Succinct definitions in the first order theory of graphs ⋮ Preferential attachment processes approaching the Rado multigraph ⋮ On the lengths of symmetry breaking-preserving games on graphs ⋮ Universal zero-one \(k\)-law ⋮ On the zero-one \(k\)-law extensions ⋮ The first order definability of graphs: Upper bounds for quantifier depth ⋮ Short Monadic Second Order Sentences about Sparse Random Graphs ⋮ Limit points of spectra for first-order properties of random hypergraphs ⋮ Monadic second-order properties of very sparse random graphs ⋮ Friendly Frogs, Stable Marriage, and the Magic of Invariance ⋮ Pseudofiniteness in Hrushovski constructions ⋮ On existentially complete triangle-free graphs ⋮ On Failure of 0-1 Laws ⋮ EMSO(FO$^2$) 0-1 Law Fails for All Dense Random Graphs ⋮ The First-Order Contiguity of Sparse Random Graphs with Prescribed Degrees ⋮ Filtration games and potentially projective modules ⋮ Evolving Shelah‐Spencer graphs ⋮ Counting extensions revisited ⋮ Random Graphs, Retractions and Clique Graphs ⋮ Quantifier alternation in first-order formulas with infinite spectra ⋮ Disproof of the zero-one law for existential monadic properties of a sparse binomial random graph ⋮ First order sentences about random graphs: small number of alternations ⋮ Zero-one \(k\)-law ⋮ Logical limit laws for layered permutations and related structures ⋮ Preface to the special issue of Permutation Patterns 2021 (PP2021) ⋮ First Order Probabilities for Galton–Watson Trees ⋮ First-order properties of bounded quantifier depth of very sparse random graphs ⋮ Logical laws for short existential monadic second-order sentences about graphs ⋮ Logical laws for existential monadic second-order sentences with infinite first-order parts ⋮ First-order zero-one law for the uniform model of the random graph ⋮ Existential monadic second order logic of undirected graphs: the Le Bars conjecture is false ⋮ Conditional probability logic, lifted Bayesian networks, and almost sure quantifier elimination ⋮ A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences ⋮ Decomposable graphs and definitions with no quantifier alternation ⋮ Logical limit laws for minor-closed classes of graphs ⋮ On the convergence of probabilities of first-order sentences for recursive random graph models ⋮ MSO 0-1 law for recursive random trees ⋮ Descriptive complexity of finite structures: Saving the quantifier rank ⋮ Unnamed Item ⋮ The complexity of random ordered structures ⋮ A simpler axiomatization of the Shelah-Spencer almost sure theories ⋮ Modular statistics for subgraph counts in sparse random graphs ⋮ How complex are random graphs in first order logic? ⋮ The component graph of the uniform spanning forest: transitions in dimensions \(9,10,11,\ldots\) ⋮ Geography of local configurations ⋮ Vapnik-Chervonenkis density in some theories without the independence property, I ⋮ The first order convergence law fails for random perfect graphs ⋮ First-order complexity of subgraph isomorphism via Kneser graphs ⋮ Homomorphism-homogeneous graphs ⋮ Complexity and randomness in the Heisenberg groups (and beyond) ⋮ Zero-one laws for \(k\)-variable first-order logic of sparse random graphs ⋮ Generating Infinite Random Graphs ⋮ Infinite spectra of first-order properties for random hypergraphs ⋮ On generic structures with a strong amalgamation property ⋮ Analyticity for rapidly determined properties of Poisson Galton-Watson trees ⋮ Strict superstablity and decidability of certain generic graphs ⋮ The first order definability of graphs with separators via the Ehrenfeucht game ⋮ A Limit Law of Almost l-partite Graphs ⋮ \(\gamma\)-variable first-order logic of uniform attachment random graphs ⋮ On the zero-one 4-law for the Erdős-Rényi random graphs ⋮ Simple structures axiomatized by almost sure theories ⋮ On the 4-spectrum of first-order properties of random graphs
This page was built for publication: The strange logic of random graphs
