|
Сибирские электронные математические известия, 2010, том 7, страницы 372–382
(Mi semr248)
|
|
|
|
Эта публикация цитируется в 8 научных статьях (всего в 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.
Поступила 30 июля 2010 г., опубликована 4 ноября 2010 г.
Образец цитирования:
В. Н. Потапов, “О совершенных раскрасках булева $n$-куба и корреляционно-иммунных функциях малой плотности”, Сиб. электрон. матем. изв., 7 (2010), 372–382
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr248 https://www.mathnet.ru/rus/semr/v7/p372
|
Статистика просмотров: |
Страница аннотации: | 454 | PDF полного текста: | 94 | Список литературы: | 55 |
|