Аннотация:
Исследуется связь однородных бент-функций и графов пересечений специального вида, которые называются графами Нэги и обозначаются через $\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