The first order definability of graphs: Upper bounds for quantifier depth

DOI10.1016/J.DAM.2006.03.002zbMATH Open1109.03023arXivmath/0311041OpenAlexW2000115653MaRDI QIDQ860411FDOQ860411

Authors: Oleg Pikhurko, Helmut Veith, Oleg Verbitsky 

Publication date: 9 January 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We say that a first order formula A distinguishes a graph G from another graph G' if A is true on G and false on G'. Provided G and G' are non-isomorphic, let D(G,G') denote the minimal quantifier rank of a such formula. We prove that, if G and G' have the same order n, then D(G,G')le(n+3)/2, which is tight up to an additive constant of 1. The analogous questions are considered for directed graphs (more generally, for arbitrary structures with maximum relation arity 2) and for k-uniform hypergraphs. Also, we study defining formulas, where we require that A distinguishes G from any other non-isomorphic G'.

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

Recommendations

• Decomposable graphs and definitions with no quantifier alternation
• Decomposable graphs and definitions with no quantifier alternation
• Succinct definitions in the first order theory of graphs
• The first order definability of graphs with separators via the Ehrenfeucht game
• First-order definitions of subgraph isomorphism through the adjacency and order relations

zbMATH Keywords

first-order logicEhrenfeucht gamegraph definability

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19) Interpolation, preservation, definability (03C40)

Cites Work

• The strange logic of random graphs
• Title not available (Why is that?)
• Elements of finite model theory.
• An optimal lower bound on the number of variables for graph identification
• Title not available (Why is that?)
• Succinct definitions in the first order theory of graphs
• Isomorphism testing for embeddable graphs through definability
• How complex are random graphs in first order logic?
• Infinitary logic and inductive definability over finite structures
• Title not available (Why is that?)
• The first order definability of graphs with separators via the Ehrenfeucht game
• Descriptive complexity of finite structures: Saving the quantifier rank

Cited In (14)

• Succinct definitions in the first order theory of graphs
• First-order Definable Retraction Problems for Posets and Reflexive Graphs
• The limits of decidability for first order logic on CPDA graphs
• Decomposable graphs and definitions with no quantifier alternation
• The Weisfeiler-Leman algorithm and recognition of graph properties
• Locality and modular Ehrenfeucht-Fraïssé games
• First-Order Definability of Trees and Sparse Random Graphs
• Two consequences of the dichotomy theorem on first order definability of graphs.
• The Complexity of Defining a Relation on a Finite Graph
• Decomposable graphs and definitions with no quantifier alternation
• The first order definability of graphs with separators via the Ehrenfeucht game
• Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas
• Combinatorial games on Galton-Watson trees involving several-generation-jump moves
• Segment transit function of the induced path function of graphs and its first-order definability

This page was built for publication: The first order definability of graphs: Upper bounds for quantifier depth

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