Geodesic
On kernel and shortest complexes of faces in the unit cube
Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 2, pp. 75-94

Voir la notice de l'article provenant de la source Math-Net.Ru

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 $c0.5$. This implies similar lower bounds for the maximum length of kernel and the number of shortest DNF Boolean functions. Bibliogr. 15.
Mots-clés : face, interval, kernel face
Keywords: complex of faces in $n$-dimensional unit cube, Boolean function, shortest covering. 
@article{DA_2011_18_2_a6,
     author = {I. P. Chukhrov},
     title = {On kernel and shortest complexes of faces in the unit cube},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {75--94},
     publisher = {mathdoc},
     volume = {18},
     number = {2},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2011_18_2_a6/}
}
TY  - JOUR
AU  - I. P. Chukhrov
TI  - On kernel and shortest complexes of faces in the unit cube
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2011
SP  - 75
EP  - 94
VL  - 18
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2011_18_2_a6/
LA  - ru
ID  - DA_2011_18_2_a6
ER  - 
%0 Journal Article
%A I. P. Chukhrov
%T On kernel and shortest complexes of faces in the unit cube
%J Diskretnyj analiz i issledovanie operacij
%D 2011
%P 75-94
%V 18
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2011_18_2_a6/
%G ru
%F DA_2011_18_2_a6
I. P. Chukhrov. On kernel and shortest complexes of faces in the unit cube. Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 2, pp. 75-94. http://geodesic.mathdoc.fr/item/DA_2011_18_2_a6/