Abstract
We deal with first-order definability in the substructure ordering \(({\mathscr{D}}; \sqsubseteq )\) of finite directed graphs. In two papers, the author has already investigated the first-order language of the embeddability ordering \(({\mathscr{D}}; \leq )\). The latter has turned out to be quite strong, e.g., it has been shown that, modulo edge-reversing (on the whole graphs), it can express the full second-order language of directed graphs. Now we show that, with finitely many directed graphs added as constants, the first order language of \(({\mathscr{D}}; \sqsubseteq )\) can express that of \(({\mathscr{D}}; \leq )\). The limits of the expressive power of such languages are intimately related to the automorphism groups of the orderings. Previously, analogue investigations have found the concerning automorphism groups to be quite trivial, e.g., the automorphism group of \(({\mathscr{D}}; \leq )\) is isomorphic to \(\mathbb {Z}_{2}\). Here, unprecedentedly, this is not the case. Even though we conjecture that the automorphism group is isomorphic to \((\mathbb {Z}_{2}^{4} \times S_{4})\rtimes _{\alpha } \mathbb {Z}_{2}\), with a particular α in the semidirect product, we only prove it is finite.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ježek, J., McKenzie, R.: Definability in substructure orderings, i: Finite semilattices. Algebra Universalis 61(1), 59 (2009). https://doi.org/10.1007/s00012-009-0002-6
Ježek, J., McKenzie, R.: Definability in substructure orderings, iii: Finite distributive lattices. Algebra Universalis 61(3), 283 (2009). https://doi.org/10.1007/s00012-009-0021-3
Ježek, J., McKenzie, R.: Definability in substructure orderings, iv: Finite lattices. Algebra Universalis 61(3), 301 (2009). https://doi.org/10.1007/s00012-009-0019-x
Ježek, J., McKenzie, R.: Definability in substructure orderings, ii: Finite ordered sets. Order 27(2), 115–145 (2010). https://doi.org/10.1007/s11083-010-9141-9
Kunos, Á.: Definability in the embeddability ordering of finite directed graphs. Order 32(1), 117–133 (2015). https://doi.org/10.1007/s11083-014-9319-7
Kunos, Á.: Definability in the embeddability ordering of finite directed graphs, ii. Order 36(2), 291–311 (2019). https://doi.org/10.1007/s11083-018-9467-2
Ramanujam, R., Ramaswamy, Thinniyam, R.S.: Definability in first order theories of graph orderings International Symposium on Logical Foundations of Computer Science, Springer, pp 331–348 (2016)
Thinniyam, R.S.: Definability of Recursive Predicates in the Induced Subgraph Order Indian Conference on Logic and Its Applications, pp 211–223. Springer (2017)
Thinniyam, R.S.: Defining recursive predicates in graph orders. Logical Methods in Computer Science 14(3). https://doi.org/10.23638/LMCS-14(3:21)2018; https://lmcs.episciences.org/4846 (2018)
Wires, A.: Definability in the substructure ordering of simple graphs. Ann. Comb. 20 (1), 139–176 (2016). https://doi.org/10.1007/s00026-015-0295-4
Acknowledgments
The author is thankful to the anonymous reviewer who pointed out a serious flaw in the paper. In response, the author not just fixed the incorrect part, but also noticed an opportunity to free the paper from some inelegant and uncomfortable technicality.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This research was supported by the UNKP-17-3 New National Excellence Program of the Ministry of Human Capacities and by the Hungarian National Foundation for Scientific Research grant no. K115518.
Rights and permissions
About this article
Cite this article
Kunos, Á. Definability in the Substructure Ordering of Finite Directed Graphs. Order 38, 401–420 (2021). https://doi.org/10.1007/s11083-020-09548-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-020-09548-x