Аналитический подход к задачам перечисления графов со спектральными ограничениями

• Автор: Исаев, Михаил Исмаилович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 147 с.

ОГЛАВЛЕНИЕ
Введение

Глава 1. Некоторые задачи перечисления графов: проблемы и методы их решения

1.1. Проблемы алгоритмического решения задач перечисления

1.2. Эйлеровы ориентации

1.2.1. Постановка задачи

1.2.2. Приближенный вероятностный алгоритм

1.2.3. Случай полного графа. Представление в виде интеграла

1.3. Эйлеровы циклы

1.3.1. Постановка задачи. Случай полного графа

1.3.2. Ориентированные графы. Представление в виде интеграла

1.3.3. Вероятностные интерпретации
1.4. Подграфы с заданной последовательностью степеней вершин
1.4.1. Постановка задачи. Представление в виде интеграла
1.4.2. Случай полного графа
1.4.3. Случай произвольного графа. Наивная гипотеза
1.5. Общая схема доказательства основных результатов
Глава 2. Асимптотические оценки многомерных интегралов гауссовского типа
2.1. Интегралы гауссовского типа. Обозначения и предположения .
2.2. Матрицы с асимптотическим диагональным доминированием .
2.2.1. Свойства обратной матрицы

2.2.2. Определитель возмущенной матрицы
2.2.3. Главные миноры
2.3. Некоторые функции над полиномами
2.3.1. Высота и четная высота
2.3.2. Функция ха
2.4. Асимптотические оценки
2.4.1. Формулировка результатов
2.4.2. Вспомогательные утверждения. Основная лемма
2.4.3. Редукция полиномов
2.4.4. Доказательство асимптотических оценок
Глава 3. Графы со спектральными ограничениями
3.1. Класс графов с сильными перемешивающими свойствами
3.1.1. Перемешивающие свойства графов
3.1.2. Доказательство эквивалентности
3.1.3. Примеры
3.1.4. Пути и разрезы
3.1.5. Свойства матрицы Лапласа
3.2. Класс существенно недвудольных графов
3.2.1. Недвудольность и апериодичность
3.2.2. Примеры
3.2.3. Нечетные пути
3.2.4. Свойства беззнаковой матрицы Лапласа
3.3. Сильная перемешиваемость и существенная недвудольность случайного графа
3.4. Комбинаторный смысл миноров матрицы Лапласа и определителя ^-матрицы
Глава 4. Аналитический подход на примере некоторых задач перечисления графов

4.1. Эйлеровы ориентации
4.1.1. Асимптотическая формула
4.1.2. Основная часть интеграла
4.1.3. Оценка незначительных частей
4.2. Эйлеровы циклы
4.2.1. Асимптотическая формула
4.2.2. Приведение к интегралу гауссовского типа
4.2.3. Основная часть интеграла
4.2.4. Оценка незначительных частей
4.3. Подграфы с заданной последовательностью степеней вершин
4.3.1. Асимптотическая формула
4.3.2. Основная часть интеграла
4.3.3. Оценка незначительных частей
4.3.4. Наивная гипотеза
Заключение
Литература
Приложение А. Доказательство Леммы

Зафиксируем константы а, b > 0. Рассмотрим класс Л4а,ь, состоящий из матриц (всевозможных размеров) вида А = I + X, которые удовлетворяют:
А — положительно определенная симметрическая матрица,
’ а (2.4)
— g-ze = 0, ||A ||2 < b,
где size A — размер матрицы A, a I — единичная матрица размера size Л.
В §2.4 получены асимптотические оценки интегралов (2.1) для случая матриц А, принадлежащих классу М.а,ь• В качестве области fln используется многомерный куб ип(те), где г, е > 0 — фиксированные константы,
ип(р) = {веШп : |Йоо<р}.
Согласно (2.4), диагональные элементы матриц из класса Л4а,ь асимптотически доминируют над остальными элементами. Свойства таких матриц обсуждаются в §2.2 и существенно используются в Главах 3, 4.
Чтобы сформулировать предположения, которым должен удовлетворять полином Т для оценки интеграла (2.1), необходимы некоторые специальные функции над полиномами, определяемые в §2.3.
2.2. Матрицы с асимптотическим диагональным доминированием
2.2.1. Свойства обратной матрицы
Пусть А — симметрическая обратимая пхп матрица. Известно, что величины любых двух матричных норм связаны между собой, см.например [11]. В частности,
1И_1||2 < = 1И”1 Нос < С\А-%, С> 0. (2.5)
В общем случае, константа С в (2.5) зависит от size Л = п. Тем не менее, в случае матрицы с асимптотическим диагональным доминированием можно выбрать константу С независимо от размера матрицы.