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

Abstract:
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. Institute of Automatization of Designing, RAS,
19/18 2nd Brestskaia str., 123056 Moscow, Russia
e-mail: chip@icad.org.ru