Исследование спектральных свойств транспозиционного графа тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Кравчук Артём Витальевич

• Кравчук Артём Витальевич
• кандидат наук
• 2026

Оглавление диссертации кандидат наук Кравчук Артём Витальевич

Введение

Глава 1. Предварительные сведения

1.1 Основные понятия

1.1.1 Симметрическая группа Бушп

1.1.2 Спектр графа

1.2 Графы Кэли и свойства Тп

1.2.1 Графы Кэли

1.2.2 Основные свойства транспозиционного графа Тп

1.3 Получение спектра Тп

1.3.1 Разбиения и таблицы Юнга

1.3.2 Регулярное представление Бушп

1.3.3 Элементы Юциса-Мёрфи и спектр Тп

1.3.4 Характеры представлений и спектр транспозиционного графа Тп

1.4 Выводы

Глава 2. Собственные значения Тп в окрестности нуля

2.1 Отсутствие разрывов в спектре Тп около нуля

2.2 Отрезок [-п—4, П-4]

2.2.1 Доказательство Теоремы

2.2.2 Доказательство технических лемм

2.3 Выводы

Глава 3. Квадратичный отрезок в спектре Тп

3.1 Отрезок [—п,п]

3.1.1 Доказательство теоремы

3.1.2 Доказательство технических лемм

3.1.3 Уточнение границ

3.2 Квадратичный отрезок

3.3 Выводы

Глава 4. Кратности собственных значений

4.1 Кратности наибольших собственных значений

4.1.1 Третье наибольшее собственное значение

4.1.2 Четвёртое наибольшее собственное значение

4.1.3 Пятое наибольшее собственное значение

4.1.4 Выводы

Глава 5. Численные результаты

5.1 Собственные значения и кратности Тп при небольших п

5.2 Доля собственных чисел в отрезке [— (П), (П)] и энергия Тп

5.3 Количество разбиений, соответствующих наименьшим по модулю собственным значениям

5.4 Выводы

Заключение

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

Публикации автора по теме диссертации

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

Введение

В диссертационной работе выполнено исследование спектральных свойств транспозиционного графа Кэли Тп.

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

Впервые понятие графа Кэли было введено выдающимся английским математиком А. Кэли в 1878 году. Граф Кэли используется для представления конечной группы относительно выбранного порождающего множества. Вершины графа соответствуют элементам группы, а рёбра соединяют вершины в соответствии с операцией группы, используя элементы порождающего множества. Другими словами, из одной вершины проводится ребро к другой вершине, если между ними можно перейти, применив один элемент из порождающего множества. В последние годы теория графов Кэли развивается как отдельная ветвь в алгебраической теории графов. Сейчас графы Кэли применяются как в классических задачах теории графов, так и в прикладных.

Транспозиционный граф Тп определяется как граф Кэли на симметрической группе Бушп относительно порождающего множества всех транспозиций {(%%]) Е Бушп, 1 ^ % < ] ^ п}. Транспозиционный граф Тп состоит из п! вершин и пп—">пп рёбер. Этот граф является связным и регулярным степени п(п——1). Также транспозиционный граф является двудольным.

В параллельных и распределённых вычислениях топологию сети можно смоделировать при помощи графа, где вершины являются вычислительными элементами (вычислителями), а рёбра являются каналами связи между ними. Транспозиционный граф часто рассматривается в контексте параллельных или распределённых вычислений [1], поскольку обладает рядом привлекательных свойств для проектирования таких систем, о которых мы поговорим ниже.

Для моделирования параллельных вычислений важен небольшой диаметр транспозиционного графа Тп, который равен п — 1 и является сублогарифмическим относительно числа вершин и рёбер, п! и п(п—1^п- соответственно. Также, то что транспозиционный граф Тп имеет высокую

п(п—1)

связность и является -Ч^—-—связным, повышает устойчивость к отказу отдельных вычислителей.

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

Лемма 1. [2, Лемма 1] Транспозиционный граф Тп,п ^ 2 может быть разбит на п непересекающихся подграфов Г1,..., Гп таким образом, что каждый подграф Г изоморфен Тп—1. Более того, для любых %,] = 1,2,... ,п при % = ] каждая вершина из Г связана ровно с одной вершиной из Г.

Известен следующий результат о гамильтоновости графов Кэли, у которых порождающее множество представлено транспозициями.

Теорема 1. [3; 4] Если порождающее множество Б состоит из транспозиций, то граф Кэли Сау(Бушп,Б) является гамильтоновым.

Однако, в контексте распределённых вычислений для транспозиционного графа Тп интересным является скорее не вопрос наличия га-мильтонового цикла, а наличия рёберно-непересекающихся гамильтоновых

циклов. Реберно-непересекающиеся гамильтоновы циклы важны в топологиях сетей, поскольку они повышают отказоустойчивость и улучшают распределение трафика сообщений по сети. Потому что если из строя вышло какое-то соединение, то всё ещё возможно гарантированно передать информацию из одного вычислителя в другой. До относительно недавнего времени о рёберно-непересекающихся гамильтоновых циклах в транспозиционном графе Тп было известно немного, пока в [5] не была представлена конструкция из четырёх рёберно-непересекающихся циклов в Т5 и было показано, как индуктивно получать рёберно-непересекающиеся гамильтоновы циклы в Тп+1 исходя из циклов Тп. Таким образом, было показано, что при п ^ 5 в транспозиционном графе Тп существует как минимум четыре рёберно-непересекающихся гамильтоновых цикла. Важной частью доказательства индуктивного перехода является как раз иерархическая структура транспозиционного графа, то есть Лемма 1. Затем, используя предыдущие результаты, в работе [6] было показано, что при п ^ 5 в транспозиционном графе Тп существует как минимум п — 1 рёберно-непересекающийся гамильтонов цикл.

В распределённых вычислительных сетях из строя могут выходить не только соединения, а также сами вычислители, поэтому интересной также является задача нахождения вершинно-непересекающихся путей. Эта задача формулируется следующим образом: пусть дана стартовая вершина в, а также множество конечных вершин О = ... , dk}, в ф О, в к—связном графе О. Необходимо найти к путей от в до di, которые не имеют общих вершин кроме стартовой вершины в. Если удастся найти эти к путей, то будет получена следующая устойчивость к сбоям: по меньшей мере один путь сохранится при выходе из строя к — 1 компонент. Эта задача, например, решается при помощи метода максимального потока, который требует полиномиального времени от количества вершин графа [7]. Так как количество вершин в транспозиционном графе Тп равно п!, то на практике этот метод практически невозможно применить и ведутся исследования алгоритмов, которые работали бы за полиномиальное время не от количества вершин, п!, а от числа п. Помимо транспозиционного графа Тп, эта задача была решена для гиперкуба Нп, Star-графа Бп и ротаторного графа Оп [8—10]. Для транспозиционного графа Тп в [11] был получен алгоритм, для которого верна следующая теорема:

Теорема 2. [11, Теорема 1] Для транспозиционного графа Tn, n^n——l"> путей, которые строятся при помощи алгоритма, не пересекаются по вершинам кроме стартовой вершины в. Временная сложность алгоритма равняется O(n7), а максимальная длина для каждого пути равняется 3п — 5.

Также в контексте распределённых и параллельных вычислений часто возникает вопрос об оценке бисекционной ширины (bisection width) графа. Бисекционная ширина может использоваться при оценке времени, необходимого для выполнения вычислений на машине, смоделированной данным графом [12]. В общем случае задача определения бисекционной ширины графа является NP—трудной. Однако, в работе [2] было получено точное значение бисекционной ширины в транспозиционном графе Tn при чётных n и довольно точная оценка для нечётных n.

Теорема 3. [2, Теорема 2] Для n ^ 2 бисекционная ширина транспозиционного графа Tn равна в случае чётных п и лежит между Пт и Пр(1 + n — 2) в случае нечётных п.

Примечательно, что для доказательства Теоремы 3, помимо иерархической структуры транспозиционного графа, авторами используются спектральные свойства транспозиционного графа и доказываются результаты про второе наибольшее собственное значение. Помимо этого стоит отметить, что параллельно и независимо от работы [2], бисекционная ширина транспозиционного графа исследовалась в работе [13].

Также интересным для изучения является изопериметрическое число (константа Чигера):

\E (V'V-V')\, , IVI

i(r) = -- : V — V, 0 < |V'| < u

где E(V',V — V' ) обозначает множество рёбер, у которых одна вершина лежит в множестве вершин V, а вторая вершина лежит в множестве V — V . Изопериметрическое число отражает, есть ли в графе узкое место и может использоваться при создании сильно связанных распределённых сетей. Графы с большим изопериметрическим числом обычно имеют быстрый рост и могут быть использованы для явного построения графов-экспандеров и графов-суперконцентраторов. Нахождение изопериметрического числа это

вычислительно сложная задача [12; 14; 15]. Однако, в [2] было получено точное значение константы Чигера транспозиционного графа Тп для чётного п и довольно точная оценка для нечётного п.

Теорема 4. [2, Теорема 3] Для п ^ 2 изопериметрическое число транспозиционного графа Тп равно | в случае чётного п и находится между | и п(1 + п — п?) в случае нечётного п.

Более того, используя данные оценки для г(Тп) и результаты из работы [12], выводится, что вычислительная сеть, моделируемая транспозиционным графом Тп, может симулировать любую вычислительную сеть с ограниченной степенью, имеющую не более п! вершин, с замедлением порядка O(log п) [2].

Также важной в теории кодирования является задача восстановления неизвестной вершины х £ V из минимального числа вершин в метрическом шаре Вг (х) радиуса г с центром в вершшине х. Решение этой задачи сводится к нахождению следующего значения:

N (Г, г) = тахХу е у (г),х=у Вг (х) П Вг (у )|.

N (Г, г) + 1 является наименьшим числом различных вершин в шаре Вг (х) вокруг неизвестной вершины х, достаточное для восстановления х при условии, что произошло не более г единичных ошибок. Поиск N (Г, г) гораздо сложнее для графов, которые не являются дистанционно-регулярными, однако в [16] значение было найдено в том числе и для транспозиционного графа.

Теорема 5. [16]

N(Тп, 1) = 1, N(Тп, 2) = §(п — 2)(п + 1) для всех п ^ 3.

Исследования других свойств, связанных с эффективным восстановлением вершин в транспозиционном графе Тп можно найти, например, в работе [17]. Причём интересно отметить, что в [17] авторы отмечают, что транспозиционный граф возникает в связи с анализом транспозиционных мутаций в молекулярной биологии [18].

Собственным значением графа Г будем называть собственное значение его матрицы смежности.

Спектром графа Г называется набор его различных собственных значений Ai < Л2 < • • • < Ak вместе с их кратностями mul(A1),mul(A2),... ,mul(Ak):

Spec(r) = [Amul{Al\ ..., AmuliAk]}.

Граф называется целочисленным (integral), если все его собственные значения являются целыми числами [19]. Впервые задача характеризации целочисленных графов была поставлена Ф. Харари и А. Швенком в 1974 году [20]. На данный момент характеризация целочисленных графов является открытой задачей. Для некоторых классов графов данная задача является решённой, например, известно, что для 3-регулярных (кубических) графов имеется только 13 неизоморфных целочисленных связных графов [21]. Но, например, характеризация k—регулярных графов для произвольного k уже является открытой задачей. Стоит отметить, что задача характеризации целочисленных графов интересна тем, что с одной стороны, целочисленных графов существует бесконечное количество, более того, для любого целого n > 0 существует целочисленный граф на n вершинах (это следует, например, из целочисленности полного графа Kn). Но с другой стороны, в 2009 году О. Ахмади, Н. Алоном, Ф. Блейком и И. Шпарлински в работе [22] было показано, что для большого количества вершин целочисленный граф является очень маловероятным объектом: доля целочисленных графов среди всех помеченных графов на n вершинах не превышает 2—зш.

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

Нахождение спектров графов Кэли над симметрической группой оказываются тесно связаны с теорией представления симметрической группы Symn [23], а через неё — с разбиением числа n, а также комбинаторикой и геометрией диаграмм Юнга.

Теория представления конечных групп служит удобным инструментом для анализа спектральных свойств графов Кэли над конечными группами [24; 25] и над симметрической группой в частности [26—28]. Подробнее про связь теории представлений симметрической группы Symn и

спектра транспозиционного графа Tn рассказывается в Главе 1. Спектр графа Кэли может быть рассмотрен через его матрицу смежности. Для конечной группы матрица смежности графа всегда диагонализуема, однако в случае симметрической группы способ в явном виде построить эту диа-гонализацию тесно связан с разложением регулярного представления этой группы в прямую сумму неприводимых представлений. В случае симметрической группы Symn все её неприводимые представления индексируются разбиениями числа n, или, что эквивалентно, диаграммами Юнга. Выражение для спектра графов Кэли над симметрической группой можно получить, используя характеры регулярных представлений [24] симметрической группы, однако для некоторых графов бывает удобно получить эквивалентное выражение, используя теорию элементов Юциса-Мёрфи. Элементы Юциса-Мёрфи — это семейство коммутирующих элементов в групповой алгебры C[Symn]. Они были представлены независимо А. Юци-сом в 1966 году [29] и Г. Мёрфи в 1981 году [30]. Подробнее о свойствах этих элементов мы рассказываем в Главе 1. Элементы Юциса-Мёрфи играют важную роль в изучении теории представлений симметрических групп [31] и находят разнообразные приложения. Помимо получения значений собственных чисел Star-графа в работе [32], элементы Юциса-Мёрфи также использовались для изучения спектральных свойств этого графа в работах [33; 34].

Перейдём к более конкретным примерам спектров графов Кэли над симметрической группой. Например, в работе [35] Д. Фридман показал, что если Tr'n С Symn есть множество из n — 1 транспозиции и Tr'n = Trn = {(1,2), (1,3),..., (1,n)}, то граф Кэли Cay(Symn,Tr'n) не будет целочисленным. Транспозиционный граф Кэли на симметрической группе Symn относительно порождающего множества Trn называется Star—графом, Sn и его спектральные свойства были изучены в различных работах. Например, в 2009 году А. Абдоллахи и Е.Ватандуст выдвинули гипотезу [19], показав её численно для n ^ 6, что спектр Star—графа является целочисленным и содержит все целые числа от — (n — 1) до n — 1, с небольшим исключением, что при n ^ 3, число 0 не входит в спектр Sn. Эта гипотеза была доказана Р. Краковски и Б. Мохаром в 2012 году в работе [36] при помощи комбинации комбинаторных методов и результатов о собственных значениях Шрейеровских косетных графов, а также свойств подграфов,

изоморфных частичным графам перестановок. Стоит отметить, что независимо и в том же, 2012 году, гипотеза А. Абдоллахи и Е.Ватандуста была подтверждена Г. Шапюи и В. Фере в работе [32], но уже используя теорию элементов Юциса-Мёрфи. Исследование кратностей собственных значений Star—графа можно найти, например, в работах [37; 38]. В качестве примера рассмотрим также граф Кэли на симметрической группе, про который известно, что он не является целочисленным.

Pancake граф, Pn = Cay(Symn, PR),n ^ 2, определяется на симметрической группе Symn относительно порождающего множества всех префикс-реверсалов PR = {ri <Е Symn, i <Е {2,... ,n}}, где ri меняет порядок элементов внутри отрезка [1, i]. Данный граф не является целочисленным, например, Spec(PA) = {э1,25,( —^^)3,05,( )3, — 14, — 23} [39]. В 2020 году К. Дальфо и М. Фиоль показали [39], что в спектре этого графа находятся все целые числа из отрезка [—1,n — 1], за исключением числа Ln——2\. Примечательно, что для доказательства этого факта авторы явно исследовали матрицу смежности, а также получили явные выражения для собственных векторов, соответствующих этому набору собственных чисел. Также в этой работе было показано, что кратность собственного значения — 1 не меньше, чем n — 1 .

Перейдём теперь к рассмотрению спектра транспозиционного графа Tn. К.Калпакис и Я.Йеша в работе [2, Лемма 3] показали, что транспозиционный граф Tn является целочисленным для всех n. Позже и независимо целочисленность транспозиционного графа была показана Е. Константиновой и Д. Лыткиной [40, Теорема 2].

Матрицей Лапласа L графа Г называется матрица L = D — A, где A является матрицей смежности графа Г, а D— диагональная матрица, у которой на диагонали стоят степени вершин графа G. Известно следующее утверждение:

Утверждение 1. [41, Утверждение 2.1] Пусть Г = (V,E) граф с n вершинами. Пусть Л2 и An это второе наименьшее и наибольшее собственные значения матрицы Лапласа соответственно. Тогда A ^ ^ n для

любого непустого собственного подмножества X с V.

Например, в работе [2] при помощи этого утверждения была получена оценка на бисекционную ширину транспозиционного графа.

Если граф Г является k—регулярным, то Л2 = k — п2, где п2—второе наибольшее собственное значение графа Г. Л2 также называют алгебраической связностью графа Г. Это значение больше нуля тогда и только тогда, когда граф Г является связным.

Хорошо известна следующая оценка на изопериметрическое число k-регулярного графа через его второе по величине собственное значение [42—44]:

^—Р2 ^ г(Г) ^ y/2k(k — П2)

Поэтому довольно важным является вопрос нахождения второго по величине собственного числа графа [45—47].

Для транспозиционного графа Tn наибольшее собственное значение

n(n—1) -1

равно -Ч^—- с кратностью 1, что прямо следует из регулярности данного графа. Второе по величине собственное значение равно n(n——3) с кратностью (n — 1)2 [2, Лемма 3].

Также при анализе спектральных свойств возникает вопрос определения энергии графа, которая определяется следующим образом:

E (Г)= £ |п|,

n^Spec(r)

где суммирование идёт по всем собственным значениям графа без учёта кратности. Для транспозиционного графа Tn точное выражения для энергии неизвестно. Известна верхняя оценка, которая берётся из наибольшего собственного значения, умноженного на количество вершин графа [48, Теорема 1]:

E(Tn) < n!(n — 1)n.

Спектр транспозиционного графа Кэли Tn может быть выведен с использованием методов теории представления симметрической группы Symn, и выражен через разбиения числа n при помощи следующей теоремы.

Теорема 6. Спектр транспозиционного графа Tn состоит из целых чисел, соответствующих разбиениям Л Ь n и только из них. Каждое разбиение Л Ь n соответствует собственному значению пЛ по следующему выражению:

п ^ пз(пз - 21 + 1)

Пл = ^-2-

з=1

с кратностью тп1 (цл) = ^ где Л = {щ,... ), а ¡л равно размер-

=Пл

ности неприводимого представления, соответствующего разбиению Л.

Подробнее о данной теореме мы поговорим в Главе 1. Таким образом, если перечислить все разбиения числа п и подставить их в выражение из Теоремы 6, то можно получить все собственные значения графа Тп. Обозначение /(п) ~ д{п) означает, что отношение ^^ стремится к 1 при п ^ сю. Количество разбиений числа р(п) асимптотически ведёт себя следующим образом:

ехр Ы^/й"-]})) р(п)--¡пт-

(см. [49]). Для больших значений п количество разбиений растёт экспоненциально, вследствие чего становится практически невозможным их явное перечисление и полный перебор всех возможных вариантов. При этом, взглянув на выражение для собственных чисел в Теореме 6, сложно ответить на довольно просто поставленные вопросы относительно спектра транспозиционного графа Тп, например, на вопросы ниже.

— Лежит ли 0 в спектре транспозиционного графа Тп?

— Лежит ли 1 в спектре транспозиционного графа Тп?

— Лежат ли все целые числа из отрезка [0,п] в спектре транспозиционного графа Тп?

— Из того, что наибольшее собственное значение транспозиционного графа Тп равно (п) следует, что все собственные значения Тп лежат в отрезке [— (2), (2) ]. Но сколько уникальных собственных чисел в зависимости от п? Их количество линейно, квадратично или имеет другую асимптотику относительно п?

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

Объектом исследования в данной работе является транспозиционный граф Кэли Тп.

Задачи исследования. В настоящей работе проводится исследование транспозиционного графа Кэли Tn. В частности, были поставлены следующие задачи:

1. Изучить связь спектра транспозиционного графа Tn с разбиениями числа n и теорией представлений симметрической группы, в частности, с использованием элементов Юциса-Мёрфи.

2. Установить наличие отрезков, все целые числа из которых лежат в спектре Tn и изучить распределение собственных значений Tn в окрестности нуля.

3. Исследовать, как количество различных собственных чисел транспозиционного графа Tn зависит от n (линейно, квадратично или иным образом) и установить асимптотические оценки для этой зависимости.

4. Ответить на вопрос, существует ли отрезок квадратичной относительно n длины, все целые числа из которого лежат в спектре Tn.

5. Вывести явные выражения для первых нескольких наибольших по модулю наибольших собственных чисел и установить соответствующие им кратности.

6. Провести вычислительные эксперименты для спектров транспозиционных графов Tn при малых значенях n.

Методология и методы исследования. При решении поставленных задач использовались методы теории графов, алгебраической теории графов, комбинаторики, спектральной теории графов и теории представлений конечных групп. Для численных экспериментов использовался язык программирования Python 3.

Положения, выносимые на защиту. В данной работе были получены следующие результаты.

1. Доказано, что для каждого k ^ 0 существует n(k) такое, что для любого n ^ n(k) и любого m <Е {0,..., k}, m <Е Spec(Tn) (Теорема 12).

2. Используя результат из предыдущего пункта, а также доказав ряд технических лемм, доказано, что все целые числа из отрезка [—n^4, n^4] лежат в спектре Tn (Теорема 13).

3. Доказано, что отрезок [—n,n] лежит в спектре транспозиционного графа Tn, используя результат из доказательства пункта 3, а также доказательства ряда новых технических лемм (Теорема 14).

4. Используя результат о том, что все целые числа из отрезка [—п,п] лежат в спектре транспозиционного графа Тп, а также доказав несколько новых технических лемм, было доказано, что все целые числа из отрезка квадратичной относительно п длины лежат в спектре транспозиционного графа Тп (Теорема 16).

5. Выводятся выражения для значений и кратностей некоторых наибольших собственных значений транспозиционного графа Тп (выражения для первого и второго наибольших собственных чисел вместе с кратностью были известны до этого), а именно:

а) третьего наибольшего (Теорема 18);

б) четвёртого наибольшего (Теорема 19);

в) пятого наибольшего (Теорема 20).

6. Получены численные результаты для спектров транспозиционного графа Тп при небольших значениях п.

Научная новизна. Все основные результаты, которые представлены в данной диссертации, являются новыми.

Теоретическая и практическая значимость. Данная работа носит теоретический характер. Исследование спектральных свойств транспозиционного графа Тп углубляет понимание алгебраической структуры графов Кэли, построенных на симметрической группе, и связывает методы теории представлений симметрических групп с алгебраической теорией графов. Это позволяет получить новые явные выражения для собственных значений и их кратностей через разбиения числа п. Выявление того, какие целые числа и с какими кратностями входят в спектр Тп, позволяет получить более полное представление о распределении собственных значений в графах, а также установить асимптотические оценки количества уникальных собственных чисел.

Степень достоверности и апробация работы. Основные результаты данной работы прошли процедуру рецензирования и опубликованы в международных журналах [57—59], а также были представлены на научных семинарах, школах, а также всероссийских и международных научных конференциях:

— Семинар «Теория графов» ИМ СО РАН (г. Новосибирск, 22 февраля 2022г.).

— Ural Seminar on Group Theory and Combinatorics (онлайн, 15 марта, 2022г.)

— The Sixth Workshop on Algebraic Graph Theory (онлайн, 21-25 марта, 2022г.).

— Вторая конференция Математических центров России (г.Москва, 711 ноября 2022г.).

— Международная конференция «Алгебра и динамические системы» (г. Нальчик, 28 июня-3 июля 2022г.).

— Международная (54-я всероссийская) молодёжная школа-конференция «Современные проблемы математики и её приложений» (г. Екатеринбург, 6-10 и 17 февраля 2023г.).

— Семинар «Теория графов» ИМ СО РАН (г. Новосибирск, 6 июня 2023г.).

— Международная конференция «Мальцевские чтения» (г. Новосибирск, 13-17 ноября 2023г.).

— Четвёртая конференция Математических центров России (г.Санкт-Петербург, 6-11 августа 2024г.).

— Международная конференция «Алгебра и математическая логика: теория и приложения» (г. Казань, 27 июня-1 июля 2024г.).

Личный вклад. По теме данной диссертации автором было опубликовано 10 работ. Из них 3 статьи в журналах из списка ВАК и Scopus [57—59]. Две работы выполнены в соавторстве с Константиновой Е.В. [57; 58] и одна работа выполнена без соавторов [59]. В совместных работах [57; 58] выбор направления и общее научное руководство, а также помощь в подготовке текста принадлежат Константиновой Е.В. Формулировки и доказательства всех новых теорем из работ [57; 58] принадлежат автору. Все выносимые на защиту результаты получены автором самостоятельно. Теоремы 12, 18, 19 опубликованы в работе [57], Теорема 13 опубликована в работе [58], Теоремы 14, 16 опубликованы в работе [59].

Список литературы диссертационного исследования кандидат наук Кравчук Артём Витальевич, 2026 год

/ / / /

\ / / / /

| / у

___— ______— - "

10 20 30 40 50 60

небольших(по модулю) собственных значений, используя результат Теоремы 9 выглядит неподъёмной задачей. Более реалистичным с точки зрения получения результатов выглядит направление получения асимптотик для кратностей этих собственных чисел.

5.4 Выводы

В данной главе был проведён численный анализ спектра транспозиционного графа Tn при малых значениях n (от 3 до 10). Было установлено, что среди собственных значений транспозиционного графа Tn при малых значениях n наибольшую кратность имеют собственные числа, близкие к нулю (в первую очередь, 0 и ±1). Однако, это неверно в общем случае и нарушается для графа Tig, в котором наибольшую кратность имеет собственное число 3.

Также было продемонстрировано, что доля покрытых собственными числами транспозиционного графа интервалов [— Q), Q) ] растёт с увеличением n и приближается к значению 0.7 уже при относительно небольших значениях n ~ 50, однако этот рост не является монотонным.

Помимо этого отдельное внимание было уделено сложности получения аналитических выражений для значений кратностей собственных чисел графа Tn. Было показано, что количество разбиений, соответствующих каждому собственному значению, растёт очень быстро. Для n = 60 среднее количество разбиений на одно собственное значение уже практически достигает 400, что сильно усложняет аналитический вывод кратностей.

Заключение

Основные результаты проведенного исследования заключаются в следующем:

1. Доказано, что для каждого к ^ 0 существует п(к) такое, что для любого п ^ п(к) и любого т Е {0,...,к}, т Е Брес(Тп), (Теорема 12).

2. Используя результат из предыдущего пункта, а также доказав ряд технических лемм, доказано, что все целые числа из отрезка [—, ] лежат в спектре Тп (Теорема 13).

3. Доказано, что отрезок [—п,п] лежит в спектре транспозиционного графа Тп, используя результат из доказательства пункта 3, а также доказательства ряда новых технических лемм (Теорема 15).

4. Используя результат о том, что все целые числа из отрезка [—п,п] лежат в спектре транспозиционного графа Тп, а также доказав несколько новых технических лемм, было показано, что все целые числа из отрезка квадратичной относительно п длины лежат в спектре транспозиционного графа Тп при достаточно больших значениях п (Теорема 16).

5. Получены выражения для значений и кратностей некоторых наибольших собственных значений транспозиционного графа Тп (выражения для первого и второго наибольших собственных чисел вместе с кратностью были известны до этого), а именно:

а) третьего наибольшего (Теорема 18);

б) четвёртого наибольшего (Теорема 19);

в) пятого наибольшего (Теорема 20).

6. Получены численные результаты и проведён анализ для спектров транспозиционного графа Тп при небольших значениях п (глава 5).

Таким образом, благодаря результатам работы, имеем следующую картину для правой части спектра Тп (Рис. 5.6):

1. известны пять наибольших собственных чисел Тп вместе с их крат-ностями;

2. известно, что все целые числа из отрезка [0,п] лежат в спектре Тп при п ^ 19;

3. известно, что все целые числа из отрезка с квадратичной относительно п длины [у1,у2] лежат в спектре Тп, где у1 = 32+1) — 2(|2п\ —

2п+1

л 2п+1к

1) и у2 = ( 2 ), при достаточно больших значениях п. • • • • • • • • •

111111111111111111-1||||||||||||||||||||||||||||||||||-• • • •—•->

О п У1 У2 ^

Рисунок 5.6 — Изученная часть спектра Тп (спектр симметричен относительно нуля).

Результаты работы открывают следующие вопросы и гипотезы, которые могут быть интересны для будущих исследований:

1. Все ли целые числа из отрезка [п + 1, у1 — 1] лежат в спектре транспозиционного графа Тп (гипотеза 1)?

2. Насколько может быть увеличено значение у2 для достаточно больших значений п?

3. Чему равны асимптотики кратностей для наименьших по модулю собственных значений Тп?

4. Чему равен предел отношения количества уникальных собственных чисел в спектре Тп к длине отрезка [— (п), (п) ]?

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

1. Heydemann M.-C. Cayley graphs and interconnection networks. — Dordrecht : Springer Netherlands, 1997. — P. 167—224.

2. Kalpakis K., Yesha Y. On the bisection width of the transposition network // Networks. — 1997. — Vol. 29. — P. 69—76.

3. P.J. Slater. Generating all permutations by graphical transpositions // Ars Combin. — 1978. — Vol. 5. — P. 219—225.

4. Компельмахер В. Л., Лисковец В. А. Последовательное порождение перестановок с помощью базиса транспозиции // Кибернетика. — 1975. — Vol. 3. — P. 17—21.

5. Hung R.-W. The property of edge-disjoint Hamiltonian cycles in transposition networks and hypercube-like networks // Discrete Applied Mathematics. — 2015. — Vol. 181. — P. 109—122.

6. Hussak W. Disjoint Hamilton cycles in transposition graphs // Discrete Applied Mathematics. — 2016. — Vol. 206. — P. 56—64.

7. Gross J., Yellen J. Graph theory and its applications (2nd ed.) — Chapman, Hall/CRC., 2005.

8. Gu Q.-P., Peng S. Node-to-set disjoint paths problem in star graphs // Information Processing Letters. — 1997. — Vol. 62, no. 4. — P. 201—207.

9. Corbett P. Rotator graphs: an efficient topology for point-to-point multiprocessor networks // IEEE Transactions on Parallel and Distributed Systems. - 1992. - Vol. 3, no. 5. - P. 622-626.

10. Rabin M. O. Efficient dispersal of information for security, load balancing, and fault tolerance //J. ACM. - New York, NY, USA, 1989. - Vol. 36, no. 2. — P. 335—348.

11. Suzuki Y., Kaneko K., Nakamori M. Node-Disjoint Paths Algorithm in a Transposition Graph // IEICE - Trans. Inf. Syst. — USA, 2006. — Vol. E89 D, no. 10. — P. 2600—2605.

12. Leighton T., Rao S. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms // [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science. — 1988. — P. 422—431.

13. Stacho L., Vrt'o I. Bisection width of transposition graphs // Discrete Applied Mathematics. — 1998. — Vol. 84, no. 1. — P. 221—235.

14. Mohar B. Isoperimetric numbers of graphs // Journal of Combinatorial Theory, Series B. — 1989. — Vol. 47, no. 3. — P. 274—291.

15. Mohar B., Poljak S. Eigenvalues in Combinatorial Optimization // Combinatorial and Graph-Theoretical Problems in Linear Algebra / ed. by R. A. Brualdi, S. Friedland, V. Klee. — New York, NY : Springer New York, 1993. — P. 107—151.

16. Konstantinova E., Levenshtein V., Siemons J. Reconstruction of permutations distorted by single transposition errors. — 2007. — URL: https: //arxiv.org/abs/math/0702191.

17. Levenshtein V. I., Siemons J. Error graphs and the reconstruction of elements in groups // J. Comb. Theory A. — 2009. — Vol. 116. — P. 795—815. — URL: https://api.semanticscholar.org/CorpusID:1456798.

18. Pevzner P. Computational Molecular Biology: An Algorithmic Approach. — 2000.

19. Abdollahi A., Vatandoost E. Which Cayley graphs are integral? // Electronic Journal of Combinatorics. — 2009. — Vol. 16, no. 1.

20. Harary F., Schwenk A. J. Which graphs have integral spectra? // Graphs and Combinatorics. — Berlin, Heidelberg : Springer Berlin Heidelberg, 1974. — P. 45—51.

21. Bussemaker F., Cvetkovic D. There are exactly 13 connected, cubic, integral graphs // Publikacije Elektrotehnickog Fakulteta = Publications de la Faculté d'Electrotechnique de l'Université à Belgrade. — 1976. — No. 544—576. — P. 43—48.

22. Graphs with integral spectrum / O. Ahmadi, N. Alon, I. F. Blake, I. E. Sh-parlinski // Linear Algebra and its Applications. — 2009. — Vol. 430, no. 1. — P. 547—552.

23. Sagan B. The Symmetric Group.Representations, Combinatorial Algorithms, and Symmetric Functions. — Springer, New York, 2001.

24. Zieschang P.-H. Cayley graphs of finite groups // Journal of Algebra. — 1988. — Vol. 118, no. 2. — P. 447—454.

25. Ghorbani M., Nowroozi F. On the spectrum of Cayley graphs related to the finite groups // Filomat. — 2017. — Jan. — Vol. 31. — P. 6419—6429.

26. Maleki R., Razafimahatratra A. S. On the Second Eigenvalue of Certain Cayley Graphs on the Symmetric Group // Bulletin of the Malaysian Mathematical Sciences Society. — 2023. — Vol. 46. — P. 158.

27. Li Y., Xia B., Zhou S. Aldous' spectral gap property for normal Cayley graphs on symmetric groups // European Journal of Combinatorics. — 2023. — Vol. 110. — P. 103657.

28. Khomyakova E., Konstantinova E. V. Catalogue of the Star graph eigenvalue multiplicities // Arabian Journal of Mathematics. — 2021. — Vol. 110. — P. 115—119.

29. Jucys A. Catalogue of the Star graph eigenvalue multiplicities // Lithuanian Journal of Physics. — 1966. — Vol. 6, no. 2. — P. 180—189.

30. Murphy G. A new construction of Young's seminormal representation of the symmetric groups // Journal of Algebra. — 1981. — Vol. 69, no. 2. — P. 287—297.

31. Vershik A., Okounkov A. A New Approach to the Representation Theory of the Symmetric Groups. II // Journal of Mathematical Sciences. — 2005. — Nov. — Vol. 131. — P. 5471—5494.

32. Chapuy G., Feray V. A note on a Cayley graph of S_n // arXiv preprint arXiv:1202.4976. — 2012. — Feb.

33. Pl-eigenfunctions of the Star graphs / S. Goryainov, V. Kabanov, E. Konstantinova, L. Shalaginov, A. Valyuzhenich // Linear Algebra and its Applications. — 2020. — Vol. 586. — P. 7—27.

34. The Star graph eigenfunctions with non-zero eigenvalues / V. V. Kabanov, E. V. Konstantinova, L. Shalaginov, A. Valyuzhenich // Linear Algebra and its Applications. — 2021. — Vol. 610. — P. 222—226.

35. Friedman J. On Cayley Graphs on the Symmetric Group Generated by Tranpositions // Combinatorica. — 2000. — Vol. 20. — P. 505—519.

36. Krakovski R., Mohar B. Spectrum of Cayley graphs on the symmetric group generated by transpositions // Linear Algebra and its Applications. — 2012. - Vol. 437, no. 3. - P. 1033-1039.

37. Avgustinovich S. V., Khomyakova E. N., Konstantinova E. V. Multiplicities of eigenvalues of the Star graph // Siberian Electronic Mathematical Reports. - 2016. - Vol. 13. - P. 1258-1270.

38. Khomyakova E. N., Konstantinova E. V. Note on exact values of multiplicities of eigenvalues of the star graph // Siberian Electronic Mathematical Reports. - 2015. - Vol. 12. - P. 92-100.

39. Dalfo C., Fiol M. Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups // Linear Algebra and its Applications. — 2020. — Vol. 597. — P. 94—112.

40. Konstantinova E., Lytkina D. Integral Cayley Graphs over Finite Groups // Algebra Colloquium. — 2020. — Mar. — Vol. 27. — P. 131—136.

41. Mohar B. Laplace eigenvalues of graphs—a survey // Discrete Mathematics. - 1992. - Vol. 109, no. 1. - P. 171-183.

42. Alon N. Eigenvalues and expanders // Combinatorica. — 1986. — Vol. 6, no. 2. — P. 83—96.

43. Alon N., Milman V. \1, Isoperimetric inequalities for graphs, and super-concentrators // Journal of Combinatorial Theory, Series B. — 1985. — Vol. 38, no. 1. - P. 73-88.

44. Dodziuk J. Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks // Transactions of the American Mathematical Society. - 1984. - Vol. 284, no. 2. - P. 787-794.

45. Li Y., Xia B., Zhou S. The second largest eigenvalue of normal Cayley graphs on symmetric groups generated by cycles // Journal of Combinatorial Theory, Series A. — 2024. — Vol. 206. — P. 105885.

46. Hoory S., Linial N., Wigderson A. Expander graphs and their applications // Bulletin of the Malaysian Mathematical Sciences Society. — 2006. — Vol. 43, no. 4. — P. 439—561.

47. Maleki R., Razafimahatratra A. S. On the Second Eigenvalue of Certain Cayley Graphs on the Symmetric Group // Bulletin of the Malaysian Mathematical Sciences Society. — 2023. — Vol. 46. — P. 158.

48. DeDeo M. R. On the Energy of Transposition Graphs // Combinatorics, Graph Theory and Computing. — 2022. — P. 305—316.

49. Hardy G. H., Ramanujan S. Asymptotic formulae in combinatory analysis // Proceedings of the London Mathematical Society. — 1918. — Vol. 2, no. 1. — P. 75—115. — (3rd ser.)

50. Biggs N. Algebraic Graph Theory. — Cambridge University Press, 1993. — (Cambridge Mathematical Library).

51. Konstantinova E. V. Lecture notes on Algebraic Graph Theory. — Novosibirsk State University, 2023. — P. 138. — URL: https://ekonsta.github. io/Slides/Lecture%20notes%20on%20Algebraic%20Graph%20Theory.pdf.

52. Frame J. S., Robinson G. d. B., Thrall R. M. The Hook Graphs of the Symmetric Group // Canadian Journal of Mathematics. — 1954. — Vol. 6. — P. 316—324.

53. Jucys A. Symmetric polynomials and the center of the symmetric group ring // Reports on Mathematical Physics. — 1974. — Vol. 5. — P. 107—112.

54. Murnaghan F. D. The Theory of Group Representations. — New York : Dover, 1938.

55. OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences, Sequence A000700. — Accessed: 2024-03-09. https://oeis.org/A000700.

56. P. Diaconis, M. Shahshahani. Generating a random permutation with random transpositions // Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete. - 1981. - Vol. 57. - P. 159-179.

Публикации автора по теме диссертации

57. Konstantinova E. V., Kravchuk A. Spectrum of the Transposition graph // Linear Algebra and its Applications. — 2022. — Vol. 654. — P. 379—389.

58. Konstantinova E. V., Kravchuk A. Distinct eigenvalues of the Transposition graph // Linear Algebra and its Applications. — 2024. — Vol. 690. — P. 132—141.

59. Kravchuk A. V. Constructing segments of quadratic length in Spec(Tn) through segments of linear length // Siberian Electronic Mathematical Reports. — 2024. — Vol. 21, no. 2. — P. 927—939.

60. Кравчук А. В. Спектр транспозиционного графа // Сборник тезисов «Второй конференции математических центров России». — Москва, Россия, 2022. — С. 11. — 7-11 ноября 2022, МГУ, МИАН.

61. Кравчук А. В. Построение отрезков квадратичной длины при помощи отрезков линейной длины в спектре транспозиционного графа // Материалы международной конференции «Алгебра и математическая логика: теория и приложения». — Казань, Россия, 2024. — С. 37. — посвящена 130-летию Н. Г. Чеботарева и 80-летию М. М. Арсланова.

62. Kravchuk A. Spectrum of the Transposition graph // The 6th Workshop on «Algebraic Graph Theory and its Applications», Book of abstracts. — Sino-Russia Mathematics Center Mathematical Center in Akademgorodok Three Gorges Mathematical Research Center, 2022. — P. 15.

63. Константинова Е. В., Кравчук А. В. О кратностях собственных значений транспозиционного графа // Сборник тезисов конференции «Алгебра и динамические системы». — Нальчик, Россия, 2022. — С. 68. — 28 июня - 3 июля 2022 г.

64. Кравчук А. В. Собственные значения транспозиционного графа // Сборник тезисов международной конференции «Мальцевские чтения». — Новосибирск, Россия, 2023. — С. 158. — 13-17 ноября 2023 г.

65. Кравчук А. В. Спектр транспозиционного графа Tn // Современные проблемы математики и ее приложений. Международная (54-я всероссийская) молодежная школа-конференция. — Екатеринбург, Россия, 2023. — С. 14. — 6-10 и 17 февраля 2023 г.

66. Кравчук А. Построение отрезков квадратичной длины при помощи отрезков линейной длины в спектре транспозиционного графа // Тезисы докладов IV Конференции математических центров России, посвященной 300-летию СПбГУ и РАН. — Санкт-Петербург, Россия : Санкт-Петербургский международный математический институт имени Леонарда Эйлера, 2024. — С. 22.