The Number of Homomorphisms to a Fixed Algebra

Abstract

V této práci dáváme částečnou odpověd' na následující otázku: Pro které pevné konečné algebry A je počet homomorfismů z podobné algebry X do A shora omezen poly- nomem proměnné |X|? Práce je rozdělena do dvou částí: Preliminaries a Results. V první části seznámíme čtenáře s tématem a uvedeme několik základních faktů o počtu homo- morfismů. V hlavní části zobecníme případ dvouprvkového polosvazu na konečné polos- vazy, poté se podíváme na konkrétní tříprvkovou algebru s majoritní operací a konkrétní tříprvkový 2-polosvaz, algebru kámen-nůžky-papír. Pak se podíváme na grupy. Nakonec uvážíme unární algebry. Všechny výše uvedené algebry kromě unárních algeber dávají kladnou odpověď na naši otázku. 1

In this work we give a partial answer to the following question: For which fixed finite algebras A is the number of homomorphisms from a similar algebra X to A bounded from above by a polynomial in the size of X? The work is divided into two parts: Preliminaries and Results. In the first part we introduce the reader to this topic and give some basic facts about the number of homomorphisms. In the main part we generalize the case of a two-element semilattice to a general finite semilattice, then we look at a specific three- element algebra with a majority operation and a specific three-element 2-semilattice, the rock-paper-scissors algebra. Then we study groups. Finally we consider unary algebras. All the algebras mentioned above apart from unary algebras give a positive answer to our question. 1