The minimal arity of near-unanimity polymorphisms

2017/12/05 by Libor Barto, Barto, Libor, Ondřej Draganov +1
Mathematics · #FOS: Mathematics #Logic (math.LO) #math.LO

paper · pdf · doi:10.48550/arxiv.1712.01731

14 pages, submitted to Mathematica Slovaca

arxiv created 2017/12/05 · arxiv updated 2017/12/06

Abstract

Dmitriy Zhuk has proved that there exist relational structures which admit near-unanimity polymorphisms, but the minimum arity of such a polymorphism is large and almost matches the known upper bounds. We present a simplified and explicit construction of such structures and a detailed, self-contained proof.

Related

• Digraph homomorphism problem and weak near unanimity polymorphism
• Characterizing Bipartite Graphs which Admit k-NU Polymorphisms via Absolute Retracts
• Typical automorphism groups of finite nonrigid structures
• The existence of a near-unanimity function is decidable
• Homomorphisms and Structural Properties of Relational Systems