Part 3. Mathematical models

Bounds on the number of proper families of $k$-valued functions

A. V. Galatenko

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: Proper families of functions are a convenient apparatus for memory-eficient specification of large parametric families of quasigroups and $d$-quasigroups. K.D. Tsaregorodtsev proved that there exists a natural one-to-one correspondence between proper families of functions and unique sink orientations of a Boolean cube. The cardinality of such orientations was estimated by J. Matousek. In our paper we extend Matousek’s lower bound to the case of $k$-valued logics for arbitrary $k > 2$, present a number of corollaries and prove that properness is a rare property, namely, the fraction of proper families of the size n in the class of all families of $n$-ary functions $(f_1,...,f_n)$ such that $x_i$ is dummy for $f_i(x_1,...,x_n)$ tends to $0$ as $n \rightarrow \infty $.

Keywords: proper families of functions, $k$-valued functions, hypergraph, matching