Дмитрий Валерьевич Карпов

Дмитрий Карпов
Лаборатория математической логики
Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН

Email: dvk0@yandex.ru


Основная область интересов - теория графов. Все, что связано с комбинаторными доказательствами в различных областях теории графов. Особенно - связность, раскраски, изображения графов на поверхностях, экстремальные задачи.

С 2009 года пишу книгу "Теория графов." Изначально в основу был положен обзорный курс по теории графов, читаемый в 3 семестре 211 группе мат-меха СПбГУ. Постепенно книга растет: я добавляю туда то, что мне интересно. Книга изменяется: я читаю материалы на спецкурсах, иногда студенты предлагают более простые и красивые доказательства. Отмечу вклад Глеба Ненашева, Александра Глазмана и других. Читайте, используйте - я буду рад, если книга вам пригодится! Если что-то покажется вам неправильным или непонятным, сообщите мне - работа над книгой продолжается.

Меня интересует всё комбинаторное в теории графов. Но результаты получаются в основном по связности графов. Далее -- ссылки на несколько моих статей по структуре связности графа. Основная идея -- построение в графах большой связности древовидных структур, обобщающих свойства дерева блоков и точек сочленения.

W.Mader в 1972-1979 годах исследовал минимальные k-связные графы (то есть такие, которые теряют k -связность при удалении любого ребра). Была доказана точная нижняя оценка на количество вершин степени~$k$ в таком графе. В следующей статье показано, что любой минимальный k-связный граф с наименьшим количеством вершин степени k строится на основе k копий дерева, степени вершин которого не превосходят k+1.

Далее - несколько оценок на максимальное количество листьев в остовных деревьях связного графа. Цель -- получить нижнюю оценку на это количество, в которую каждая вершина вносит вклад, зависящий от ее степени. Начало этой деятельности было работами, вышедшими в 1990-е, в которых получаются оценки через минимальную степень графа. При этом, минимальная степень должна быть не менее~3, так как использованный для построения деревьев метод мертвых вершин плохо подходит для учета вершин степеней 1 и 2. Однако, его модификации плюс новые методы, основанные на использовании блоков и точек сочленения, позволяют получить новые оценки. И еще одна деталь -- мне оценка интересна только в случае, когда существует бесконечная серия примеров, на которых она достигается.

А теперь - не о связности. Раскраски, теорема Брукса - как мне все это нравится. Жаль, мало что получилось придумать. Сначала - работа с теоремой, которая, на мой взгляд, обобщает теорему Брукса на правильные раскраскеи гиперграфов. А здесь - обобщение теоремы Брукса на правильные динамические раскраски вершин графа, то есть, раскраски, в которых окрестность каждой вершины степени хотя бы два имеет хотябы два разных цвета. Оказалось, что для такой раскраски также достаточно количества цветов, равного максимальной степени графа, правда, начиная с максимальной степени 8. И графы-исключения очень похожи на полный граф, являющийся исключением в теореме Брукса.

Преподавательская работа не просто дополняет научную... Мне кажется, ничто так не способно стимулировать появление новых идей, как хорошие ученики. Мне повезло иметь таких учеников, как Николай Гравин, Александр Глазман, Глеб Ненашев. Николай в 2009 году защитил кандидатскую диссертацию под моим рукводством. Студенты попадают ко мне благодаря обзорному курсу по теории графов, что я читаю в 3 семестре 211 группе мат-меха СПбГУ. Вот какой он был в осеннем семестре 2014 года. А студентов-старшекурсников я мучаю спецкурсами, в которых стараюсь разбирать теоремы, в которых мне самому разобраться интересно и непросто. Далее - вопросы последних четырех спецкурсов, прочитанных в 2012-2013 годах.

А это, надеюсь, в скором времени станет моей докторской диссертацией. Я постарался написать введение так, чтобы была понятна идеология того, что я сделал по связности. А про пользу теории графов в народном хозяйстве как раз не написал...
  • Структура связности графа.


  • [Laboratory] [Institute]