Семинар «Алгебра. Матрицы. Графы.» от МЛ ТИ «Реализующее число простого сборного графа»

Дата: 17 апреля 2026 г., 18:10 - 19:30

Докладчик: Калинку Максим, студент ПМИ, ФКН НИУ ВШЭ 

Аннотация: Доклад продолжает обсуждение простых сборных графов, начатое 3 апреля, и посвящён вопросу о графах с наибольшим сборным числом при фиксированном количестве вершин. Хотя вычислительная сложность задачи определения сборного числа неизвестна, анализ работы жадных алгоритмов позволяет эффективно отделить графы, на которых достигается максимум. В первой части доклада будет представлен недавний результат для общего случая графов: точная формула реализующего числа R_min(k) = 3k - 2 и характеризация экстремального класса как семейства петельных подстановок. Во второй части мы обсудим, как эти идеи обобщаются на случай простых сборных графов без петель. Также будут намечены перспективы дальнейшего развития данной теории.

Место проведения: Покровский бульвар, д. 11, R408

Доклад проводится в рамках цикла семинаров "Алгебра. Матрицы. Графы."