Mathematics – Combinatorics
Scientific paper
2011-01-19
Mathematics
Combinatorics
5 pages
Scientific paper
A coloring of the Boolean $n$-cube is called perfect if, for every vertex $x$, the collection of the colors of the neighbors of $x$ depends only on the color of $x$. A Boolean function is called correlation-immune of degree $n-m$ if it takes the value 1 the same number of times for each $m$-face of the Boolean $n$-cube. In the present paper it is proven that each Boolean function $\chi^S$ ($S\subset E^n$) satisfies the inequality $${\rm nei}(S)+ 2({\rm cor}(S)+1)(1-\rho(S))\leq n,$$ where ${\rm cor}(S)$ is the maximum degree of the correlation immunity of $\chi^S$, ${\rm nei} (S)= \frac{1}{|S|}\sum\limits_{x\in S}|B(x)\cap S|-1$ is the average number of neighbors in the set $S$ for vertices in $S$, and $\rho(S)=|S|/2^n$ is the density of the set $S$. Moreover, the function $\chi^S$ is a perfect coloring if and only if we obtain an equality in the above formula. Keywords: hypercube, perfect coloring, perfect code, correlation-immune function.
No associations
LandOfFree
On the connection between correlation-immune functions and perfect 2-colorings of the Boolean 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 the connection between correlation-immune functions and perfect 2-colorings of the Boolean n-cube, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the connection between correlation-immune functions and perfect 2-colorings of the Boolean n-cube will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-156080