pith. sign in

arxiv: 1806.07871 · v1 · pith:QJYFQ3VHnew · submitted 2018-06-20 · 🧮 math.LO

Definability in the embeddability ordering of finite directed graphs, II

classification 🧮 math.LO
keywords first-ordermathcaldigraphsdirecteddefinabilitydefinableembeddabilityfinite
0
0 comments X
read the original abstract

We deal with first-order definability in the embeddability ordering $( \mathcal{D}; \leq)$ of finite directed graphs. A directed graph $G\in \mathcal{D}$ is said to be embeddable into $G' \in \mathcal{D}$ if there exists an injective graph homomorphism $\varphi \colon G \to G'$. We describe the first-order definable relations of $( \mathcal{D}; \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 $(\mathcal{D}; \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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.