On perfect colorings of Boolean $n$-cube and correlation immune functions with small density

V. N. Potapov

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 7 (2010), pp. 372-382

Résumé

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.

Détail

Mots-clés : hypercube, MDS code
Keywords: perfect coloring, perfect code, correlation-immune function, component.