RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2019, том 26, выпуск 4, страницы 121–131 (Mi da940)

Связь однородных бент-функций и графов Нэги

А. С. Шапоренкоab

a Новосибирский гос. университет, ул. Пирогова, 2, 630090, Новосибирск, Россия
b JetBrains Research, ул. Пирогова, 1, 630090, Новосибирск, Россия

Аннотация: Исследуется связь однородных бент-функций и графов пересечений специального вида, которые называются графами Нэги и обозначаются через $\Gamma_{(n,k)}$. Граф $\Gamma_{(n,k)}$ — граф, вершины которого соответствуют $\binom{n}{k}$ неупорядоченным подмножествам размера $k$ множества $\{1,\dots,n\}$. Две вершины такого графа соединены ребром в том и только том случае, если рассматриваемые подмножества размера $k$ имеют в точности один общий элемент. Были выделены те значения $n$ и $k$, при которых в графе $\Gamma_{(n,k)}$ клики размера $k+1$ максимальны. Получена формула для числа клик размера $k+1$ в графе $\Gamma_{(n,k)}$ для $n=\frac{(k+1)k}{2}$. Доказано, что однородные булевы функции от $10$ и $28$ переменных, полученные путём взятия дополнения к кликам максимального размера в графах $\Gamma_{(10,4)}$ и Г$_{(28,7)}$ соответственно, не являются бент-функциями. Табл. 3, ил. 2, библиогр. 9.

Ключевые слова: граф пересечений, граф Нэги, однородная бент-функция, клика максимального размера.

УДК: 519.7

Статья поступила: 25.02.2019
Переработанный вариант: 01.08.2019
Принята к публикации: 28.08.2019

DOI: 10.33048/daio.2019.26.649



© МИАН, 2024