Smooth digraphs modulo primitive positive constructability and cyclic loop conditions

DOI10.1142/S0218196721500442MaRDI QIDQ4958331zbMATH OpenOpenAlexFDO

Authors Manuel Bodirsky, Florian Starke, Albert Vucaj

Publication date 7 September 2021

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

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

zbMATH Keywords

directed cyclesheight 1 identitiesloop conditionsminor-preserving mapsprimitive positive constructionssmooth digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Operations and polynomials in algebraic structures, primal algebras (08A40) Applications of universal algebra in computer science (08A70) Equational logic, Mal'tsev conditions (08B05)

Abstract: Finite smooth digraphs, that is, finite directed graphs without sources and sinks, can be partially ordered via pp-constructability. We give a complete description of this poset and, in particular, we prove that it is a distributive lattice. Moreover, we show that in order to separate two smooth digraphs in our poset it suffices to show that the polymorphism clone of one of the digraphs satisfies a prime cyclic loop condition that is not satisfied by the polymorphism clone of the other. Furthermore, we prove that the poset of cyclic loop ordered by their strength for clones is a distributive lattice, too.

Recommendations

• The structure of polynomial operations associated with smooth digraphs.
• The local loop lemma
• Two-element structures modulo primitive positive constructability
• Loop conditions for strongly connected digraphs
• On Maltsev digraphs

Cites work

• H-coloring dichotomy revisited
• Absorption in universal algebra and CSP
• Algebraic approach to promise constraint satisfaction
• Complexity of tree homomorphisms
• Congruence modularity implies cyclic terms for finite algebras
• CSP dichotomy for special polyads
• CSP dichotomy for special triads
• Duality and Polynomial Testing of Tree Homomorphisms
• Free Completely Distributive Lattices
• Loop conditions
• Loop conditions for strongly connected digraphs
• On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
• Taylor's modularity conjecture and related problems for idempotent varieties
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The wonderland of reflections
• Two-element structures modulo primitive positive constructability

Cited in

(6)

• The structure of polynomial operations associated with smooth digraphs.
• Local–global property for G-invariant terms
• Submaximal clones over a three-element set up to minor-equivalence
• Multisorted Boolean clones determined by binary relations up to minion homomorphisms
• The generic circular triangle-free graph
• Maximal digraphs with respect to primitive positive constructability

This page was built for publication: Smooth digraphs modulo primitive positive constructability and cyclic loop conditions

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