Smooth digraphs modulo primitive positive constructability and cyclic loop conditions

Research output: Contribution to journalResearch articleContributedpeer-review

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 conditions ordered by their strength for clones is a distributive lattice, too.

Details

Original languageEnglish
Pages (from-to)929-967
Number of pages39
JournalInternational journal of algebra and computation
Volume31
Issue number5
Publication statusPublished - Aug 2021
Peer-reviewedYes

External IDs

ORCID /0000-0001-8228-3611/work/142241060

Keywords

ASJC Scopus subject areas

Keywords

  • directed cycles, Height 1 identities, loop conditions, minor-preserving maps, primitive positive constructions, smooth digraphs

Library keywords