Geodesic
On perfect 2-colorings of the $q$-ary hypercube
Prikladnaâ diskretnaâ matematika, no. 13 (2011), pp. 18-20 
V. N. Potapov. On perfect 2-colorings of the $q$-ary hypercube. Prikladnaâ diskretnaâ matematika, no. 13 (2011), pp. 18-20. http://geodesic.mathdoc.fr/item/PDM_2011_13_a8/
@article{PDM_2011_13_a8,
     author = {V. N. Potapov},
     title = {On perfect 2-colorings of the $q$-ary hypercube},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {18--20},
     year = {2011},
     number = {13},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2011_13_a8/}
}
TY  - JOUR
AU  - V. N. Potapov
TI  - On perfect 2-colorings of the $q$-ary hypercube
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2011
SP  - 18
EP  - 20
IS  - 13
UR  - http://geodesic.mathdoc.fr/item/PDM_2011_13_a8/
LA  - ru
ID  - PDM_2011_13_a8
ER  - 
%0 Journal Article
%A V. N. Potapov
%T On perfect 2-colorings of the $q$-ary hypercube
%J Prikladnaâ diskretnaâ matematika
%D 2011
%P 18-20
%N 13
%U http://geodesic.mathdoc.fr/item/PDM_2011_13_a8/
%G ru
%F PDM_2011_13_a8

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

A coloring of the $q$-ary $n$-dimensional cube (hypercube) is called perfect if, for every $n$-tuple $x$, the collection of the colors of the neighbors of $x$ depends only on the color of $x$. A Boolean-valued function is called correlation-immune of degree $n-m$ if it takes the value 1 the same number of times for each $m$-dimensional face of the hypercube. Let $f=\chi^S$ be a characteristic function of some subset $S$ of hypercube. In the paper the inequality $\rho(S)q(\operatorname{cor}(f)+1)\le A(S)$ is proved, where $\operatorname{cor}(f)$ is the maximum degree of the correlation immunity of $f$, $A(S)$ is the average number of neighbors in the set $S$ for $n$-tuples in a complement of a set $S$, and $\rho(S)=|S|/q^n$ is the density of the set $S$. Moreover, the function $f$ is a perfect coloring if and only if we obtain an equality in the above formula.

[1] Fon-Der-Flaass D. G., “Perfect 2-colorings of a hypercube”, Siber. Math. J., 48:4 (2007), 740–745 | DOI | MR | Zbl

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

[3] Fon-Der-Flaass D. G., “A bound of correlation immunity”, Siber. Electron. Math. Rep., 4 (2007), 133–135 | MR | Zbl

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

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

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

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

[8] Potapov V. N., “O sovershennykh raskraskakh buleva $n$-kuba i korrelyatsionno-immunnykh funktsiyakh maloi plotnosti”, Sibirskie elektronnye matematicheskie izvestiya, 7 (2010), 372–382 | MR