Logical complexity of graphs: a survey
By Oleg Pikhurko, Oleg Verbitsky. 2010
31 citations recorded by the source corpus.
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).
Subfields: Graph Learning
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Graph Learning
Citations in the corpus
- The Weisfeiler-Lehman Method and Graph Isomorphism Testing (2011, methodology): “The history and details of the generalised k-dimensional WeisfeilerLehman method (which we will term the k-dim WL as in [10] and [28]) and other related methods can be found in [33, 34, 16], among others.”
- Detecting Similar Programs via The Weisfeiler-Leman Graph Kernel (2016, background): “It is well known that the exact information captured by i iterations of naı̈ve vertex classification can be precisely expressed in a certain type of logic (see [19]).”
- Learning Games from Videos Guided by Descriptive Complexity (2012, background): “These include planar graphs, classes of graphs excluding a minor, and several other classes, see (Pikhurko and Verbitsky 2010) for a survey.”