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

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

Email: dvk0@yandex.ru

Родился 2 марта 1975 года в Ленинграде.
В 1992 году окончил ФМЛ 239.
В 1997 году окончил математико-механический факультет Санкт-Петербургского государственного Университета.
С 1997 года работаю в Лаборатории математической логики ПОМИ им. В.А.Стеклова РАН. С 2011 года - старший научный сотрудник .
С 1997 года работаю в Лаборатории математической логики ПОМИ им. В.А.Стеклова РАН. С 2011 года - старший научный сотрудник В 2004 году защитил диссертацию (к.ф-м.н.) "Структура разбиения k-связного графа". В 2015 году защитил диссертацию (д.ф-м.н.) "Структура связности графа". .

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

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

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

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

Д.В.Карпов, А.В.Пастор. Структура разбиения k-связного графа. Записки научных семинаров ПОМИ т.266 (2000), стр. 76-106.
Д.В.Карпов. Разделяющие множества в k-связном графе. Записки научных семинаров ПОМИ т.340 (2006), стр. 33-60.
Д.В.Карпов, А.В.Пастор. Структура разбиения трехсвязного графа.. Записки научных семинаров ПОМИ т.391 (2011), стр. 90-148.
Д.В.Карпов. Дерево разбиения двусвязного графа.. Записки научных семинаров ПОМИ т.417 (2013), стр. 86-105.
Д.В.Карпов. Дерево разрезов и минимальный k-связный граф. Записки научных семинаров ПОМИ т.427 (2014), стр. 22-40.

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

Д.В.Карпов. Минимальные k-связные графы с минимальным числом вершин степени k. Записки научных семинаров ПОМИ т.427 (2014), стр. 41-65.

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

Д.В.Карпов. Остовные деревья с большим количеством висячих вершин. Записки научных семинаров ПОМИ т.381 (2010), стр. 78-87.
Д.В.Карпов. Остовные деревья с большим количеством висячих вершин: новые нижние оценки через количество вершин степеней 3 и не менее 4. Записки научных семинаров ПОМИ т.406 (2012), стр. 31-66.
Д.В.Карпов. Остовные деревья с большим количеством висячих вершин: нижние оценки через количество вершин степеней 1, 3 и не менее . Записки научных семинаров ПОМИ т.406 (2012), стр. 67-94.

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

Н.В.Гравин, Д.В.Карпов. О правильных раскрасках гиперграфов. Записки научных семинаров ПОМИ т.391 (2011), стр. 79-89.

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

Д.В.Карпов. Динамические правильные раскраски вершин графа. Записки научных семинаров ПОМИ т.381 (2010), стр. 47-77.

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

Обзорный курс. 211 группа, 3 семестр.

А студентов-старшекурсников я мучаю спецкурсами, в которых стараюсь разбирать теоремы, в которых мне самому разобраться интересно и непросто. Далее - вопросы последних четырех спецкурсов, прочитанных в 2012-2013 годах.

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

Структура связности графа.