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)
05C80: Random graphs (graph-theoretic aspects)
05-02: Research exposition (monographs, survey articles) pertaining to combinatorics
03B10: Classical first-order logic
Related Items
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?, 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, Simple structures axiomatized by almost sure theories, Bounded quantifier depth spectra for random graphs, Universal zero-one \(k\)-law, On the zero-one \(k\)-law extensions, Zero-one \(k\)-law, 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, 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, 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, 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, The first order definability of graphs with separators via the Ehrenfeucht game, Limit points of spectra for first-order properties of random hypergraphs, 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, Unnamed Item, Homomorphism-homogeneous graphs, On generic structures with a strong amalgamation property, Random Graphs, Retractions and Clique Graphs
