Part 2. Mathematics and Computer Science

On growth rate of structures with a finite number of essential constraints

S. A. Komkov

Lomonosov Moscow State University

Abstract: Growth rate is a function defined for an arbitrary finite set $A$ with a set of operations $M$ defined on it. Its order characterizes the strength of given operations. We show that if there is only a finite number of important essential predicates among all predicates that are preserved by each function from $M$ then the growth rate order of the $(A, M)$ pair is logarithmic.

Keywords: growth rate, finite sets, constraint language, logarithmic growth rate.