First-order definitions of subgraph isomorphism through the adjacency and order relations

DOI10.2140/MOSCOW.2020.9.293MaRDI QIDQ2211263zbMATH OpenOpenAlexFDO

Authors Oleg Grigoryan, Mikhail Makarov, M. E. Zhukovskii

Publication date 10 November 2020

Published in Moscow Journal of Combinatorics and Number Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2140/moscow.2020.9.293

zbMATH Keywords

first-order logicordersubgraph isomorphismdescriptive complexitysubtreelogical complexitylinearly ordered graphsquantifier depth

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

Recommendations

• On first-order definitions of subgraph isomorphism properties
• Logical complexity of induced subgraph isomorphism for certain families of graphs
• On the first-order complexity of induced subgraph isomorphism

Cites work

• scientific article; zbMATH DE number 3910446 (Why is no real title available?)
• A short tutorial on order-invariant first-order logic
• Color-coding
• On the first-order complexity of induced subgraph isomorphism
• Powers of tensors and fast matrix multiplication
• Tight bounds on the asymptotic descriptive complexity of subgraph isomorphism

Cited in

(6)

• On the first-order complexity of induced subgraph isomorphism
• First-order complexity of subgraph isomorphism via Kneser graphs
• On first-order definitions of subgraph isomorphism properties
• The first order definability of graphs: Upper bounds for quantifier depth
• On the first-order complexity of induced subgraph isomorphism
• Logical complexity of induced subgraph isomorphism for certain families of graphs

This page was built for publication: First-order definitions of subgraph isomorphism through the adjacency and order relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2211263)