What is it about?
Whether a graph or a network contains a pattern F as a subgraph can be described by a sentence of first-order logic. A direct description has quantifier depth v(F), where v(F) is the number of vertices in F. It is non-obvious whether or not this can be done more succinctly. We show that a first-order description of quantifier depth at most (2/3)v(F)+1 is always possible, and that this bound cannot be much better in general.
Photo by Alina Grubnyak on Unsplash
Why is it important?
The quantifier depth is an important measure of descriptive complexity of a graph property.
Read the Original
This page is a summary of: Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism, ACM Transactions on Computational Logic, April 2019, ACM (Association for Computing Machinery), DOI: 10.1145/3303881.
You can read the full text:
The following have contributed to this page