How complex are random graphs in first order logic?
From MaRDI portal
Publication:4667860
DOI10.1002/RSA.20049zbMath1060.05085arXivmath/0401247OpenAlexW2952496718MaRDI QIDQ4667860
Oleg Pikhurko, Jeong Han Kim, Oleg Verbitsky, J. H. Spencer
Publication date: 21 April 2005
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0401247
Related Items (18)
Succinct definitions in the first order theory of graphs ⋮ The first order definability of graphs: Upper bounds for quantifier depth ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity ⋮ Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas ⋮ New bounds and constructions for neighbor-locating colorings of graphs ⋮ Separating codes and traffic monitoring ⋮ Decomposable graphs and definitions with no quantifier alternation ⋮ On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds. ⋮ Unnamed Item ⋮ Characterization of product anti-magic graphs of large order ⋮ The complexity of random ordered structures ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs ⋮ Separating Codes and Traffic Monitoring ⋮ On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs ⋮ The first order definability of graphs with separators via the Ehrenfeucht game ⋮ Locating-dominating sets and identifying codes in graphs of girth at least 5
Cites Work
This page was built for publication: How complex are random graphs in first order logic?
