Volume 18, No 2, 2011, P. 75-94

UDC 519.95
I. P. Chukhrov
On kernel and shortest complexes of faces in the unit cube

Studying extreme kernel complexes of faces of given dimension, we obtain lower estimates of the number of shortest complexes of faces in the unit $n$-dimensional cube. It is shown that the number of shortest complex $k$-dimensional faces is of the same logarithm order as the number of complexes consisting of no more than $2^{n-1}$ different faces of dimension $k$, with $1\le k\le c\cdot n$ and $c<0.5$. This implies similar lower bounds for the maximum length of kernel and the number of shortest DNF Boolean functions.
Bibliogr. 15.

Keywords: face, interval, kernel face, complex of faces in n-dimensional unit cube, boolean function, shortest covering.

Chukhrov Igor Petrovich 1
1. Institute of Automatization of Designing, RAS,
19/18 2nd Brestskaia str., 123056 Moscow, Russia
e-mail: chip@icad.org.ru

 © Sobolev Institute of Mathematics, 2015