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

Galatenko Alexei Vladimirovich

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

Galatenko A. V.

Galatenko Alexei Vladimirovich

associate professor, Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, MaTIS chair

Published: 2025, vol. 29, issue 1, pp. 50–59

Download full text (In Russian)

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.

BibTeX

@article{IS-Galatenko2025,
  author  = {Galatenko, Alexei Vladimirovich},
  title   = {{Bounds on the number of proper families of k-valued functions}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2025},
  volume  = {29},
  number  = {1},
  pages   = {50--59},
}

AMSBIB

\Bibitem{IS-Galatenko2025}
\by A.\,V.~Galatenko
\paper Bounds on the number of proper families of k-valued functions
\jour Intelligent Systems. Theory and Applications
\yr 2025
\vol 29
\issue 1
\pages 50--59
\lang In Russian

Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue