Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2019, 13:4, 717-739
Volume 26, No 4, 2019, P. 74-107
UDC 519.714
K. L. Rychkov
On the perfectness of minimal regular partitions of the edge set of the $n$-dimensional cube
Abstract:
We prove that, for n equal to 3, 5, and a power of 2, every minimal partition of the edge set of the $n$-dimensional cube is perfect. As a consequence, we obtain some description of the classes of all minimal parallel-serial contact schemes ($\pi$-schemes) realizing the linear Boolean functions that depend essentially on $n$ variables for the corresponding values of $n$.
Bibliogr. 16.
Keywords: Boolean function, $\pi$-scheme, regular partition of the edge set of the $n$-dimensional cube, lower complexity bound.
DOI: 10.33048/daio.2019.26.662
Konstantin L. Rychkov 1
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: rychkov@math.nsc.ru
Received June 10, 2019
Revised July 29, 2019
Accepted August 28, 2019
References
[1] V. M. Khrapchenko, Complexity of the realization of a linear function in the class of $\Pi$-circuits, Mat. Zametki 9 (1), 35–40 (1971) [Russian] [Math. Notes Acad. Sci. USSR 9 (1), 21–23 (1971)].[2] V. M. Khrapchenko, A method of determining lower bounds for the complexity of $\Pi$-schemes, Mat. Zametki 10 (1), 83–92 (1971) [Russian] [Math. Notes Acad. Sci. USSR 10 (1), 474–479 (1971)].
[3] V. M. Khrapchenko, A simplified proof of a lower complexity estimate, Discrete Math. 25 (2), 82–84 (2013) [Russian] [Discrete Math. Appl. 23 (2), 171–174 (2013)].
[4] K. L. Rychkov, A modification of Khrapchenko’s method and its application to estimation of complexity $\Pi$-schemes for code functions, in Methods of Discrete Analysis in Theory of Graphs and Schemes, Vol. 42 (Izd. Inst. Mat., Novosibirsk, 1985), pp. 91–98 [Russian].
[5] A. Razborov, Applications of matrix methods to the theory of lower bounds in computational complexity, Combinatorica 10 (1), 81–93 (1990).
[6] M. Karchmer and A. Wigderson, Monotone circuits for connectivity require super-logarithmic depth, SIAM J. Discrete Math. 3 (2), 255–265 (1990).
[7] J. Håstad, The shrinkage exponent of de Morgan formulas is 2, SIAM J. Comput. 27 (1), 48–64 (1998).
[8] D. Yu. Cherukhin, To the question of a logical representation for the parity counter, Neform. Nauka, No. 2, 14–23 (2009) [Russian].
[9] S. V. Avgustinovich, Yu. L. Vasil’ev, and K. L. Rychkov, The computation complexity in the class of formulas, Diskretn. Anal. Issled. Oper. 19 (3), 3–12 (2012) [Russian] [J. Appl. Ind. Math. 6 (4), 403–409 (2012)].
[10] Yu. L. Vasil’ev and K. L. Rychkov, A lower bound on formula size of a ternary linear function, Diskretn. Anal. Issled. Oper. 20 (4), 15–26 (2013) [Russian] [J. Appl. Ind. Math. 7 (4), 490–499 (2013)].
[11] K. L. Rychkov, On minimal $\pi$-schemes for linear Boolean functions, in Methods of Discrete Analysis in Synthesis of Schemes for Boolean Functions, Vol. 51 (Izd. Inst. Mat., Novosibirsk, 1991), pp. 84–104 [Russian] [Sib. Adv. Math. 3 (3), 172–185 (1993)].
[12] S. V. Yablonskii, Realization of a linear function in the class of $\Pi$-circuits, Dokl. Akad. Nauk SSSR, Nov. Ser. 94 (5), 805–806 (1954) [Russian].
[13] K. L. Rychkov, Sufficient conditions for the minimal $\pi$-schemes for linear Boolean functions to be locally nonrepeating, Diskretn. Anal. Issled. Oper. 22 (5), 71–85 (2015) [Russian] [J. Appl. Ind. Math. 9 (4), 580–587 (2015)].
[14] K. L. Rychkov, Complexity of the realization of a linear Boolean function in the class of $\pi$-schemes, Diskretn. Anal. Issled. Oper. 25 (3), 36–94 (2018) [Russian] [J. Appl. Ind. Math. 12 (3), 540–576 (2018)].
[15] F. Harary, Graph Theory (Addison-Wesley, London, 1969).
[16] P. Turán, Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok 48 (1), 436–452 (1941) [Hungarian].
