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), не являются бент-функциями.

Скачать электронную версию публикации