Smooth digraphs modulo primitive positive constructability and cyclic loop conditions

DOI10.1142/S0218196721500442zbMATH Open1502.08004arXiv1906.05699OpenAlexW3173701534MaRDI QIDQ4958331FDOQ4958331

Albert Vucaj, Florian Starke, Manuel Bodirsky

Publication date: 7 September 2021

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

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.

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)

Cites Work

• Title not available (Why is that?)
• 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)
• \(H\)-coloring dichotomy revisited
• Duality and Polynomial Testing of Tree Homomorphisms
• Taylor's modularity conjecture and related problems for idempotent varieties
• Complexity of tree homomorphisms
• Free Completely Distributive Lattices
• Congruence modularity implies cyclic terms for finite algebras
• CSP dichotomy for special triads
• On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
• The wonderland of reflections
• CSP dichotomy for special polyads
• Algebraic approach to promise constraint satisfaction
• Loop conditions
• Two-element structures modulo primitive positive constructability
• Loop conditions for strongly connected digraphs

Cited In (3)

• 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

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)