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

smooth digraphsloop conditionsdirected cyclesminor-preserving mapsheight 1 identitiesprimitive positive constructions

Mathematics Subject Classification ID

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

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

• Absorption in universal algebra and CSP
• Algebraic approach to promise constraint satisfaction
• CSP dichotomy for special polyads
• CSP dichotomy for special triads
• Complexity of tree homomorphisms
• Congruence modularity implies cyclic terms for finite algebras
• 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 CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The wonderland of reflections
• Two-element structures modulo primitive positive constructability
• \(H\)-coloring dichotomy revisited

Cited in

(4)

• Submaximal clones over a three-element set up to minor-equivalence
• Multisorted Boolean clones determined by binary relations up to minion homomorphisms
• The structure of polynomial operations associated with smooth digraphs.
• Local–global property for G-invariant terms

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)