Abstract:
In the paper, we study the relationship between proper families of Boolean functions and unique sink orientations of Boolean cubes. A family of Boolean functions $ F = (f_1(x_1, \ldots, x_n), \ldots, f_n(x_1, \ldots, x_n))$ is called proper if for every two binary vectors $\alpha, \beta$, $\alpha \ne \beta$, the following condition holds: $$ \exists i (\alpha_i \ne \beta_i\ \&\ f_i(\alpha) = f_i(\beta)).$$ Unique sink orientation of Boolean cube $\mathbb{E}_n$ is such an orientation of edges of $\mathbb{E}_n$ that any subcube of $\mathbb{E}_n$ has a unique sink, i.e., a unique vertex without outgoing edges. The existence of one-to-one correspondence between two classes of objects is proved, and various properties are derived for proper families. The following boundary for the number $T(n)$ of proper families of given size $n$ is obtained: there exist two numbers $B$ and $A$, $B \ge A > 0$, such that $n^{A 2^n} \le T(n) \le n^{B 2^n}$ for $n \ge 2$. Also, coNP-completeness of the problem of recognizing properness is derived.
Keywords:
proper families of Boolean functions, unique sink orientations.
Bibliographic databases:
Document Type:
Article
UDC:519.1+512.5
Language: Russian
Citation:
K. D. Tsaregorodtsev, “One-to-one correspondense between proper families of Boolean functions and unique sink orientations of cubes”, Prikl. Diskr. Mat., 2020, no. 48, 16–21
This publication is cited in the following 5 articles:
A. V. Galatenko, V. A. Nosov, A. E. Pankratev, K. D. Tsaregorodtsev, “O porozhdenii $n$-kvazigrupp s pomoschyu pravilnykh semeistv funktsii”, Diskret. matem., 35:1 (2023), 35–53
A. V. Galatenko, V. A. Nosov, A. E. Pankratiev, K. D. Tsaregorodtsev, “Proper families of functions and their applications”, Matem. vopr. kriptogr., 14:2 (2023), 43–58
A. V. Galatenko, A. E. Pankratiev, K. D. Tsaregorodtsev, “A criterion of properness for a family of functions”, J. Math. Sci., 284:4 (2024), 451–459
A. V. Galatenko, A. E. Pankratiev, V. M. Staroverov, “Generation of Proper Families of Functions”, Lobachevskii J Math, 43:3 (2022), 571
K. D. Tsaregorodtsev, “Properties of proper families of Boolean functions”, Discrete Math. Appl., 32:5 (2022), 369–378