Mathematics – Combinatorics
Scientific paper
2011-04-07
Mathematics
Combinatorics
6 pages
Scientific paper
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 present paper it is proven the inequality $\rho(S)q({\rm cor}(f)+1)\leq \alpha(S)$, where ${\rm 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)=|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.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.
No associations
LandOfFree
On perfect 2-colorings of the q-ary n-cube does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On perfect 2-colorings of the q-ary n-cube, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On perfect 2-colorings of the q-ary n-cube will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-717896