Том 26, номер 4, 2019 г., Стр. 121-131

УДК 519.7
Шапоренко А. С.
Связь однородных бент-функций и графов Нэги

Аннотация:
Исследуется связь однородных бент-функций и графов пересечений специального вида, которые называются графами Нэги и обозначаются через $\Gamma_{(n,k)}$. Граф $\Gamma_{(n,k)}$ — граф, вершины которого соответствуют $\binom{n}{k}$ неупорядоченным подмножествам размера $k$ множества {$1, . . . , 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)}$ и $\Gamma_{(28,7)}$ соответственно, не являются бент-функциями.
Табл. 3, ил. 2, библиогр. 9.

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

DOI: 10.33048/daio.2019.26.649

Шапоренко Александр Сергеевич ¹
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: shaporenko.alexandr@gmail.com

Статья поступила 25 февраля 2019 г.
После доработки — 1 августа 2019 г.
Принята к публикации 28 августа 2019 г.

Литература

[1] Rothaus O. S. On “bent” functions // J. Comb. Theory., Ser. A. 1976. Vol. 20, No. 3. P. 300–305.

[2] Qu C., Seberry J., Pieprzyk J. Homogeneous bent functions // Discrete Appl. Math. 2000. Vol. 102, No. 1–2. P. 133–139.

[3] Charnes C., Rotteler M., Beth T. Homogeneous bent functions, invariants, and designs // Des., Codes Cryptogr. 2002. Vol. 26, No. 1–2. P. 139–154.

[4] Bernasconi A, Codenotti B. Spectral analysis of Boolean functions as a graph eigenvalue problem // IEEE Trans. Comput. 1999. Vol. 48, No. 3. P. 345–351.

[5] Bernasconi A., Codenotti B., VanderKam J. M. A characterization of bent functions in terms of strongly regular graphs // IEEE Trans. Comput. 2001. Vol. 50, No. 9. P. 984–985.

[6] Коломеец Н. А. Верхняя оценка числа бент-функций на расстоянии $2^k$ от произвольной бент-функции от $2k$ переменных // Прикл. дискрет. математика. 2014. № 3. С. 28–39.

[7] Коломеец Н. А. О связности графа минимальных расстояний множества бент-функций // Прикл. дискрет. математика. Прил. 2015. № 8. С. 33–34.

[8] Корсакова Е. П. Классификация графов квадратичных бент-функций от шести переменных // Дискрет. анализ и исслед. операций. 2013. Т. 20, № 5. С. 45–47.

[9] Tokareva N. Bent functions: results and applications to cryptography. Acad. Press, 2015. 220 p.