Сибирские электронные математические известия
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Сиб. электрон. матем. изв.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Сибирские электронные математические известия, 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 г.
Тип публикации: Статья
УДК: 519.14, 519.174.7
MSC: 05B15, 05C15
Образец цитирования: В. Н. Потапов, “О совершенных раскрасках булева $n$-куба и корреляционно-иммунных функциях малой плотности”, Сиб. электрон. матем. изв., 7 (2010), 372–382
Цитирование в формате AMSBIB
\RBibitem{Pot10}
\by В.~Н.~Потапов
\paper О~совершенных раскрасках булева $n$-куба и корреляционно-иммунных функциях малой плотности
\jour Сиб. электрон. матем. изв.
\yr 2010
\vol 7
\pages 372--382
\mathnet{http://mi.mathnet.ru/semr248}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/semr248
  • https://www.mathnet.ru/rus/semr/v7/p372
  • Эта публикация цитируется в следующих 8 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Статистика просмотров:
    Страница аннотации:440
    PDF полного текста:83
    Список литературы:52
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024