Связь однородных бент-функций и графов пересечений | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/16

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

Исследуется связь однородных бент-функций и графов пересечений Г(п ^). Граф Г(„Д, -граф, верШ„Ны КСТОРОГС СОС,™,^ (к) НеуП°ряд°ЧеННЫм подь.нс- жествам размера к множества {1,..., n}, две вершины соединены ребром в том и только в том случае, если соответствующие им подмножества имеют в точности один общий элемент. Выделены те n и к, для которых справедливо, что в Г(п ^) есть клики размера к + 1. Выдвинуто предположение о том, что для таких n и к клики размера к + 1 являются максимальными. Получено, что при n = (к + 1)к/2 количество клик размера к + 1 в графе Г(п^) равно n!/^ + 1)!. Установлено, что однородные булевы функции, полученные путём взятия дополнения к кликам максимального размера в графах Г(ю;4) и Г(28,7), не являются бент-функциями.

Connection between homogeneous bent functions and intersection graphs.pdf Бент-функцией называется булева функция от n переменных (n чётно), такая, что расстояние Хэмминга от данной функции до множества всех аффинных функций является максимально возможным. Бент-функция называется однородной, если все одночлены её АНФ имеют одинаковые степени. В [1] определён граф пересечений Г(П)&), вершины которого соответствуют ^ неупорядоченным подмножествам размера k множества {1,... ,n}. Две вершины соединены ребром в том и только в том случае, если соответствующие подмножества имеют в точности один общий элемент. Будем называть дополнением к клике графа Г(п>*) множество всех вершин этого графа, кроме тех, которые являются вершинами рассматриваемой клики. В графе Г(6 3) 20 вершин вида {а,Ь, с}, где а,Ь,с е {1,... , 6} и различны. В этом графе были выделены клики размера 4 (k +1) и, как указано в [1], такой размер клики является максимальным. Всего в графе Г(6 3) 30 таких клик. В Г(6,3) дополнением к клике С с вершинами {1, 3, 6}, {1, 4, 5}, {2, 3, 5} и {2, 4, 6} будет множество, состоящее из 16 вершин. Если мы будем сопоставлять вершинам {€, m,n} одночлены x^xmxn, то 16 вершин дополнения к клике C будут соответствовать 16 одночленам АНФ однородной бент-функции от шести переменных степени 3 [2]. Поскольку таких клик 30 (равно как и однородных бент-функций от шести переменных степени 3 [2]), справедливо, что такие функции находятся во взаимно однозначном соответствии с дополнениями клик (максимальных) С графа Г(6 3), i = 1,... , 30. Встаёт вопрос о возможности классификации однородных бент-функций от большего числа переменных с помощью выделения некоторого подмножества вершин графа r(n)fc). Теорема 1. В графе Г(п,^), n, k G N, не всегда есть клика размера k + 1. Теорема 2. Пусть n ^ (k + 1)k/2, k G N. Тогда в графе T(n,k) найдётся клика размера k + 1 . Теорема 3. Если в графе Г(п,^), n, k G N, есть клика размера k + 1, она не всегда является максимальной. Компьютерные вычисления показали, что для n = 10 и k = 4 максимальный размер клики в графе Г(10,4) равен 5. В этом случае (как и в случае n = 6 и k = 3) n выражается через k формулой n = (k + 1)k/2. В связи с этим появляется предположение о том, что при n = (k + 1)k/2, k G N, в графе Г(п,&) клика размера k + 1 является максимальной. Теорема 4. Пусть n = (k + 1)k/2, k G N. Тогда в графе Г(п,&) количество клик размера k + 1 равно n!/(k + 1)!. Было установлено, что однородные булевы функции, полученные путём взятия дополнения к кликам максимального размера в графах Г(10,4) и Г(28,7), не являются бент-функциями.

Ключевые слова

homogeneous bent functions, однородные бент-функции, intersection graphs, графы пересечений

Авторы

ФИООрганизацияДополнительноE-mail
Шапоренко Александр СергеевичНовосибирский государственный университетстудентshaporenko.alexandr@gmail.com
Всего: 1

Ссылки

Charnes С., Rotteler M., and Beth T. Homogeneous bent functions, invariants, and designs // Designs, Codes and Cryptography. 2002. No. 26. P. 139-154.
Qu C., Seberry J., and Pieprzyk J. Homogeneous bent functions // Discrete Appl. Math. 2000. V. 102. No. 1-2. P. 133-139.
 Связь однородных бент-функций и графов пересечений | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/16

Связь однородных бент-функций и графов пересечений | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/16