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

DOI10.1016/J.DAM.2006.03.002MaRDI QIDQ860411zbMATH OpenOpenAlexFDO

Authors Oleg Pikhurko, Helmut Veith, Oleg Verbitsky

Publication date 9 January 2007

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

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

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)

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'.

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

Cites work

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

Cited in

(14)

• Segment transit function of the induced path function of graphs and its first-order definability
• 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
• Two consequences of the dichotomy theorem on first order definability of graphs.
• First-Order Definability of Trees and Sparse Random 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

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)