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

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

Email: dvk0@yandex.ru


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

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

А это новый проект - книга "Связность графов." Именно по этому разделу мне есть что сказать, и это гораздо больше чем уместно написать в обзорной книге по теории графов. Работа над книгой начата весной 2017 по результатам прочтения спецкурса "Связность." Пока что текст весьма сырой и будет дополнен. Там есть и классика, и мои собственные результаты. НЕкоторые классические теоремы (например, теоремы Мадера, Халина, Татта) записаны с моими доказательствами и в моем изложении терминологии. Связность - область достаточно трудная и абстрактная, но надеюсь, кому-нибудь новая книжка пригодится! Хочу сделать ее максимально понятной сильному читателю.

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

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]