Семинар «Алгебра. Матрицы. Графы»

На семинаре будет представлена фундаментальная теорема Хуа, лежащая в основе геометрии матриц. Эта теорема полностью описывает вид биективных отображений прямоугольных матриц, сохраняющих отношение когерентности: такие отображения переводят любые две матрицы, разность которых имеет ранг 1, в матрицы с таким же свойством. Оказывается, что все такие преобразования имеют простую структуру - они являются композицией умножения на обратимые матрицы, сдвига (прибавления произвольной матрицы) и, возможно, транспонирования. Теорема находит важные применения и допускает различные обобщения, которые также будут кратко затронуты.
Основное внимание в докладе будет уделено разбору ключевых идей и плану доказательства этой теоремы.

Рассмотрим пространство матриц m x n над конечным полем Fq, будем называть расстоянием d(A,B) между матрицами величину rk (A-B). В докладе будет рассказано о совместной статье Максаева, Промыслова и автора доклада, посвящённой описанию пар биективных отображений таких, что расстояние d(A,B) = k тогда и только тогда, когда d( f(A), g(B) ) = k. Оказывается, кроме небольшого количества исключительных случаев, такие отображения обязательно совпадают и являются изометриями. Основное внимание в докладе будет посвящено обзору применяемых методов, а именно рассказу теории схем отношений, свойствам их собственных чисел и чисел пересечений.

В данном продолжении доклада от 6.03 большая часть будет посвящена q-комбинаторике, от слушателей не требуется знакомство с предыдущим докладом. В заключении мы обсудим свойства собственных чисел схемы билинейных форм и свойства её чисел пересечений, что позволит завершить обзор недавней статьи "Maps preserving a fixed rank-distance on matrices over finite fields".

В докладе рассматриваются простые сборные графы — класс графов специального вида с заданным циклическим порядком ребер в каждой вершине. Интерес к этим объектам обусловлен их ролью в описании процессов рекомбинации ДНК простейших. Благодаря возможности представления таких графов с помощью 2-слов, для их анализа применим широкий спектр комбинаторных методов. Будут подробно разобраны основные свойства и характеристики простых сборных графов, включая сборное число и количество различных гамильтоновых множеств полигональных путей. Особое внимание будет уделено гипотезе 2013 года о строении простого сборного графа, обладающего максимальным числом гамильтоновых множеств полигональных путей, в связи с недавно опубликованным доказательсвтом данной гипотезы. В докладе будет представлено это доказательство, а также намечены дальнейшие перспективы развития данной теории.

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