Logical complexity of graphs: a survey

MaRDI QIDQ3118383zbMATH OpenFDO

Authors Oleg Pikhurko, Oleg Verbitsky

Publication date 2 March 2012

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

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Random graphs (graph-theoretic aspects) (05C80) Descriptive complexity and finite models (68Q19)

Abstract: We discuss the definability of finite graphs in first-order logic with two relation symbols for adjacency and equality of vertices. The logical depth $D(G)$ of a graph $G$ is equal to the minimum quantifier depth of a sentence defining $G$ up to isomorphism. The logical width $W(G)$ is the minimum number of variables occurring in such a sentence. The logical length $L(G)$ is the length of a shortest defining sentence. We survey known estimates for these graph parameters and discuss their relations to other topics (such as the efficiency of the Weisfeiler-Lehman algorithm in isomorphism testing, the evolution of a random graph, quantitative characteristics of the zero-one law, or the contribution of Frank Ramsey to the research on Hilbert's Entscheidungsproblem). Also, we trace the behavior of the descriptive complexity of a graph as the logic becomes more restrictive (for example, only definitions with a bounded number of variables or quantifier alternations are allowed) or more expressible (after powering with counting quantifiers).

Recommendations

• On the definability of properties of finite graphs
• Logical complexity of induced subgraph isomorphism for certain families of graphs
• First-Order Definability of Trees and Sparse Random Graphs
• The Complexity of Defining a Relation on a Finite Graph
• How complex are random graphs in first order logic?

Cited in

(16)

• Defining long words succinctly in FO and MSO
• Decomposable graphs and definitions with no quantifier alternation
• Bounds for the quantifier depth in finite-variable logics: alternation hierarchy
• On the first-order complexity of induced subgraph isomorphism
• Decomposable graphs and definitions with no quantifier alternation
• The Complexity of Defining a Relation on a Finite Graph
• On the WL-dimension of circulant graphs of prime power order
• Combinatorial refinement on circulant graphs
• Relating description complexity to entropy
• On the Weihrauch degree of the additive Ramsey theorem
• Hilbert's tenth problem for term algebras with a substitution operator
• Complemented subsets and Boolean-valued, partial functions
• Defining long words succinctly in FO and MSO
• Finite variable counting logics with restricted requantification
• On the definability of properties of finite graphs
• Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree

This page was built for publication: Logical complexity of graphs: a survey

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