This article is cited 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.
UDC:
519.1+512.5
DOI:
10.17223/20710410/48/2
Fulltext:
PDF file (630 kB)