Geodesic
On perfect colorings of Boolean $n$-cube and correlation immune functions with small density
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 7 (2010), pp. 372-382.

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

A coloring of Boolean $n$-cube is called perfect if, for every vertex, the collection of colors of its neighbors depends only on its own color. Parameters of a perfect coloring are given by an array. A Boolean function is called correlation immune of degree $n-m$ if it takes the value $1$ equal number of times on any $m$-face of Boolean $n$-cube. It is proved that Boolean function $\chi^S$ ($S\subset E^n$) is a perfect coloring if it satisfies the equality $\rho(S)=1-\frac{n}{2(1+\mathrm{cor}(S))}$, where $\mathrm{cor}(S)$ is the maximum degree of the correlation immune of $\chi^S$ and $\rho(S)=|S|/2^n$. It is offered a straightforward concatenative construction for a perfect coloring of Boolean $n$-cube with array $ \left(\begin{array}{cc} 0 k(2^s-1)\\ k k(2^s-2)\\ \end{array}\right)$. This construction provides a new lower bound on the number of such perfect colorings. Also we give an upper bound for this number. We find the cardinality of the minimal component of perfect coloring with these parameters and prove that any minimal component of such perfect coloring is linear.
Mots-clés : hypercube, MDS code
Keywords: perfect coloring, perfect code, correlation-immune function, component. 
@article{SEMR_2010_7_a23,
     author = {V. N. Potapov},
     title = {On perfect colorings of {Boolean} $n$-cube and correlation immune functions with small density},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {372--382},
     publisher = {mathdoc},
     volume = {7},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2010_7_a23/}
}
TY  - JOUR
AU  - V. N. Potapov
TI  - On perfect colorings of Boolean $n$-cube and correlation immune functions with small density
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2010
SP  - 372
EP  - 382
VL  - 7
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2010_7_a23/
LA  - ru
ID  - SEMR_2010_7_a23
ER  - 
%0 Journal Article
%A V. N. Potapov
%T On perfect colorings of Boolean $n$-cube and correlation immune functions with small density
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2010
%P 372-382
%V 7
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2010_7_a23/
%G ru
%F SEMR_2010_7_a23
V. N. Potapov. On perfect colorings of Boolean $n$-cube and correlation immune functions with small density. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 7 (2010), pp. 372-382. http://geodesic.mathdoc.fr/item/SEMR_2010_7_a23/

[1] D. G. Fon-Der-Flaass, “Sovershennye 2-raskraski giperkuba”, Sibirskii matematicheskii zhurnal, 48:4 (2007), 923–930 | MR | Zbl

[2] D. G. Fon-Der-Flaass, “Sovershennye 2-raskraski 12-mernogo kuba, dostigayuschie granitsy korrelyatsionnoi immunnosti”, Sibirskie Elektronnye Matematicheskie Izvestiya, 4 (2007), 292–295 | MR | Zbl

[3] D. G. Fon-Der-Flaass, “A bound of correlation immunity”, Sibirskie Elektronnye Matematicheskie Izvestiya (Siberian Electronic Mathematical Reports), 4 (2007), 133–135 | MR | Zbl

[4] K. V. Vorobev, D. G. Fon-Der-Flaass, “O sovershennykh 2-raskraskakh giperkuba”, Sibirskie Elektronnye Matematicheskie Izvestiya, 7 (2010), 65–75 | MR

[5] Yu. V. Tarannikov, “O korrelyatsionno-immunnykh i ustoichivykh bulevykh funktsiyakh”, Matematicheskie voprosy kibernetiki, 11, Fizmatlit, M., 2002, 91–148 | MR

[6] J. Friedman, “On the bit extraction problem”, Proc. 33rd IEEE Symposium on Foundations of Computer Science (1992), 314–319 | Zbl

[7] J. Bierbrauer, “Bounds on orthogonal arrays and resilient functions”, Journal of Combinatorial Designs, 3 (1995), 179–183 | DOI | MR | Zbl

[8] P. R. J. Ostergard, O. Pottonen, and K. T. Phelps, “The perfect binary one-error-correcting codes of length 15: Part II-Properties”, IEEE Transactions on Information Theory, 56 (2010), 2571–2582 | DOI

[9] K. T. Phelps, “A general product construction for error correcting codes”, SIAM J. Algebraic Discrete Methods, 5:2 (1984), 224–228 | DOI | MR | Zbl

[10] D. S. Krotov, “Nizhnie otsenki chisla $m$-kvazigrupp poryadka $4$ i chisla sovershennykh dvoichnykh kodov”, Diskret. analiz i issled. operatsii. Ser. 1, 7:2 (2000), 47–53 | MR | Zbl

[11] D. S. Krotov, S. V. Avgustinovich, “On the number of 1-perfect binary codes: a lower bound”, IEEE Trans. Inform. Theory, 54:4 (2008), 1760–1765 | DOI | MR

[12] O. A. Logachev, A. A. Salnikov, V. V. Yaschenko, Bulevy funktsii v teorii kodirovaniya i kriptologii, Izd-vo MTsNMO, M., 2004

[13] F. Dzh. Mak-Vilyams, N. Dzh. A. Sloen, Teoriya kodov, ispravlyayuschikh oshibki, Svyaz, M., 1979 | Zbl

[14] V. N. Potapov, D. S. Krotov, “Asimptotika chisla $n$-kvazigrupp poryadka 4”, Sibirskii matematicheskii zhurnal, 47:4 (2006), 873–887 | MR | Zbl