Минимальные носители собственных функций дистанционно регулярных графов тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Сотникова Евгения Вадимовна

• Сотникова Евгения Вадимовна
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Сотникова Евгения Вадимовна

Введение

Глава 1. Кубические дистанционно регулярные графы

1.1 Введение

1.2 Предварительные сведения

1.3 Двудольные графы

1.4 Двойное двудольное покрытие

1.5 Граница весового распределения

1.6 Метод

1.7 ^-условия: Подграфы

1.8 Кубические дистанционно регулярные графы

1.9 Алгоритм

1.10 Основные результаты главы

Глава 2. Графы билинейных форм

2.1 Введение

2.2 Сильно регулярные графы

2.3 Графы билинейных форм И >

Глава 3. Третья глава

3.1 Введение

3.2 Основные результаты главы

Заключение

Список литературы

Введение

В диссертационной работе выполнено исследование собственных функций с минимальным по мощности носителем в некоторых дистанционно регулярных графах, а также рассматривается вопрос вложения произвольного д-значного кода, исправляющего одну ошибку, в совершенный код, исправляющий одну ошибку, большей длины над тем же полем.

Диссертация выполнена в 2014 - 2019 гг. в аспирантуре федерального государственного бюджетного учреждения науки "Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук".

Введение диссертации (часть автореферата) на тему «Минимальные носители собственных функций дистанционно регулярных графов»

Актуальность темы исследования

Комбинаторика является одним из любопытнейших разделов математики. С одной стороны её можно считать относительно "старой" дисциплиной, поскольку отдельные её элементы прослеживаются достаточно далеко в историческом плане. С другой стороны она весьма "молода", так как настоящий расцвет комбинаторики начался лишь недавно. Предполагается, что зародилась комбинаторика на Востоке и что её основоположниками можно считать по большей части Индию и немного Китай. Например, формула числа перестановок п-элементного множества, а также формула числа сочетаний из п-элементного множества по к элеметов были известны ещё в 1150 году и, вероятнее, даже ещё ранее, в VI веке нашей эры. Частные случаи этих формул встречаются и в более ранних текстах, датированных II веком до н.э. В работе Биггса [1] представлен довольно подробный обзор истории комбинаторики до того момента, как она стала самостоятельной дисциплиной. Исходной точкой развития комбинаторики как отдельного направления в том виде, в котором мы знаём её сейчас, принято считать знаменитый трактат Б. Паскаля [2]. В нём исследуются свойства биномиальных коэффициентов, а также впервые формально применяется метод математической индукции. Термин "комбинаторика" появляется в работе [3] (хотя сам Лейбниц трактовал это понятие весьма широко, включая в него всю конечную математику и логику, а также считал комбинаторику важной частью любого исследования, в основе которого лежат анализ и синтез). Согласно Лейбницу главнейшая задача комбинаторного искусства состоит в разложении сложных вещей и понятий на простые "неделимые" элементы и

выявлении всех возможных их комбинаций. В 1713 году выходит работа Я. Бер-нулли [4], представляющая собой трактат из четырёх частей, вторая из которых была посвящена довольно полному и систематичному изложению известных в то время комбинаторных фактов. Окончательно же как самостоятельное направление комбинаторика сформировалась в работах Леонарда Эйлера (конец XVIII века). Более подробный исторический обзор можно найти, например, в [5] и [6].

Несмотря на своё историческое наследние, комбинаторика довольно долго оставалась в тени более классических направлений математики и не воспринималась всерьёз как отдельная дисциплина. Но в двадцатом веке ситуация кардинальным образом поменялась. Ещё до того, как первые компьютеры были построены, исследователи понимали, что их система будет основана на дискретных принципах, а не вещественных, а это приведёт к целому спектру новых постановок задач, которые в конечном итоге породят мощный фундамент новой теории. Бурное развитие технологий также привело к появлению программных пакетов для вычислений и моделирования (Mathematica, MatLab, GAP и др.), и это оказало колоссальное влияние на математику в целом, и комбинаторику в частности. Ведь теперь целый ряд задач, который до этого не поддавался теоретическим решениям, можно было решить с помощью компьютерного перебора. Таким образом, компьютер стал мощным инструментом для проверки гипотез, перебора различных вариантов и работы с большими объёмами данных. Более того, с помощью компьютерных программ стало возможно доказывать теоремы. Первым таким примером, вызвавшим широкий общественный резонанс, была работа 1976 года [7], в которой решалась известная проблема четырёх красок. Невозможность проверки доказательства вручную положила начало спорам в научной среде, можно ли считать компьютерные доказательства математическими доказательствами [8-10]. В настоящий момент времени компьютерные программы уже плотно вошли в число рабочих инструментов математиков. В качестве других примеров результатов, полученных с помощью компьютера, можно привести доказательство несуществования проективной плоскости порядка 10 [11] (см. также [12]), классификацию систем троек Штейнера порядка 19 [13], доказательство несуществования частичной геометрии с параметрами (4, 27, 2) [14]. Отметим, что для получения последнего результата его авторам

потребовался 1 календарный год (что соответствовало 270 годам процессорного времени).

К настоящему моменту времени комбинаторика уже настолько тесно переплелась со многими направлениями математики, что среди научного сообщества нет единого мнения, как именно определять данную дисциплину. Если говорить общими словами, то комбинаторика изучает структуру объектов, упорядоченных в соответствии с некоторыми правилами. При изучении комбинаторных объектов естественным образом возникают задачи существования, перечисления и классификации таких объектов, а также задача построения новых объектов заданного класса с теми же или новыми параметрами. Одним из подходов к решению таких задач состоит в изучении соответствующих трейдов. Неформально говоря, трейды представляют собой некоторое множество, на которое могут отличаться два комбинаторных объекта из одного и того же класса. Пусть С и С' — какие-то комбинаторные конфигурации, имеющие одинаковые параметры (например, латинские квадраты, системы Штейнера, совершенные коды и др.). Тогда С \ С' и С' \ С будут трейдами, а пара (С \ С', С' \ С)

— битрейдом. Заметим, что в литературе также встречается альтернативная терминология: в некоторых работах саму пару называют трейдом.

Интересен тот факт, что часто можно определить трейды независимым образом. В таком случае трейды вовсе не обязательно будут вкладываться в какие-то "полные" конфигурации. Более того, они могут существовать даже при тех параметрах, при которых "полные" конфигурации невозможны. Следовательно, трейды можно рассматривать как некоторое обобщающее понятие. Например, двоичные совершенные коды в графах Хэмминга существуют только тогда, когда длина п представима в виде п = 2т — 1 для некоторого натурального числа т (см. например, [15]). А вот 1-совершенный трейд существует при любом нечётном п [16]. Таким образом, трейды интересно изучать и как самостоятельный комбинаторный объект.

С помощью трейдов можно построить новые конфигурации с необходимыми параматрами. Данный подход основывается на идее свитчинга, то есть на замене подмножества исходной конфигурации на некоторое другое подмножество таким образом, чтобы не нарушались свойства исходного объекта. Пусть (Т0,Т\)

— битрейд, а Т0 — подмножество конфигурации С, называемое свитчинговой компонентой. Тогда Т\ и С \ Т0 будет конфигурацией с теми же параметрами.

В случае когда в конфигурации С есть N попарно непересекающихся трейдов, свитчинг можно независимым образом применить к каждому из трейдов, что даст 2м конфигураций с теми же параметрами. Таким образом, свитчинговый метод позволяет получать нижние оценки на число исследуемых объектов, а задача поиска битрейдов минимальной мощности напрямую связана с вопросами оценки числа объектов.

Свитчинговый метод оказался очень мощным инструментом для построения новых объектов и изучения их различных свойств. В качестве яркого примера можно привести теорию кодирования. Пожалуй, одним из наиболее известных объектов теории кодирования является совершенный код. Рассмотрим векторное пространство ^ размерности п над конечным полем ^ с введённой на нём метрикой Хэмминга (то есть расстояние между двумя векторами определяется как число различных координатных позиций). Произвольное подмножество С С ^ называется кодом. Окружим каждый кодовый вектор кода С сферой радиуса £. Если все такие сферы образуют плотную упаковку пространства (то есть они попарно не пересекаются, а их объединение совпадает со всем пространством), то код С называется совершенным кодом, исправляющим £ ошибок. Впервые совершенные коды возникли в работах Го-лея [17] (двоичный длины 23, троичный длины 11) и Хэмминга [18] (д = 2). Двоичные коды Хэмминга обобщаются на случай произвольного д (см. [19]). Все эти коды образуют линейное подпространство в . Попытки построить другие совершенные коды долгое время не приводили к успехам. Этот факт в итоге объяснился с появлением теоремы о том, что нетривиальный совершенный код над любым полем конечным полем должен иметь параметры кода Хэмминга или Голея [20], [21] (см. также предшествующие работы [22-25]). Таким образом, за исключением единственных с точностью до эквивалентности кодов Голея, не существует совершенных кодов, исправляющих многократные ошибки (несуществование нелинейных совершенных кодов с параметрами кодов Голея было доказано в работе [26]). А вот класс совершенных кодов, исправляющих одну ошибку, напротив, оказался весьма богатым на различные интересные свойства и подструктуры, что в итоге привело к целому ряду крупных задач и большому количеству результатов. Шапиро и Злотник выдвинули гипотезу [19], что все совершенные коды эквиваленты линейным. Однако в 1962 году Ю. Л. Васильевым в работе [27] были построены первые нелинейные совершенные

коды, полученные с помощью свитчинга так называемых ¿-компонент (в исходной работе использовалась терминология дизъюнктивных нормальных форм). ¿-Компонента определяется следующим образом. Пусть С — совершенный двоичный код, а М — некоторое его подмножество. Заменим во всех векторах из М элемент в ¿-ой позиции на противоположный. Обозначим полученное множество М' = М + е^. Множество М называется ¿-компонентой совершенного кода С', если С' = (С\ М) и М' является совершенным кодом. ¿-Компонента называется минимальной, если она не может быть разбита на меньшие ¿-компоненты. За работой Васильева последовала целая серия статей с конструкциями новых нелинейных совершенных кодов. Перечислим некоторые из них: конструкция Моллара [28] (обобщающая конструкцию Васильева), конструкция Зиновьева, конструкция Хедена [29], конструкция Соловьёвой [30] (независимо найдена Фелпсом [31], а затем обобщена в [32]), конструкция Кротова, обобщающая конструкцию Фелпса [33]. В работе [34] было доказано, что любой совершенный код неполного ранга (рангом кода называется размерность линейной оболочки его кодовых векторов) может быть получен конструкцией Кротова. Однако из указанного результата не следует классификация всех таких кодов, поскольку компоненты, используемые в конструкции, сами по себе не классифицированы.

Стоит отметить, что несмотря на то, что вокруг совершенных кодов на текущий момент построена глубокая математическая теория, ряд проблем до сих пор остаётся открытым. Например, не решена задача полной классификации д-значных совершенных кодов для д, являющегося степенью простого числа (для двоичных совершенных кодов длины 15 вопрос решён в работе [35], где найдено 5983 неэквивалентных кодов). Свитчинговые методы позволили получить богатые классы новых конструкций совершенных кодов, тем самым улучшая нижнюю оценку на число различных неэквивалентных кодов. Долгое время оценка, полученная Ю. Л. Васильевым в уже упомянутой работе [27] оставалась наилучшей (незначительное улучшение оценки Васильева получалось с помощью конструкции Моллара [28]). Впервые её удалось улучшить С. В. Ав-густиновичу и Ф. И. Соловьёвой [36] (см. также [37]) с помощью свитчинга так называемых «-компонент. В работе [36] был поставлен вопрос, любой ли совершенный код может быть получен из кода Хэмминга применением последовательных свитчингов? Если бы это имело место, то в перспективе можно было бы получить верхнюю оценку на число совершенных кодов, довольно близкую

к нижней. Однако в работе [38] были предложены совершенные коды длины 15, которые нельзя получить из кода Хэмминга с помощью свитчингов, что опровергло изначальную гипотезу.

Кроме того, свитчинговый метод нашёл широкое применение в работах различных авторов для построения совершенных кодов с заранее заданными свойствами. Рассмотрим несколько таких примеров: задачу о рангах и ядрах, задачу о существовании несистематических совершенных кодов и задачу построения совершенных кодов с тривиальной группой автоморфизмов.

В работе [39] поставлен вопрос какие пары (г, к) можно реализовать в качестве ранга г и размерности ядра к некоторого двоичного совершенного кода. До этого в работах [40] и [41] были найдены все достижимые значения для г и к, соответственно. С помощью свитчингового метода в работе [42] проблема рангов и ядер была положительно решена для всех п = 2т — 1 при к > 5, кроме случая совершенного кода полного ранга длины 31 с размерностью ядра 21 (задача для этого случая была решена в работе [43]).

В работе [44] (см. 5.6 Problem) был поставлен вопрос о существовании несистематических совершенных двоичных кодов (длины 15). Первые примеры таких кодов были представлены в [45] для всех длин п = 2т — 1, т > 8 с помощью свитчинга ¿-компонент. Этот результат был улучшен в статье [46] для т > 5. В той же работе был сформулирован вопрос о минимальном числе свитчингов, которые нужно произвести, чтобы получить из кода Хэмминга несистематический код, ответ на который был получен в статье [47]. Стоит отметить, что в ЛеВан в своей диссертации [48] построил класс неэквивалентных совершенных кодов длины 15, некоторые из которых, как позднее выяснилось, также были несистематическими. Таким образом задача существования двоичных несистематических совершенных кодов решена для всех возможных длин п.

Существование совершенных кодов с тривиальной группой автоморфизмов следует из работы [49], в которой доказано, что любая конечная группа изоморфна полной перестановочной группе автоморфизмов некоторого совершенного кода. В работе [50] с помощью свитчинга «-компонент построен класс несистематичеких двоичных кодов полного ранга длины п = 2т — 1, т > 8 с тривиальной группой автоморфизмов. Этот результат был улучшен С. А. Ма-

люгиным в работе [51] для случая т > 5, а позднее и для случая п = 15 с помощью компьютера.

Разумеется, это лишь небольшая часть результатов. Более детальные обзоры по совершенным кодам и свитчиноговым методам в них можно найти, например, в [52-54].

Стоит отметить, что вопрос существования д-значных кодов для значений д, не являющихся степенью простого числа, до сих пор остаётся открытым (за исключением некоторых частных случаев, см. [55-58]). Известен результат, что если такие коды существуют, то они не эквивалентны групповым кодам [59].

Но вернёмся к трейдам в контексте других комбинаторных объектов. Примером трейдов являются нуль-дизайны. Прежде чем определить их, обратимся к одним из ключевых комбинаторных объектов — ¿-дизайнам. Пусть V, к, £ и Л — это некоторые положительные целые числа, удовлетворяющие условиям £ < к < V. Пусть V — некоторый набор из V различных элементов. Блоком В называется произвольное подмножество из V можности к. ¿-Дизайном 8\(Ъ,к,у) называется такой набор В блоков, что любое ¿-подмножество из V встречается в точности в Л блоках В Е В. Пусть М — свободный Ъ-модуль, порождённый

всеми подмножествами из V; элементами М являются все суммы с = ^ схХ,

х су

где сх Е Ъ. Таким образом ¿-дизайном является такой элемент с = су У,

\у =

где все су > 0, что для всех ¿-подмножеств X выполняется

^ = Л

х су

Подмодуль определяется следующим образом:

Ык = {с Е М : ^ сх = 0, где для \Х\ = к,сх = о} х су

Его элементы называются нуль-дизайнами. Как уже неоднократно упоминалось, понимание структуры нуль-дизайнов позволяет лучше понять структуру ¿-дизайнов, так как произвольный дизайн 8\(Ъ,к,у) отличается от какого-то фиксированного дизайна ^,к,у) на некоторый нуль-дизайн. В работе [60] получена порождающая система для модуля ^, имеющего специальный вид. В [61] аналогичная задача рассматривается в терминах полиномов, что поз-

воляет получить те же самые порождающие более простым способом и в явном виде выразить базис Щ в терминах простых полиномов. Среди других результатов, касающихся нуль-дизайнов, хотелось бы упомянуть следующие: в работах [62], [61], [63] были предложены элегантные конструкции базисов пространств нуль-дизайнов, в [64], [61] найдена размерность пространства и минимальное число ^-подмножеств для построения ненулевого нуль-дизайна, в [65] из уже известных дизайнов были построены новые дизайны с помощью нуль-дизайнов, в [66] определение нуль-дизайнов обобщается на конечные градуированные частично упорядоченные множества.

Наконец, обсудим связь трейдов с ещё одним интересным объектом, изучению которого и посвящена большая часть данной диссертации. Оказывается, многие комбинаторные конфигурации могут быть выражены в терминах собственных функций некоторых графов, отвечающих одному из его собственных значений. Таким образом симметрическую разность двух различных конфигураций можно также представить в виде собственной функции. Отсюда следует, что задача нахождения минимального по мощности битрейда напрямую связана с задачей поиска собственных функций графов с минимальным числом ненулевых значений. В качестве примера рассмотрим связь собственных функций с совершенными раскрасками (также известными как equitable partitions). Совершенной ^-раскраской графа называется такая раскраска его вершин в к цветов, что цветовой состав окрестности каждой из вершин (то есть количество вершин каждого цвета) зависит только от цвета исходной вершин. Рассмотрим произвольную совершенную раскраску в два цвета, черный и белый. Пусть любая чёрная (белая) вершина смежна с a (d) вершинами своего цвета и смежна с b (с) вершинами противоположного цвета. Тогда матрица параметров S совершен-

числами этой матрицы являются 90 = а + Ь = с + ё, и 9\ = а — с.

Отметим, что понятие совершенной раскраски обобщает понятие совершенного кода, исправляющего одну ошибку, поскольку совершенный код длины п можно представить в виде совершенной раскраски графа Хэмминга с

ной раскраски записывается следующим образом: S

п \

, где чёрным вершинам соответствуют кодовые

п — 1

вершины.

Пусть С — множество вершин чёрного цвета, определим функцию

/ М =

{

1 — х * с;

—5тг * * с-

Функция / является собственной функцией графа Хэмминга для собственного числа 9\, принимающей разные значения только в точках разного цвета.

В контексте поиска собственных функций с минимальным носителем, пожалуй, одним из интереснейших (но не единственым) классов графов для изучения является семейство дистанционно регулярных графов. В силу своей природы эти графы позволяют применять к ним целый ряд мощных методов из различных областей математики. Более того, для любого дистанционно регулярного графа из его набора параметров в явном виде можно получить нижнюю оценку на мощность носителя собственной функции. В некоторых случаях эта оценка достигается, однако в некоторых её невозможно реализовать. Оба случая представляют интерес. Кроме того, дистанцинно регулярные графы связаны с ещё одним важнейшим объектом алгебраической комбинаторики, схемами отношений. Схемы отношений представляют собой общую концепцию, позволяющую объединить задачи из разных областей, таких как теория кодирования, теория дизайнов, теория конечных групп и алгебраическая теория графов. Неформально говоря, схема отношений — это некоторое разбиение множества ребёр полного графа, удовлетворяющее определённым условиям регулярности. В комбинаторике схемы отношений являются очень полезным инструментом для решения разнообразных задач. С помощью неравенств, связывающих параметры схем отношений, можно получать, например, верхние оценки на размер кодов, исправляющих ошибки, или нижние оценки на число блоков в ¿-дизайнах. Отметим, что задача полной характеризации всех дистанционно регулярных графов на текущий момент времени не решена, несмотря на огромное количество исследований, посвящённых данному вопросу.

И, наконец, хотелось бы сказать несколько слов о выборе графа билинейных форм в качестве объекта исследований в данной работе (см. Главу 2). Графы билинейных форм интересны не только как семейство дистанционно регулярных с бесконечно растущим диаметром. С ними связаны так называемые ранговые коды, в которых вместо метрики Хэмминга используется ранговая метрика. В последнее время среди исследователей наблюдается повышенный

интерес к ранговым кодам [67-69]. Это связано не только с их теоретической значимостью. Ранговые коды нашли своё применения в таких областях, как криптография [70; 71], пространственно-временное кодирование [72], случайное сетевое кодирование [73-75]. Первые конструкции ранговых кодов были даны Дельсартом ещё в 1978 [76]. Широко известны оптимальные ранговые коды (МРД-коды), называемые (обобщёнными) кодами Габидуллина. Впервые они были введены в [77], а затем обобщены в [78]. Другие конструкции линейных МРД-кодов были предложены в работах [79;80]. Бесконечное семейство нелинейных МРД-кодов было построено в [81]. Вопрос нахождения новых конструкций МРД-кодов остаётся открытым, поэтому изучение различных подструктур в графах билинейных форм представляется весьма актуальным и интересным.

Степень разработанности темы исследования

Задача описания собственных функций с минимальным по мощности носителем рассматривалась разными авторами для многих семейств графов. В данном разделе мы опишем известные на текущий момент результаты. Начнём с графов Хэмминга. Вершинами графа Хэмминга Н(п,д) являются упорядоченные п-кортежи с элементами из некоторого множества мощности д. Две вершины считаются смежными, если они отличаются в одной позиции. В работе [82] Д. Кротовым отмечается, что для двоичного случая размер минимального носителя 2(п+|0|)/2 найти не сложно, но публикаций этого факта не известно, поэтому приводится ход доказательства и пример собственной функции с таким носителем. Из работы В. Потапова [83] следует, что носитель собственной функции / : Н(п,д) ^ {-1,0,1} с собственным значением 0 = п(д — 1) — д• г по мощности не может быть меньше 2г. Д. Кротов и К. Воробьёв в статье [84] ([85] — перевод) с помощью полиномов Кравчука улучшили эту нижнюю оценку мощности носителя при д > 2, а также привели явную конструкцию 1-совершенного трейда, имеющего на тот момент минимальную мощность. Затем в работе А. А. Валю-женича [86] было доказано, что собственная функция графа Хэмминга Н(п,д), отвечающая второму по максимальности собственному значению, может иметь минимум 2(д — 1)дп—2 ненулей, а также была приведена полная характеризация всех функций с минимальным носителем. В статье А. Валюженича и К. Воробьёва [87] рассматривается более общая задача, состоящая в нахождении минимального носителя функции, принадлежащей прямой сумме собственных пространств и^(п,д), и+\(п,д),... ,Uj(п,д), отвечающих последовательным соб-

ственным числам 9i, 9+\, ..., 9j, где 9^ = n(q — 1) — q • к. В случае п > i + j и q > 3 авторами найдена минимальная возможная мощность носителя таких функций, а также получена полная характеризация функций с минимальным носителем. В случае п < i + j при q > 4 найдена мощность минимального носителя. Характеризация также приведена для случаев i = j, п < 2i при q > 5. В частности, была получена характеризация собственных функций с минимальным носителем из собственного пространства Ui(n,q) для случаев i < |, q > 3 и i > |, q > 5. Случай малых q и п < г + j при i = j не покрывается харак-теризацией, и авторы приводят несколько примеров, наглядно показывающих сложности, которые возникают при этих параметрах.

Задача о минимальных носителях собственных функций графов Джонсона рассматривалась К. Воробьёвым и соавторами [88]. Вершинами графа Джонсона J(n,w) являются двоичные векторы длины п, содержащие w единиц. Ребрами соединяются те вершины, которые имеют в точности w — 1 общих единиц. В упомянутой работе доказано, что для любого i £ {1,... ,w} и для всех достаточно больших п > n0(i,w) собственная функция, соответствующая собственному значению Xi = (п—w—i)(w—i) — i, имеет по меньшей мере ненулей. Кроме того, в той же работе приведена характеризация собственных функций, достигающих этой границы. Задача оценки n0(i,w) на текущий момент времени остаётся открытой.

C. Горяиновым и соавторами [89] на основе найденного ими семейства новых максимальных клик в графах Пэли квадратичного порядка q2, где q — степень нечётного простого числа, были построены собственные функции, соответствующие двум неглавным собственным значениям, с носителем мощности q + 1, то есть достигающим нижней оценки весового распределения. Графы Пэли Р(q) являются графами Кэли аддитивной группы F+ конечного поля с порождающим множеством, состоящим из всех квадратов мультипликативной группы F*, при дополнительном условии q = 1 mod 4.

Минимальные носители собственных функций графа Дуба изучались Е. Беспаловым в работе [90]. Графом Дуба D(m,n) называется декартово произведение т копий графа Шрикханде и п копий полного графа К4. Это дистанционно регулярный граф, чьи параметры совпадают с параметрами графа Хэмминга Н(2т + п, 4). Беспаловым была получена характеризация всех собственных функций с минимальным носителем, соответствующих второму по

максимальности собственному значению (в этом случае мощность минимально носителя равна 6 • 42m+n—2), а также для случая минимального собственного числа (мощность минимального носителя — 22m+n).

Интересен тот факт, что аналогичная задача для графов Грассманна была решена в более ранних работах, будучи сформулированной в другом контексте и терминологии. Вершинами графа Грассмана Jq(N,m) являются все т-мерные подпространства векторного пространства F^. Две вершины U и V смежны, если размерность пересечения соответствующих подпространств равна т — 1, иными словами U ~ V ^^ dim(^P\V) = т—1. G. D. James в [91], рассматривая задачу о размере носителя некоторых представлений общей линейной группы над Fg, приводит пример нуль-дизайна из Nq(t,t + 1,п) с носителем мощности 2(1+ q)(1 + q2)... (1+ qf), а также выдвигает гипотезу, что это будут минимальные носители таких нуль-дизайнов. S. Cho в работе [92] подтверждает эту гипотезу, а в работе [66] приводит характеризацию нуль-дизайнов с минимальным носителем в терминах максимальных изотропных пространств некоторой билинейной формы. В контексте терминологии собственных функций аналогичный результат приводится в [93].

Список литературы диссертационного исследования кандидат наук Сотникова Евгения Вадимовна, 2019 год

Список литературы

1. Biggs, N. L. The roots of combinatorics / N. L. Biggs // Historia Mathematica. — 1979. — Vol. 6, no. 2. — P. 109-136.

2. Pascal, B. Traite du triangle arithmétique avec quelques autres petits traites sur la mesme Matiere / B. Pascal // Dezprez, Paris. — 1665.

3. Leibniz, G. W. Dissertatio de arte combinatoria / G. W. Leibniz // Fickium & Seuboldum, Leipzig. — 1666.

4. Bernoulli, J. Ars conjectandi, opus posthumum. Accedit Tractatus de seriebus infinitis, et epistola gallice scripta de ludo pilae reticularis / J. Bernoulli // Basel: Thurneysen Brothers. — 1713.

5. Handbook of Combinatorics (Vol. 2) / Ed. by R. L. Graham, M. Grotschel, L. Lovasz. — Cambridge, MA, USA: MIT Press, 1995. — 1281 p.

6. Combinatorics: ancient and modern / Ed. by R. Wilson, J. J. Watkins. — Oxford University Press, 2013. — 368 p.

7. Appel, K. Every planar map is four colorable / K. Appel, W. Haken // Bulletin of the American Mathematical Society. — 1976. — Vol. 82, no. 5. — P. 711-712.

8. Swart, E. R. The philosophical implications of the four-color problem / E. R. Swart // The American Mathematical Monthly. — 1980. — Vol. 87, no. 9. — P. 697-707.

9. Tymoczko, T. Computers, proofs and mathematicians: a philosophical investi-gaion of the four-color proof / T. Tymoczko // Math. Mag. — 1980. — Vol. 53, no. 3. — P. 131-138.

10. Wilson, R. Four colours suffice: how the map problem was solved — revised color edition. / R. Wilson. — Princeton University Press, 2013. — 224 p.

11. Lam, C. W. H. The non-existence of finite projective planes of order 10 / C. W. H. Lam, S. Swiercz, L. Thiel // Canadian Journal of Mathematics. — 1989. — Vol. 41, no. 6. — P. 1117-1123.

12. Lam, C. W. H. The search for a finite projective plane of order 10 / C. W. H. Lam // American Mathematical Monthly. — 1991. — Vol. 98, no. 4. — P. 305-318.

13. Kaski, P. The Steiner triple systems of order 19 / P. Kaski, P. Ostergard // Math. Comput. — 2004. — Vol. 73, no. 248. — P. 2075-2092.

14. Ostergard, P. R. J. There is no McLaughlin geometry / P. R. J. (Ostergard, L. H. Soicher // Journal of Combinatorial Theory, Series A. — 2018. — Vol. 155. — P. 27-41.

15. MacWilliams, F. J. The theory of error-correcting codes / F. J. MacWilliams, N. J. Sloane. — North Holland Publishin Co., 1977. — 762 p.

16. Васильев, Ю. Л. О подвижных множествах в двоичном гиперкубе / Ю. Л. Васильев, С. В. Августинович, Д. С. Кротов // Дискретный анализ и исследование операций. — 2008. — Т. 15, № 3. — С. 11-21.

17. Golay, M. J. E. Notes on digital coding / M. J. E. Golay // Proceedings of the I.R.E. — 1949. — Vol. 37. — P. 657.

18. Hamming, R. W. Error detecting and error correcting codes / R. W. Hamming // The Bell System Technical Journal. — 1950. — Vol. 29, no. 2. — P. 147-160.

19. Shapiro, H. S. On the mathematical theory of error correcting codes / H. S. Shapiro, D. L. Slotnik // IBM Journal of Research and Development. — 1959. — Vol. 3, no. 1. — P. 25-34.

20. Зиновьев, В. А. Несуществование совершенных кодов над полями Галуа / В. А. Зиновьев, В. К. Леонтьев // Проблемы управления и теории информации. — 1973. — Т. 2, № 2. — С. 123-132.

21. Tietavainen, A. On the nonexistence of perfect codes over finite fields / A. Tietavainen // SIAM Journal on Applied Mathematics. — 1973. — Vol. 24, no. 1. — Pp. 88-96.

22. Lloyd, S. P. Binary block coding / S. P. Lloyd // Bell Systems Technical Journal. — 1957. — Vol. 36, no. 2. — P. 517-535.

23. van Lint, J. H. On the nonexistence of perfect 2- and 3-Hamming-error correcting codes over GF(q) / J. H. van Lint // Inform. and Control. — 1970. — Vol. 16, no. 4. — P. 396-401.

24. Tietavainen, A. There are no unknown perfect binary codes / A. Tietavainen, A. Perko // Annales Universitatis Turkuensis. Ser. A, I. — 1971. — Vol. 148.

— Pp. 3-10.

25. Зиновьев, В. А. О совершенных кодах / В. А. Зиновьев, В. К. Леонтьев // Проблемы передачи информации. — 1972. — Т. 8, № 1. — С. 26-35.

26. Delsarte, P. Unrestricted codes with the Golay parameters are unique / P. Del-sarte, J. M. Goethals // Discrete Mathematics. — 1975. — Vol. 12. — P. 211-224.

27. Васильев, Ю. Л. О негрупповых плотно упакованных кодах / Ю. Л. Васильев // Проблемы кибернетики. — 1962. — Т. 8. — С. 337-339.

28. Mollard, M. A generalized parity function and its use in the construction of perfect codes / M. Mollard // SIAM J. Algebraic Discrete Methods. — 1986.

— Vol. 7, no. 1. — P. 113-115.

29. Heden, O. A new construction of group and nongroup perfect codes / O. Heden // Information and Control. — 1977. — Vol. 34, no. 4. — P. 314-323.

30. Сольвьёва, Ф. И. О двоичных негрупповых кодах / Ф. И. Сольвьёва // Методы дискретного анализа в изучении булевых функций и графов. — 1981. — Т. 37. — С. 65-76.

31. Phelps, K. T. A combinatorial construction of perfect codes / K. T. Phelps // SIAM J. Algebraic and Discrete Methods. — 1983. — Vol. 4, no. 3. — P. 398-403.

32. Phelps, K. T. A general product construction for error-correcting codes / K. T. Phelps // SIAM J. Algebraic and Discrete Methods. — 1984. — Vol. 5, no. 2. — P. 224-228.

33. Кротов, Д. С. Комбинированная конструкция совершенных двоичных кодов / Д. С. Кротов // Проблемы передачи информации. — 2000. — Т. 36, № 4. — С. 74-79.

34. Heden, O. On the classification of perfect binary 1-error correcting codes / O. Heden // TRITA-MAT-2002-01, preprint, KTH, Stockholm. — 2002.

35. Ostergard, P. R. J. The perfect binary one-error-correcting codes of length 15: part I - classification / P. R. J. Ostergard, O. Pottonen // IEEE Transactions on Information Theory. — 2009. — Vol. 55, no. 10. — P. 4657-4660.

36. Avgustinovich, S. V. Construction of perfect binary codes by sequential translations of the ¿-components / S. V. Avgustinovich, F. I. Solov'eva // Proceedings of the Fifth International Workshop on Algebraic and Combinatorial Coding Theory, Sozopol, Bulgaria. — 1996. — P. 15-19.

37. Августинович, С. В. Построение совершенных бинарных кодов последовательными сдвигами а-компонент / С. В. Августинович, Ф. И. Соловьёва // Проблемы передачи информации. — 1997. — Т. 33, № 3. — С. 15-21.

38. Phelps, K. T. Switching equivalence classes of perfect codes / K. T. Phelps, M. LeVan // Designs, Codes and Cryptography. — 1999. — Vol. 16, no. 2. — P. 179-184.

39. Etzion, T. On perfect codes and tilings: problems and solutions / T. Etzion, A. Vardy // SIAM J. Discrete Math. — 1998. — Vol. 11, no. 2. — P. 205-223.

40. Etzion, T. Perfect binary codes: Constructions, properties and enumerataion / T. Etzion, A. Vardy // IEEE Transactions on Information Theory. — 1994. — Vol. 40, no. 3. — P. 754-763.

41. Phelps, K. T. Kernels of nonlinear Hamming codes / K. T. Phelps, M. LeVan // Designs, Codes and Cryptography. — 1995. — Vol. 6, no. 3. — P. 247-257.

42. Avgustinovich, S. V. On the ranks and kernel problem for perfect codes / S. V. Avgustinovich, F. I. Solov'eva, O. Heden // Problems of Information Transmission. — 2003. — Vol. 39, no. 4. — P. 341-345.

43. Heden, O. A full rank perfect code of length 31 / O. Heden // Designs, Codes and Cryptography. — 2006. — Vol. 38, no. 1. — P. 125-129.

44. Hergert, F. Algebraische Methoden fur Nichtlineare Codes: Ph.D. thesis / F. Hergert; Technischen Hochschule, Darmstadt. — Germany, 1985.

45. Августинович, С. В. О несистематических совершенных двоичных кодах / С. В. Августинович, Ф. И. Соловьёва // Проблемы передачи информации.

— 1996. — Т. 32, № 3. — С. 47-50.

46. Phelps, K. T. Nonsystematic perfect codes / K. T. Phelps, M. LeVan // SIAM Journal on Discrete Mathematics. — 1999. — Vol. 12, no. 1. — P. 27-34.

47. Малюгин, С. А. Несистематические совершенные двоичные коды / С. А. Малюгин // Дискретный анализ и исследования операций сер. 1.

— 2001. — Т. 8, № 1. — С. 55-76.

48. LeVan, M. Designs and codes: Ph.D. thesis / M. LeVan; Auburn University, Auburn. — AL, USA, 1995.

49. Phelps, K. T. Every finite group is the automorphism group of some perfect code / K. T. Phelps // Journal of Combinatorial Theory, series A. — 1986.

— Vol. 43, no. 1. — P. 45-51.

50. Avgustinovich, S. V. Perfect binary codes with trivial automorphism group / S. V. Avgustinovich, F. I. Solov'eva // Proceedings of the Information Theory Workshop, Killarney, Ireland. — 1998. — P. 114-115.

51. Malyugin, S. A. Perfect codes with trivial automorphism group / S. A. Malyu-gin // Proceedings of the International Workshop on Optimal Codes, Sozopol, Bulgaria. — 1998. — P. 163-167.

52. Solov'eva, F. I. On perfect binary codes / F. I. Solov'eva // Discrete Applied Mathematics. — 2008. — Vol. 156, no. 9. — P. 1488-1498.

53. Heden, O. A survey of perfect codes / O. Heden // Advances in Mathematics of Communications. — 2008. — Vol. 2, no. 2. — P. 223-247.

54. Соловьёва, Ф. И. Обзор по совершенным кодам / Ф. И. Соловьёва // Математические вопросы кибернетики. — 2013. — Т. 18. — С. 5-34.

55. Golomb, S. W. Rook domains, Latin squares, affine planes, and error-distributing codes / S. W. Golomb, E. C. Posner // IEEE Transactions on Information Theory. — 1964. — Vol. 10, no. 3. — P. 196-208.

56. Horton, J. D. — Some improved bounds on covering sets. — Master's thesis, York University, Canada, 1969.

57. Heden, O. A study on mixed perfect codes: Ph.D. thesis / O. Heden. — Stockholm, Sweden, 1977.

58. Roos, C. preprint / C. Roos // Delft, the Netherlands. — 1979.

59. Lenstra Jr., H. W. Two theorems of perfect codes / H. W. Lenstra Jr. // Discrete Mathematics. — 1972. — Vol. 3, no. 1-3. — P. 125-132.

60. Graver, J. E. The module structure of integral designs / J. E. Graver, W. B. Ju-rkat // Journal of Combinatorial Theory, Series A. — 1973. — Vol. 15, no. 1.

— P. 75-90.

61. Graham, R. L. On the structure of ¿-designs / R. L. Graham, S.-Y. R. Li, W.-C. W. Li // SIAM Journal on Algebraic Discrete Methods. — 1980. — Vol. 1, no. 1. — P. 8-14.

62. Frankl, P. Intersection theorems and mod p rank of inclusion matrices / P. Fran-kl // Journal of Combinatorial Theory, Series A. — 1990. — Vol. 54, no. 1. — P. 85-94.

63. Khosrovshahi, G. B. On the bases for trades / G. B. Khosrovshahi, C. H. Maysoori // Linear Algebra and its Applications. — 1995. — Vol. 226-228.

— P. 731-748.

64. Frankl, P. On the number of sets in a null ¿-design / P. Frankl, J. Pach // European Journal of Combinatorics. — 1983. — Vol. 4, no. 1. — P. 21-23.

65. Hwang, H. L. On (k,t)-trades and the contruction of BIB designs with repeated blocks / H. L. Hwang // Ph.D. dissertation, The University of Illinois at Chicago. — 1982.

66. Cho, S. Minimal null designs and a density theorem of posets / S. Cho // European Journal of Combinatorics. — 1998. — Vol. 19, no. 4. — P. 433-440.

67. Augot, D. Rank metric and Gabidulin codes in characteristic zero / D. Augot, P. Loidreu, G. Robert // Proceedings ISIT. — 2013. — P. 509-513.

68. de la Cruz, J. Algebraic structure of MRD codes / J. de la Cruz, M. Kiermaier, A. Wasserman, W. Willems // Advances in Mathematics of Communications.

— 2016. — Vol. 10. — P. 499-510.

69. Ravagnani, A. Rank-metric code and their duality theory / A. Ravagnani // Designs, Codes and Cryptography. — 2016. — Vol. 80. — P. 197-216.

70. Gabidulin, E. M. Ideals over a noncommutative ring and their application in cryptology / E. M. Gabidulin, A. V. Paramonov, O. V. Tretjakov // Advances in cryptology, EUROCRYPT'91, Lecture Notes in Computer Science. — 1991.

— Vol. 547. — P. 482-489.

71. Silva, D. Universal secure network coding via rank-metric codes / D. Silva, F. R. Kschischang // IEEE Transactions on Information Theory. — 2011. — Vol. 57, no. 2. — P. 1124-1135.

72. Tarokh, V. Space-time codes for high data rate wireless communication: performance criterion and code construction / V. Tarokh, N. Seshadri, A. R. Calder-bank // IEEE Transactions on Information Theory. — 1998. — Vol. 44, no. 2.

— P. 744-765.

73. Gabidulin, E. M. Rank errors and rank erasures correction / E. M. Gabidulin, A. V. Paramonov, O. V. Tretjakov // Proceedings of the 4th International Colloquium on Coding Theory, Dilijan, Armenia, Yerevan. — 1992. — P. 11-19.

74. Kotter, R. Coding for errors and erasures in random network coding / R. Kotter, F. Kschischang // IEEE Transactions on Information Theory. — 2008. — Vol. 54, no. 8. — P. 3579-3591.

75. Silva, D. A rank-metric approach to error control in random network coding / D. Silva, F. Kschischang, R. Kotter // IEEE Transactions on Information Theory. — 2008. — Vol. 54, no. 9. — P. 3951-3967.

76. Delsarte, Ph. Bilinear forms over a finite field, with applications to coding theory / Ph. Delsarte // Journal of Combinatorial Theory, Series A. — 1978.

— Vol. 25, no. 3. — P. 226-241.

77. Габидулин, Э. М. Теория кодов с максимальным ранговым расстоянием / Э. М. Габидулин // Проблемы передачи информации. — 1985. — Т. 21, № 1. — С. 3-16.

78. Kshevetskiy, A. The new construction of rank codes / A. Kshevetskiy, E. M. Gabidulin // Proceedings, International Symposium on Information Theory. — 2005. — P. 2105-2108.

79. Sheekey, J. A new family of linear maximum rank distance codes / J. Sheekey // Advances in Mathematics of Communications. — 2016. — Vol. 10. — P. 475-488.

80. Lunardon, G. Generalized twisted Gabidulin codes / G. Lunardon, R. Trom-betti, Y. Zhou // Journal of Combinatorial Theory, Series A. — 2018. — Vol. 159. — P. 79-106.

81. Durante, N. Non-linear maximum rank distance codes in the cyclic model for the field reduction of finite geometries / N. Durante, A. Siciliano // The Electronic Journal of Combinatorics. — 2017. — Vol. 24, no. 2. — P. 2.33.

82. Кротов, Д. С. Трейды в комбинаторных конфигурациях / Д. С. Кротов // Материалы XII международного семинара "Дискретная математика и её приложения", Москва, 20-25 июня. — 2016. — С. 84-96.

83. Potapov, V. N. On perfect 2-colorings of the g-ary n-cube / V. N. Potapov // Discrete Mathematics. — 2012. — Vol. 312, no. 6. — P. 1269-1272.

84. Воробьёв, К. В. Оценки мощности минимального 1-совершенного битрейда в графе Хэмминга / К. В. Воробьёв, Д. С. Кротов // Дискретный анализ и исследование операций. — 2014. — Т. 21, № 6. — С. 3-10.

85. Vorob'ev, K. V. Bounds for the size of a minimal 1-perfect bitrade in a Hamming graph / K. V. Vorob'ev, D. S. Krotov // Journal of Applied and Industrial Mathematics. — 2015. — Vol. 9, no. 1. — P. 141-146.

86. Valyuzhenich, A.A. Minimum supports of eigenfunctions of Hamming graphs / A. A. Valyuzhenich // Discrete Mathematics. — 2017. — Vol. 340, no. 5. — P. 1064-1068.

87. Valyuzhenich, A. Minimum supports of functions on the Hamming graphs with spectral constraints / A. Valyuzhenich, K. Vorob'ev // Discrete Mathematics.

— 2019. — Vol. 342, no. 5. — P. 1351-1360.

88. Vorob'ev, K. Minimum supports of eigenfunctions of Johnson graphs / K. Vorob'ev, I. Mogilnykh, A. Valyuzhenich // Discrete Mathematics. — 2018.

— Vol. 341, no. 8. — P. 2151-2158.

89. Goryainov, S. On eigenfunctions and maximal cliques of Paley graphs of square order / S. Goryainov, V. V. Kabanov, L. Shalaginov, A. Valyuzhenich // Finite Fields and Their Applications. — 2018. — Vol. 52. — P. 361-369.

90. Bespalov, E. A. On the minumum supports of some eigenfunctions in the Doob graphs / E. A. Bespalov // Siberian Electronic Mathematical Reports. — 2018.

— Vol. 15. — P. 258-266.

91. James, G. D. Representations of general linear groups / G. D. James. — LMS Lecture Note Series 94, Cambridge University Press, 1984. — 147 p.

92. Cho, S. On the support size of null designs of finite ranked posets / S. Cho // Combinatorica. — 1999. — Vol. 19, no. 4. — P. 589-595.

93. Krotov, D. S. To the theory of g-ary Steiner and other-type trades / D. S. Kro-tov, I. Yu. Mogilnykh, V. N. Potapov // Discrete Mathematics. — 2016. — Vol. 339, no. 3. — P. 1150-1157.

94. Avgustinovich, S. V. Embedding in a perfect code / S. V. Avgustinovich, D. S. Krotov // Journal of Combinatorial Designs. — 2009. — Vol. 17, no. 5.

— P. 419-423.

95. Романов, А. М. О допустимых семействах компонент кода Хэмминга / А. М. Романов // Дискретный анализ и исследование операций. — 2012.

— Т. 19, № 2. — С. 84-91.

96. Романов, А. М. О вложении равновесных кодов в совершенные коды / А. М. Романов // Дискретный анализ и исследование операций. — 2016.

— Т. 23, № 4. — С. 26-34.

97. Krotov, D. S. Embedding in g-ary 1-perfect codes and partitions / D. S. Krotov, E. V. Sotnikova // Discrete Mathematics. — 2015. — Vol. 338, no. 11. — P. 1856-1859.

98. Sotnikova, E. V. Eigenfunctions supports of minimum cardinality in cubical distance-regular graphs / E. V. Sotnikova // Siberian Electronic Mathematical Reports. — 2018. — Vol. 15. — P. 223-245.

99. Sotnikova, E. V. Minimum supports of eigenfunctions in bilinear forms graphs / E. V. Sotnikova // Siberian Electronic Mathematical Reports. — 2019. — Vol. 16. — P. 501-515.

100. Сотникова, Е. В. Собственные функции с минимальным носителем дистанционно регулярных графов степени к = 3 / Е. В. Сотникова // Материалы X молодежной школы по дискретной математике и ее приложениям, Москва, 6-8 октября. — 2015. — С. 65-68.

101. Sotnikova, E. V. The eigenfunctions with the minimum support of the cubic distance-regular graphs / E. V. Sotnikova // Abstracts of the International Conference and PhD Summer School Groups and Graphs, Algorithms and Automata, Yekaterinburg, Russia, August, 9-15. — 2015. — P. 89-89.

102. Sotnikova, E. V. Minimum supports of eigenfunctions in bilinear forms graphs / E. V. Sotnikova // Abstracts of the International Conference and PhD Summer School Graphs and Groups, Representations and Relations, Novosibirsk, Russia, August, 6-19. — 2018. — P. 81-81.

103. Biggs, N. L. Cubic distance-regular graphs / N. L. Biggs, A. G. Boshier, J. Shawe-Taylor // Journal of the London Mathematical Society. — 1986.

— Vol. 33, no. 3. — P. 385-394.

104. Cvetkovic, D. Eigenspaces of graphs / D. Cvetkovic, P. Rowlinson, S. Simic.

— Cambridge University Press, 1997. — 258 p.

105. Weichsel, P. M. The Kronecker product of graphs / P. M. Weichsel // Proceedings of the American Mathematical Society. — 1962. — Vol. 13, no. 1. — P. 47-52.

106. Horn, R. A. Topics in Matrix Analysis / R. A. Horn, C. R. Johnson. — Cambridge University Press, 1991. — 607 p.

107. Krotov, D. S. On weight distributions of perfect colorings and completely regular codes / D. S. Krotov // Designs, Codes and Cryptography. — 2011. — Vol. 61, no. 3. — P. 315-329.

108. Information System on Graph Classes and their Inclusions [электронный ресурс]. — http://www.graphclasses.org/smallgraphs.html, Доступ: 31.05.2019.

109. Imrich, W. Multiple Kronecker covering graphs / W. Imrich, T. Pisanski // European Journal of Combinatorics. — 2008. — Vol. 29, no. 5. — P. 1116-1122.

110. Brouwer, A. E. Distance-regular graphs / A. E. Brouwer, A. M. Cohen, A. Neu-maier. — Springer-Verlag Berlin Heidelberg, 1989. — 495 p.

111. Hoffman, A. J. On eigenvalues and colourings of graphs / A. J. Hoffman. — in: B. Harris (Ed.), Graph Theory and Its Applications, Acad. Press, New York, 1970. — Vol. 33. — P. 79-91.

112. Bang, S. Delsarte clique graphs / S. Bang, A. Hiraki, J. H. Koolen // European Journal of Combinatorics. — 2007. — Vol. 28, no. 2. — P. 501-516.

113. Cho, S. Minimal null designs of subspace lattice over finite fields / S. Cho // Linear algebra and its applications. — 1998. — Vol. 282, no. 1-3. — P. 199-220.

114. Chevalley, C. Demonstration d'une hypothese de M. Artin / C. Chevalley // Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (in French). — 1935. — Vol. 11. — Pp. 73-75.

115. Elman, R. The algebraic and geometric theory of quadratic forms / R. Elman, N. Karpenko, A. Merkurjev. — American Mathematical Society, 2008. — 435 p.

116. Phelps, K. T. Ranks of g-ary 1-perfect codes / K. T. Phelps, M. Villanueva // Designs, Codes and Cryptography. — 2002. — Vol. 27, no. 1-2. — P. 139-144.