First-Order Definability of Trees and Sparse Random Graphs

DOI10.1017/S0963548306008376zbMath1119.03025arXivmath/0506288WikidataQ57401489 ScholiaQ57401489MaRDI QIDQ3438138

Oleg Verbitsky, Tomasz Łuczak, Oleg Pikhurko, Tom Bohman, Clifford D. Smyth, J. H. Spencer, Alan M. Frieze

Publication date: 15 May 2007

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0506288

zbMATH Keywords

random graphrandom treedescriptive complexitygiant component

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Model theory of finite structures (03C13) Interpolation, preservation, definability (03C40) Descriptive complexity and finite models (68Q19)

Related Items

Decomposable graphs and definitions with no quantifier alternation, Characterization of product anti-magic graphs of large order