Geodesic
On perfect $2$-colorings of the hypercube
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 7 (2010), pp. 65-75.

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

A vertex coloring of a graph is called perfect if the multiset of colors appearing on the neighbours of any vertex depends only on the color of the vertex. The parameters of a perfect coloring are thus given by a $n\times n$ matrix, where $n$ is the number of colors. We give a recursive construction which can produce many different perfect colorings of the hypercube $H_n $ with $2$ colors and the parameters $\left({\begin{array}{ll} a b\\c d \end{array}}\right)$ satisfying the conditions $({b,c})=1,b+c=2^m$, $c>1$. In particular, this construction allows one to find many non-isomorphic perfect colorings with the parameters $\left( {\begin{array}{ll} k\cdot a k\cdot b \\ k\cdot c k\cdot d \end{array}}\right)$. For the parameters $\left({\begin{array}{ll} a b\\c d \end{array}}\right)$ satisfying the extra condition $a\ge c-({b,c})$, we find a lower bound on the number of produced colorings which is hyperexponential in $n$.
Mots-clés : Hypercube
Keywords: perfect coloring, perfect code. 
@article{SEMR_2010_7_a5,
     author = {K. V. Vorobev and D. G. Fon-Der-Flaass},
     title = {On perfect $2$-colorings of the hypercube},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {65--75},
     publisher = {mathdoc},
     volume = {7},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2010_7_a5/}
}
TY  - JOUR
AU  - K. V. Vorobev
AU  - D. G. Fon-Der-Flaass
TI  - On perfect $2$-colorings of the hypercube
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2010
SP  - 65
EP  - 75
VL  - 7
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2010_7_a5/
LA  - ru
ID  - SEMR_2010_7_a5
ER  - 
%0 Journal Article
%A K. V. Vorobev
%A D. G. Fon-Der-Flaass
%T On perfect $2$-colorings of the hypercube
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2010
%P 65-75
%V 7
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2010_7_a5/
%G ru
%F SEMR_2010_7_a5
K. V. Vorobev; D. G. Fon-Der-Flaass. On perfect $2$-colorings of the hypercube. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 7 (2010), pp. 65-75. http://geodesic.mathdoc.fr/item/SEMR_2010_7_a5/

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

[2] M. Kholl, Kombinatorika, Mir, M., 1970, 64–79 | MR

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

[4] 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

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

[6] K. V. Vorobev, “O chisle sovershennykh 2-raskrasok giperkuba”, Materialy XLVI Mezhdunarodnoi nauchnoi studencheskoi konferentsii “Student i nauchno-tekhnicheskii progress”: Matematika, Novosib. gos. un-t, Novosibirsk, 2008, 182