One-to-one correspondense between proper families of~Boolean functions and unique sink orientations of~cubes

K. D. Tsaregorodtsev

Prikladnaâ diskretnaâ matematika, no. 2 (2020), pp. 16-21

Résumé

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.

Détail

Keywords: proper families of Boolean functions
Mots-clés : unique sink orientations.