Definability in the embeddability ordering of finite directed graphs. II

DOI10.1007/S11083-018-9467-2MaRDI QIDQ2314424zbMATH OpenOpenAlexWikidataFDO

Authors Ádám Kunos

Publication date 22 July 2019

Published in Order (Search for Journal in Brave)

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

zbMATH Keywords

categorydirected graphembeddability orderingfirst-order definability

Mathematics Subject Classification ID

Interpolation, preservation, definability (03C40) Directed graphs (digraphs), tournaments (05C20) Partial orders, general (06A06)

Abstract: We deal with first-order definability in the embeddability ordering $(mathcalD;leq)$ of finite directed graphs. A directed graph $GinmathcalD$ is said to be embeddable into $G^{\prime }inmathcalD$ if there exists an injective graph homomorphism $varphicolonGo{G}^{\prime }$. We describe the first-order definable relations of $(mathcalD;leq)$ using the first-order language of an enriched small category of digraphs. The description yields the main result of one of the author's papers as a corollary and a lot more. For example, the set of weakly connected digraphs turns out to be first-order definable in $(mathcalD;leq)$. Moreover, if we allow the usage of a constant, a particular digraph $A$, in our first-order formulas, then the full second-order language of digraphs becomes available.

Recommendations

• Definability in the embeddability ordering of finite directed graphs
• Definability in the substructure ordering of finite directed graphs
• Definability in first order theories of graph orderings
• Definability in first-order theories of graph orderings
• Definability in the substructure ordering of simple graphs

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 substructure ordering of simple graphs
• Definability of recursive predicates in the induced subgraph order

Cited in

(9)

• Definability in the embeddability ordering of finite directed graphs
• Definability in the substructure ordering of simple graphs
• Definability in the substructure ordering of finite directed graphs
• Complexity in Young's lattice
• Defining recursive predicates in graph orders
• Definability in first-order theories of graph orderings
• Definability of recursive predicates in the induced subgraph order
• Definability in first order theories of graph orderings
• On the automorphism group of the substructure ordering of finite directed graphs

This page was built for publication: Definability in the embeddability ordering of finite directed graphs. II

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