RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2010, том 7, страницы 372–382 (Mi semr248)

Эта публикация цитируется в 8 статьях

Статьи

О совершенных раскрасках булева $n$-куба и корреляционно-иммунных функциях малой плотности

В. Н. Потапов

Институт математики им. С. Л. Соболева СО РАН

Аннотация: 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 $\begin{matrix} 0 & k(2^s-1)\\ k & k(2^s-2)\\ \end{matrix}$. 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.

Ключевые слова: hypercube, perfect coloring, perfect code, MDS code, correlation-immune function, component.

УДК: 519.14, 519.174.7

MSC: 05B15, 05C15

Поступила 30 июля 2010 г., опубликована 4 ноября 2010 г.



© МИАН, 2024