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






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


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

This article is cited in 1 scientific paper (total in 1 paper)

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
Received: 08.09.2010

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}


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

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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  mathnet  crossref  crossref  mathscinet  elib
  • Дискретная математика
    Number of views:
    This page:335
    Full text:85
    References:32
    First page:19

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020