RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

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

 Diskr. Mat., 2011, Volume 23, Issue 1, Pages 132–158 (Mi dm1136)

On irredundant complexes of faces in the unit cube

I. P. Chukhrov

Abstract: The study of properties of irredundant complexes of faces is connected with the problem of minimisation of Boolean functions in the class of disjunctive normal forms (d.n.f.). In researches by S. V. Yablonskii, Yu. I. Zhuravlev, V. V. Glagolev, Yu. L. Vasilyev, A. A. Sapozhenko, on the base of construction and investigation of properties of particular Boolean functions, estimates of the maximum length and number of irredundant d.n.f. have been obtained.
The author suggests a different approach to investigations of these objects based on constructing and estimating the cardinality of sets of irredundant complexes of faces. In this paper, with the use of the probabilistic approach, new methods of construction and estimation of characteristics of irredundant complexes of faces are suggested, which give a possibility to improve the known estimates. On the base of a method of construction of irredundant complexes of faces in a belt of the unit cube $B^n$ of width $k$, we obtain estimates of the maximum number of faces and the number of irredundant complexes for the faces of dimension $k<(1/4-\varepsilon)n$, where $\varepsilon$ is as small as wished positive constant. By the optimal choice of the parameters we obtain for the logarithm of the number of irredundant complexes of faces the lower bound of order $n2^n$ with constant $1.355\cdot2^{-5}$ for the dimension of the faces $k\approx0.0526n$.
Because of equivalence of the problem of minimisation of Boolean functions in the class of d.n.f. and the problem of construction of complexes of faces covering subsets of vertices of the unit cube, the obtained results can be used for estimation of the maximum values of the length and the number of irredundant d.n.f.

DOI: https://doi.org/10.4213/dm1136

Full text: PDF file (749 kB)
References: PDF file   HTML file

English version:
Discrete Mathematics and Applications, 2011, 21:2, 243–274

Bibliographic databases:

UDC: 512.95

Citation: I. P. Chukhrov, “On irredundant complexes of faces in the unit cube”, Diskr. Mat., 23:1 (2011), 132–158; Discrete Math. Appl., 21:2 (2011), 243–274

Citation in format AMSBIB
\Bibitem{Chu11} \by I.~P.~Chukhrov \paper On irredundant complexes of faces in the unit cube \jour Diskr. Mat. \yr 2011 \vol 23 \issue 1 \pages 132--158 \mathnet{http://mi.mathnet.ru/dm1136} \crossref{https://doi.org/10.4213/dm1136} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2830702} \elib{http://elibrary.ru/item.asp?id=20730379} \transl \jour Discrete Math. Appl. \yr 2011 \vol 21 \issue 2 \pages 243--274 \crossref{https://doi.org/10.1515/DMA.2011.015} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-79959999919} 

• http://mi.mathnet.ru/eng/dm1136
• https://doi.org/10.4213/dm1136
• http://mi.mathnet.ru/eng/dm/v23/i1/p132

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. I. P. Chukhrov, “On the relation between the irredundant and minimal complexes of faces in the unit cube”, Discrete Math. Appl., 22:3 (2012), 273–306
•  Number of views: This page: 344 Full text: 91 References: 33 First page: 19