Definability in the substructure ordering of finite directed graphs

DOI10.1007/S11083-020-09548-XMaRDI QIDQ2665828zbMATH OpenOpenAlexFDO

Authors Ádám Kunos

Publication date 19 November 2021

Published in Order (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.09209

zbMATH Keywords

automorphism groupdirected graphembeddability orderingfirst-order definabilitysubstructure ordering

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Interpolation, preservation, definability (03C40) Directed graphs (digraphs), tournaments (05C20)

Abstract: We deal with first-order definability in the substructure ordering $(mathcalD;sqsubseteq)$ of finite directed graphs. In two papers, the author has already investigated the first-order language of the embeddability ordering $(mathcalD;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 $(mathcalD;sqsubseteq)$ can express that of $(mathcalD;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 $(mathcalD;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}imes{S}_4)time{s}_{alpha}mathbb{Z}_2$, with a particular $alpha$ in the semidirect product, we only prove it is finite.

Recommendations

• Definability in the embeddability ordering of finite directed graphs
• Definability in the embeddability ordering of finite directed graphs. II
• Definability in the substructure ordering of simple graphs
• Definability in substructure orderings. II: Finite ordered sets
• Definability in substructure orderings. I: Finite semilattices

Cites work

• Definability in first order theories of graph orderings
• Definability in substructure orderings. I: Finite semilattices
• Definability in substructure orderings. II: Finite ordered sets
• Definability in substructure orderings. III: Finite distributive lattices
• Definability in substructure orderings. IV: Finite lattices
• Definability in the embeddability ordering of finite directed graphs
• Definability in the embeddability ordering of finite directed graphs. II
• Definability in the substructure ordering of simple graphs
• Definability of recursive predicates in the induced subgraph order
• Defining recursive predicates in graph orders

Cited in

(5)

• Definability in the embeddability ordering of finite directed graphs
• Definability in the embeddability ordering of finite directed graphs. II
• Definability in the substructure ordering of simple graphs
• Definability in the Subword Order
• On the automorphism group of the substructure ordering of finite directed graphs

This page was built for publication: Definability in the substructure ordering of finite directed graphs

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