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

Original · EN

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=χˢ be a characteristic function of some subset S of hypercube. In the present paper it is proven the inequality ρ(S)q(cor(f)+1)≤ α(S), where cor(f) is the maximum degree of the correlation immunity of f, α(S) is the average number of neighbors in the set S for n-tuples in the complement of a set S, and ρ(S)=|S|/qⁿ 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.Also we find new lower bound for the cardinality of components of perfect coloring and 1-perfect code in the case q>2. Keywords: hypercube, perfect coloring, perfect code, MDS code, bitrade, equitable partition, orthogonal array.