تقرير
Logical complexity of induced subgraph isomorphism for certain graph families
| العنوان: | Logical complexity of induced subgraph isomorphism for certain graph families |
|---|---|
| المؤلفون: | Kudryavtsev, E. D., Makarov, M. V., Shlychkova, A. S., Zhukovskii, M. E. |
| سنة النشر: | 2019 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics |
| الوصف: | We prove that, for every $\ell\geq 4$, there exists an $\ell$-vertex graph and a first order sentence having a quantifier depth at most $\ell-1$ defining the property of having an induced subgraph isomorphic to the given one. We prove that a first order sentence defining the property of containing an induced subgraph on $\ell$ vertices isomorphic to a given disjoint union of isomorphic complete multipartite graphs has a quantifier depth at least $\ell$. Finally, we prove that, for every graph on $\ell\leq 5$ vertices a sentence defining the property of containing an induced subgraph isomorphic to the given one has a quantifier depth at least $\ell-1$. Comment: in Russian |
| نوع الوثيقة: | Working Paper |
| اللغة: | Russian |
| URL الوصول: | http://arxiv.org/abs/1902.03648 |
| رقم الأكسشن: | edsarx.1902.03648 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |