Maximal Digraphs With Respect to Primitive Positive Constructibility

DOI10.1007/S00493-022-4918-1MaRDI QIDQ6362924zbMATH OpenFDO

Publication date 15 March 2021

Full work available at URL https://doi.org/10.1007/S00493-022-4918-1

Abstract: We study the class of all finite directed graphs up to primitive positive constructability. The resulting order has a unique greatest element, namely the graph

P_{1}

with one vertex and no edges. The graph

P_{1}

has a unique greatest lower bound, namely the graph

P_{2}

with two vertices and one directed edge. Our main result is a complete description of the greatest lower bounds of

P_{2}

; we call these graphs submaximal. We show that every graph that is not equivalent to

P_{1}

and

P_{2}

is below one of the submaximal graphs.

This page was built for publication: Maximal Digraphs With Respect to Primitive Positive Constructibility

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