|
This article is cited in 6 scientific papers (total in 6 papers)
Theoretical Backgrounds of Applied Discrete Mathematics
One-to-one correspondense between proper families of Boolean functions and unique sink orientations of cubes
K. D. Tsaregorodtsev Moscow State University, Moscow, Russia
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.
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
Linking options:
https://www.mathnet.ru/eng/pdm701 https://www.mathnet.ru/eng/pdm/y2020/i2/p16
|
Statistics & downloads: |
Abstract page: | 229 | Full-text PDF : | 88 | References: | 33 |
|