First-Order Definability of Trees and Sparse Random Graphs

DOI10.1017/S0963548306008376MaRDI QIDQ3438138zbMATH OpenWikidataFDO

Authors Tom Bohman, Tomasz Łuczak, Oleg Pikhurko, Oleg Verbitsky, Alan Frieze, Clifford Smyth, Joel Spencer

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

descriptive complexitygiant componentrandom graphrandom tree

Mathematics Subject Classification ID

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

Abstract: Let D(G) be the smallest quantifier depth of a first order formula which is true for a graph G but false for any other non-isomorphic graph. This can be viewed as a measure for the first order descriptive complexity of G. We will show that almost surely D(G)=Theta(ln n/lnln n), where G is a random tree of order n or the giant component of a random graph G(n,c/n) with constant c>1. These results rely on computing the maximum of D(T) for a tree T of order n and maximum degree l, so we study this problem as well.

Recommendations

• Definability in first-order theories of graph orderings
• Definability in first order theories of graph orderings
• The first order definability of graphs: Upper bounds for quantifier depth
• First-order properties of bounded quantifier depth of very sparse random graphs
• On computing the measures of first-order definable sets of trees
• First-order and monadic properties of highly sparse random graphs
• Probabilities of first-order sentences on sparse random relational structures: An application to definability on random CNF formulas
• A first-order axiomatization of the theory of finite trees
• Infinitary logics and very sparse random graphs
• Zero-one laws for \(k\)-variable first-order logic of sparse random graphs

Cited in

(11)

• Decomposable graphs and definitions with no quantifier alternation
• Characterization of product anti-magic graphs of large order
• The complexity of random ordered structures
• The first order definability of graphs with separators via the Ehrenfeucht game
• Logical complexity of graphs: a survey
• Decomposable graphs and definitions with no quantifier alternation
• scientific article; zbMATH DE number 4051033 (Why is no real title available?)
• First-order properties of trees, star-free expressions, and aperiodicity
• How complex are random graphs in first order logic?
• Combinatorial games on Galton-Watson trees involving several-generation-jump moves
• Canonical labeling of sparse random graphs

This page was built for publication: First-Order Definability of Trees and Sparse Random Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3438138)