Geodesic
On the perfectness of minimal regular partitions of the edge set of the $n$-dimensional cube
Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 4, pp. 74-107.

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

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. 
@article{DA_2019_26_4_a4,
     author = {K. L. Rychkov},
     title = {On the perfectness of minimal regular partitions of the edge set of the $n$-dimensional cube},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {74--107},
     publisher = {mathdoc},
     volume = {26},
     number = {4},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2019_26_4_a4/}
}
TY  - JOUR
AU  - K. L. Rychkov
TI  - On the perfectness of minimal regular partitions of the edge set of the $n$-dimensional cube
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2019
SP  - 74
EP  - 107
VL  - 26
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2019_26_4_a4/
LA  - ru
ID  - DA_2019_26_4_a4
ER  - 
%0 Journal Article
%A K. L. Rychkov
%T On the perfectness of minimal regular partitions of the edge set of the $n$-dimensional cube
%J Diskretnyj analiz i issledovanie operacij
%D 2019
%P 74-107
%V 26
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2019_26_4_a4/
%G ru
%F DA_2019_26_4_a4
K. L. Rychkov. On the perfectness of minimal regular partitions of the edge set of the $n$-dimensional cube. Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 4, pp. 74-107. http://geodesic.mathdoc.fr/item/DA_2019_26_4_a4/

[1] V. M. Khrapchenko, “Complexity of the realization of a linear function in the class of $\Pi$-circuits”, Math. Notes Acad. Sci. USSR, 9:1 (1971), 21–23 | MR | Zbl | Zbl

[2] V. M. Khrapchenko, “A method of determining lower bounds for the complexity of $\Pi$-schemes”, Math. Notes Acad. Sci. USSR, 10:1 (1971), 474–479 | MR | Zbl

[3] V. M. Khrapchenko, “A simplified proof of a lower complexity estimate”, Discrete Math. Appl., 23:2 (2013), 171–174 | DOI | DOI | MR | Zbl

[4] K. L. Rychkov, “A modification of Khrapchenko's method and its application to estimation of complexity of $\Pi$-schemes for code functions”, Methods of Discrete Analysis in Theory of Graphs and Schemes, 42, Izd. Inst. Mat., Novosibirsk, 1985, 91–98 (Russian)

[5] A. Razborov, “Applications of matrix methods to the theory of lower bounds in computational complexity”, Combinatorica, 10:1 (1990), 81–93 | DOI | MR | Zbl

[6] M. Karchmer, A. Wigderson, “Monotone circuits for connectivity require super-logarithmics depth”, SIAM J. Discrete Math., 3:2 (1990), 255–265 | DOI | MR | Zbl

[7] J. Håstad, “The shrinkage exponent of de Morgan formulas is 2”, SIAM J. Comput., 27 (1998), 48–64 | DOI | MR

[8] D. Yu. Cherukhin, “To the question of a logical representation for the parity counter”, Neform. Nauka, 2009, no. 2, 14–23 (Russian)

[9] S. V. Avgustinovich, Yu. L. Vasil'ev, K. L. Rychkov, “The computation complexity in the class of formulas”, J. Appl. Ind. Math., 6:4 (2012), 403–409 | DOI | MR | MR | Zbl

[10] Yu. L. Vasil'ev, K. L. Rychkov, “A lower bound on formula size of a ternary linear function”, J. Appl. Ind. Math., 7:4 (2013), 490–499 | MR | Zbl

[11] K. L. Rychkov, “On minimal $\pi$-schemes for linear Boolean functions”, Sib. Adv. Math., 3:3 (1993), 172–185 | MR

[12] S. V. Yablonskii, “Realization of a linear function in the class of $\Pi$-circuits”, Dokl. Akad. Nauk SSSR, Nov. Ser., 94:5 (1954), 805–806 (Russian) | Zbl

[13] K. L. Rychkov, “Sufficient conditions for the minimal $\pi$-schemes for linear Boolean functions to be locally nonrepeating”, J. Appl. Ind. Math., 9:4 (2015), 580–587 | DOI | MR | Zbl

[14] K. L. Rychkov, “Complexity of the realization of a linear Boolean function in the class of $\pi$-schemes”, J. Appl. Ind. Math., 12:3 (2018), 540–576 | DOI | MR | Zbl

[15] F. Harary, Graph theory, Addison-Wesley, London, 1969, 273 pp. | MR | Zbl

[16] P. Turán, “Eine Extremalaufgabe aus der Graphentheorie”, Mat. Fiz. Lapok, 48 (1941), 436–452 (Hungarian) | MR