Geodesic
On a combinatorial problem for the set of binary vectors
The Bulletin of Irkutsk State University. Series Mathematics, Tome 12 (2015), pp. 49-57 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this paper we introduce a new combinatorial problem for covering binary sets. This problem appears in connection to research of complexity of ESOP. Shannon function is called maximum from complexities of the shortest representation of each Boolean function. Hence the upper bound of the Shannon function guarantees the existence of the representation of any Boolean function with this complexity. It is important for applications. As usual implicit algorithms of minimisation working with any Boolean function are used for defining the upper bound of Shannon function. Previously we have developed the algorithm of minimisation of Boolean functions in ESOPs which uses the combinatorial technique connected with tasks of finding covering and packing of binary sets. ESOP for given Boolean function is built by pattern which is described of non-singular matrix over the field $Z_2$ in that earch row and column matches any binary set. These binary sets should have the packing with density $1+o(1)$ for getting the effective upper bound. It is normal to use error-correcting linear codes for building a matrix of pattern. In this case Hamming code may by used. And so it lets use terms of the linear codes theory in definitions of combinatorial problems. In this paper we investigate a problem which belongs to covering and packing design. In doing so requirements to matrix impose several conditions to cover. In this work some of possible covers are introduced which have been described in terms of error-correcting linear codes.
Keywords: boolean function, ESOP, Hamming code, covering design. 
@article{IIGUM_2015_12_a4,
     author = {K. D. Kirichenko},
     title = {On a combinatorial problem for the set of binary vectors},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {49--57},
     year = {2015},
     volume = {12},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2015_12_a4/}
}
TY  - JOUR
AU  - K. D. Kirichenko
TI  - On a combinatorial problem for the set of binary vectors
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2015
SP  - 49
EP  - 57
VL  - 12
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2015_12_a4/
LA  - ru
ID  - IIGUM_2015_12_a4
ER  - 
%0 Journal Article
%A K. D. Kirichenko
%T On a combinatorial problem for the set of binary vectors
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2015
%P 49-57
%V 12
%U http://geodesic.mathdoc.fr/item/IIGUM_2015_12_a4/
%G ru
%F IIGUM_2015_12_a4
K. D. Kirichenko. On a combinatorial problem for the set of binary vectors. The Bulletin of Irkutsk State University. Series Mathematics, Tome 12 (2015), pp. 49-57. http://geodesic.mathdoc.fr/item/IIGUM_2015_12_a4/

[1] Kirichenko K. D., “Bounds of the minimization patterns' complexity of ESOP”, IIGU Ser. Matematika, 2:2 (2009), 67–76 (in Russian) | MR | Zbl

[2] Bashov M. A., Selezneva C. N., “On the length of functions of $k$-valued logics in modulo $k$ ESOP”, Diskretnaya matematika, 26:3 (2014), 3–9 (in Russian) | DOI | MR

[3] MacWilliams F. J., Sloane N. J. A., The Theory of Error Correction Codes, North-Holland Publishing Company, 1977 | MR

[4] J. N. Cooper, R. B. Ellis, A. B. Kahng, “Asymmetric binary covering codes”, Journal of Combinatorial Theory, 100:2 (2001), 232–249 | DOI | MR

[5] V. Rodl, “On a packing and covering problem”, European Journal of Combinatorics, 6 (1985), 69–78 | DOI | MR | Zbl

[6] P. Turan, “Reseach Problems”, Magyar Tud. Acad. Mat. Kutato Int. Kozl., 6 (1961), 417–423 | MR