# The Descriptive Complexity of Subgraph Isomorphism Without Numerics

Ontology type: schema:Chapter      Open Access: True

### Chapter Info

DATE

2017-05-06

AUTHORS ABSTRACT

Let F be a connected graph with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell$$\end{document} vertices. The existence of a subgraph isomorphic to F can be defined in first-order logic with quantifier depth no better than \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell$$\end{document}, simply because no first-order formula of smaller quantifier depth can distinguish between the complete graphs \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_\ell$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_{\ell -1}$$\end{document}. We show that, for some F, the existence of an F subgraph in sufficiently large connected graphs is definable with quantifier depth \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell -3$$\end{document}. On the other hand, this is never possible with quantifier depth better than \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell /2$$\end{document}. If we, however, consider definitions over connected graphs with sufficiently large treewidth, the quantifier depth can for some F be arbitrarily small comparing to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell$$\end{document} but never smaller than the treewidth of F.We also prove that any first-order definition of the existence of an induced subgraph isomorphic to F requires quantifier depth strictly more than the density of F, even over highly connected graphs. From this bound we derive a succinctness result for existential monadic second-order logic: A usage of just one monadic quantifier sometimes reduces the first-order quantifier depth at a super-recursive rate. More... »

PAGES

308-322

### Book

TITLE

Computer Science – Theory and Applications

ISBN

978-3-319-58746-2
978-3-319-58747-9

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-58747-9_27

DOI

http://dx.doi.org/10.1007/978-3-319-58747-9_27

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1085148876

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Institut f\u00fcr Informatik, Humboldt-Universit\u00e4t zu Berlin, Unter den Linden 6, 10099, Berlin, Germany",
"id": "http://www.grid.ac/institutes/grid.7468.d",
"name": [
"Institut f\u00fcr Informatik, Humboldt-Universit\u00e4t zu Berlin, Unter den Linden 6, 10099, Berlin, Germany"
],
"type": "Organization"
},
"familyName": "Verbitsky",
"givenName": "Oleg",
"id": "sg:person.01046052752.53",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01046052752.53"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Discrete Mathematics, Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow Region, Russia",
"id": "http://www.grid.ac/institutes/grid.18763.3b",
"name": [
"Department of Discrete Mathematics, Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow Region, Russia"
],
"type": "Organization"
},
"familyName": "Zhukovskii",
"givenName": "Maksim",
"id": "sg:person.011152672013.96",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011152672013.96"
],
"type": "Person"
}
],
"datePublished": "2017-05-06",
"datePublishedReg": "2017-05-06",
"description": "Let F be a connected graph with \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\ell$$\\end{document} vertices. The existence of a subgraph isomorphic to F can be defined in first-order logic with quantifier depth no better than \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\ell$$\\end{document}, simply because no first-order formula of smaller quantifier depth can distinguish between the complete graphs \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$K_\\ell$$\\end{document} and \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$K_{\\ell -1}$$\\end{document}. We show that, for some F, the existence of an F subgraph in sufficiently large connected graphs is definable with quantifier depth \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\ell -3$$\\end{document}. On the other hand, this is never possible with quantifier depth better than \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\ell /2$$\\end{document}. If we, however, consider definitions over connected graphs with sufficiently large treewidth, the quantifier depth can for some F be arbitrarily small comparing to \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\ell$$\\end{document} but never smaller than the treewidth of\u00a0F.We also prove that any first-order definition of the existence of an induced subgraph isomorphic to F requires quantifier depth strictly more than the density of F, even over highly connected graphs. From this bound we derive a succinctness result for existential monadic second-order logic: A usage of just one monadic quantifier sometimes reduces the first-order quantifier depth at a super-recursive rate.",
"editor": [
{
"familyName": "Weil",
"givenName": "Pascal",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-319-58747-9_27",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-319-58746-2",
"978-3-319-58747-9"
],
"name": "Computer Science \u2013 Theory and Applications",
"type": "Book"
},
"keywords": [
"rate",
"hand",
"definition",
"results",
"existence",
"usage",
"depth",
"density",
"second-order logic",
"first-order logic",
"formula",
"first-order definition",
"complexity",
"connected graph",
"descriptive complexity",
"logic",
"quantifiers",
"first-order formulas",
"vertices",
"isomorphic",
"induced subgraph",
"graph",
"subgraphs",
"isomorphism",
"complete graph",
"numerics",
"large connected graph",
"large treewidth",
"treewidth",
"succinctness results",
"subgraph isomorphism",
"subgraphs isomorphic",
"quantifier depth",
"smaller quantifier depth",
"first-order quantifier depth",
"super-recursive rate"
],
"name": "The Descriptive Complexity of Subgraph Isomorphism Without Numerics",
"pagination": "308-322",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1085148876"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-319-58747-9_27"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-319-58747-9_27",
"https://app.dimensions.ai/details/publication/pub.1085148876"
],
"sdDataset": "chapters",
"sdDatePublished": "2021-11-01T19:01",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_57.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-319-58747-9_27"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-58747-9_27'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-58747-9_27'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-58747-9_27'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-58747-9_27'

This table displays all metadata directly associated to this object as RDF triples.

109 TRIPLES      23 PREDICATES      64 URIs      57 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author N260669d64e234f8c9d55b6193c0cc5e8
4 schema:datePublished 2017-05-06
5 schema:datePublishedReg 2017-05-06
6 schema:description Let F be a connected graph with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell$$\end{document} vertices. The existence of a subgraph isomorphic to F can be defined in first-order logic with quantifier depth no better than \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell$$\end{document}, simply because no first-order formula of smaller quantifier depth can distinguish between the complete graphs \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_\ell$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_{\ell -1}$$\end{document}. We show that, for some F, the existence of an F subgraph in sufficiently large connected graphs is definable with quantifier depth \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell -3$$\end{document}. On the other hand, this is never possible with quantifier depth better than \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell /2$$\end{document}. If we, however, consider definitions over connected graphs with sufficiently large treewidth, the quantifier depth can for some F be arbitrarily small comparing to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell$$\end{document} but never smaller than the treewidth of F.We also prove that any first-order definition of the existence of an induced subgraph isomorphic to F requires quantifier depth strictly more than the density of F, even over highly connected graphs. From this bound we derive a succinctness result for existential monadic second-order logic: A usage of just one monadic quantifier sometimes reduces the first-order quantifier depth at a super-recursive rate.
7 schema:editor Nb79580d801bb4a6ab9e7e6ed1878f05b
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N31278f8b3dc047299f25c941aa8265f8
12 schema:keywords complete graph
13 complexity
14 connected graph
15 definition
16 density
17 depth
18 descriptive complexity
19 existence
21 first-order definition
22 first-order formulas
23 first-order logic
24 first-order quantifier depth
25 formula
26 graph
27 hand
28 induced subgraph
29 isomorphic
30 isomorphism
31 large connected graph
32 large treewidth
33 logic
36 numerics
37 quantifier depth
38 quantifiers
39 rate
40 results
41 second-order logic
42 smaller quantifier depth
43 subgraph isomorphism
44 subgraphs
45 subgraphs isomorphic
46 succinctness results
47 super-recursive rate
48 treewidth
49 usage
50 vertices
51 schema:name The Descriptive Complexity of Subgraph Isomorphism Without Numerics
52 schema:pagination 308-322
53 schema:productId N27985e6270e64bf28d3316d06b35c477
54 N5cc1fb438a944fea9d5f9d62dcd64d60
56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085148876
57 https://doi.org/10.1007/978-3-319-58747-9_27
58 schema:sdDatePublished 2021-11-01T19:01
60 schema:sdPublisher N9d749600bf174fb1ae6b8cd3777ac61d
61 schema:url https://doi.org/10.1007/978-3-319-58747-9_27
63 sgo:sdDataset chapters
64 rdf:type schema:Chapter
65 N260669d64e234f8c9d55b6193c0cc5e8 rdf:first sg:person.01046052752.53
66 rdf:rest N386ea61830c9404eb3de8aab7ce444a8
67 N27985e6270e64bf28d3316d06b35c477 schema:name dimensions_id
68 schema:value pub.1085148876
69 rdf:type schema:PropertyValue
70 N31278f8b3dc047299f25c941aa8265f8 schema:isbn 978-3-319-58746-2
71 978-3-319-58747-9
72 schema:name Computer Science – Theory and Applications
73 rdf:type schema:Book
74 N386ea61830c9404eb3de8aab7ce444a8 rdf:first sg:person.011152672013.96
75 rdf:rest rdf:nil
76 N5cc1fb438a944fea9d5f9d62dcd64d60 schema:name doi
77 schema:value 10.1007/978-3-319-58747-9_27
78 rdf:type schema:PropertyValue
79 N9d749600bf174fb1ae6b8cd3777ac61d schema:name Springer Nature - SN SciGraph project
80 rdf:type schema:Organization
81 Nb79580d801bb4a6ab9e7e6ed1878f05b rdf:first Nc4de1b34096b450896bb8945e725e0d3
82 rdf:rest rdf:nil
83 Nc4de1b34096b450896bb8945e725e0d3 schema:familyName Weil
84 schema:givenName Pascal
85 rdf:type schema:Person
87 rdf:type schema:Organisation
88 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
89 schema:name Information and Computing Sciences
90 rdf:type schema:DefinedTerm
91 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
92 schema:name Computation Theory and Mathematics
93 rdf:type schema:DefinedTerm
94 sg:person.01046052752.53 schema:affiliation grid-institutes:grid.7468.d
95 schema:familyName Verbitsky
96 schema:givenName Oleg
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01046052752.53
98 rdf:type schema:Person
99 sg:person.011152672013.96 schema:affiliation grid-institutes:grid.18763.3b
100 schema:familyName Zhukovskii
101 schema:givenName Maksim
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011152672013.96
103 rdf:type schema:Person
104 grid-institutes:grid.18763.3b schema:alternateName Department of Discrete Mathematics, Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow Region, Russia
105 schema:name Department of Discrete Mathematics, Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow Region, Russia
106 rdf:type schema:Organization
107 grid-institutes:grid.7468.d schema:alternateName Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099, Berlin, Germany
108 schema:name Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099, Berlin, Germany
109 rdf:type schema:Organization