Maximal Digraphs With Respect to Primitive Positive Constructibility

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.

References in corpus (1)

• Smooth digraphs modulo primitive positive constructability and cyclic loop conditions

Cited by in corpus (1)

• Symmetric Linear Arc Monadic Datalog and Gadget Reductions