 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Prikl. Diskr. Mat.: Year: Volume: Issue: Page: Find

 Personal entry: Login: Password: Save password Enter Forgotten password? Register

 Prikl. Diskr. Mat., 2020, Number 48, Pages 16–21 (Mi pdm701)  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.

DOI: https://doi.org/10.17223/20710410/48/2  Full text: PDF file (630 kB) References: PDF file   HTML file

Bibliographic databases: UDC: 519.1+512.5

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 Citation in format AMSBIB
\Bibitem{Tsa20}
\by K.~D.~Tsaregorodtsev
\paper One-to-one correspondense between proper families of~Boolean functions and unique sink orientations of~cubes
\jour Prikl. Diskr. Mat.
\yr 2020
\issue 48
\pages 16--21
\mathnet{http://mi.mathnet.ru/pdm701}
\crossref{https://doi.org/10.17223/20710410/48/2}

 SHARE:      •  Contact us: math-net2022_01 [at] mi-ras ru Terms of Use Registration to the website Logotypes © Steklov Mathematical Institute RAS, 2022