|
Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports], 2010, Volume 7, Pages 372–382
(Mi semr248)
|
|
|
|
This article is cited in 8 scientific papers (total in 8 papers)
Research papers
On perfect colorings of Boolean $n$-cube and correlation immune functions with small density
V. N. Potapov Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
Abstract:
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.
Keywords:
hypercube, perfect coloring, perfect code, MDS code, correlation-immune function, component.
Received July 30, 2010, published November 4, 2010
Citation:
V. N. Potapov, “On perfect colorings of Boolean $n$-cube and correlation immune functions with small density”, Sib. Èlektron. Mat. Izv., 7 (2010), 372–382
Linking options:
https://www.mathnet.ru/eng/semr248 https://www.mathnet.ru/eng/semr/v7/p372
|
Statistics & downloads: |
Abstract page: | 460 | Full-text PDF : | 94 | References: | 55 |
|