Sbornik: Mathematics
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Mat. Sb.:
Year:
Volume:
Issue:
Page:
Find




Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register

Sbornik: Mathematics, 2021, Volume 212, Issue 4, Pages 517–530
DOI: https://doi.org/10.1070/SM9259 (Mi sm9259) 		 
Logical complexity of induced subgraph isomorphism for certain families of graphs

M. E. Zhukovskiiab, E. D. Kudryavtsevc, M. V. Makarovc, A. S. Shlychkovac

a Laboratory of Advanced Combinatorics and Network Applications, Moscow Institute of Physics and Technology, Dolgoprudny, Moscow Oblast, Russia
b Moscow Center for Fundamental and Applied Mathematics, Moscow, Russia
c Moscow Institute of Physics and Technology, Dolgoprudny, Moscow Oblast, Russia
English version PDF (506 kB)
References:
PDF
HTML
DOI: https://doi.org/10.1070/SM9259
Abstract: We investigate the problem of the most efficient first-order definition of the property of containing an induced subgraph isomorphic to a given pattern graph, which is closely related to the time complexity of the decision problem for this property.
We derive a series of new bounds for the minimum quantifier depth of a formula defining this property for pattern graphs on five vertices, as well as for disjoint unions of isomorphic complete multipartite graphs. Moreover, we prove that for any $\ell\geqslant 4$ there exists a graph on $\ell$ vertices and a first-order formula of quantifier depth at most $\ell-1$ that defines the property of containing an induced subgraph isomorphic to this graph.
Bibliography: 12 titles.
Keywords: first-order formula, quantifier depth, induced subgraph, logical complexity.
Funding agency Grant number
Russian Science Foundation 18-71-00069
The research of M. E. Zhukovskii was financially supported by the Russian Science Foundation (project no. 18-71-00069) in the Laboratory of Advanced Combinatorics and Network Applications of the Moscow Institute of Physics and Technology. Sections 1, 4.2, 6 and 7, as well as the proofs of Theorems 2 and 4, were written by M. E. Zhukovskii. Sections 2, 3, 4.1 and 5, as well as the proofs of Theorems 1 and 3, were written by the other authors.
Received: 08.04.2019 and 06.12.2020
Russian version:
Matematicheskii Sbornik, 2021, Volume 212, Number 4, Pages 76–90
DOI: https://doi.org/10.4213/sm9259
Bibliographic databases:
Document Type: Article
UDC: 510.67
MSC: 05C, 68Q19
Language: English
Original paper language: Russian
Citation: M. E. Zhukovskii, E. D. Kudryavtsev, M. V. Makarov, A. S. Shlychkova, “Logical complexity of induced subgraph isomorphism for certain families of graphs”, Mat. Sb., 212:4 (2021), 76–90; Sb. Math., 212:4 (2021), 517–530
Citation in format AMSBIB
\Bibitem{ZhuKudMak21}
\by M.~E.~Zhukovskii, E.~D.~Kudryavtsev, M.~V.~Makarov, A.~S.~Shlychkova
\paper Logical complexity of induced subgraph isomorphism for certain families of graphs
\jour Mat. Sb.
\yr 2021
\vol 212
\issue 4
\pages 76--90
\mathnet{http://mi.mathnet.ru/sm9259}
\crossref{https://doi.org/10.4213/sm9259}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2021SbMat.212..517Z}
\elib{https://elibrary.ru/item.asp?id=46877526}
\transl
\jour Sb. Math.
\yr 2021
\vol 212
\issue 4
\pages 517--530
\crossref{https://doi.org/10.1070/SM9259}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000701436600001}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85109148622}
Linking options:
  • https://www.mathnet.ru/eng/sm9259
  • https://doi.org/10.1070/SM9259
  • https://www.mathnet.ru/eng/sm/v212/i4/p76
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Математический сборник Sbornik: Mathematics
    Statistics & downloads:
    Abstract page:254
    Russian version PDF:72
    English version PDF:23
    Russian version HTML:80
    References:21
    First page:6
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024