On perfect 2-colorings of the q-ary n-cube

A coloring of a 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 value 1 the same number of times for each m-dimensional face of the hypercube. Let f = chi(s) he a characteristic function of a subset S of hypercube. In the present paper we prove the inequality rho(S)q(cor(f) + 1) <= alpha(S), where cor(f) is the maximum degree of the correlation immunity of f. alpha(S) is the average number of neighbors in the set S for n-tuples in the complement of a set S, and rho(S) = vertical bar S vertical bar/q(n) is the density of the set S. Moreover, the function f is a perfect coloring if and only if we have an equality in the formula above. Also, we find a new lower bound for the cardinality of components of a perfect coloring and a 1-perfect code in the case q > 2. (C) 2011 Elsevier B.V. All rights reserved.