[МУЗЫКА] [МУЗЫКА] Здравствуйте! Мы приступаем к завершающему модулю нашего курса, в котором мы познакомимся с такими понятиями, как схема отношений и когерентные конфигурации. Схема отношения является одной из важнейших составляющих алгебраической комбинаторики. И в качестве основных истоков схем отношений можно выделить статистику и теорию групп. Само понятие «схема отношений» впервые возникло в работе Боуза и Шимамото 1952 года, которая была посвящена задаче планирования экспериментов. Алгебраический аппарат для схем отношений был предложен в работе Боуза — Меснера в 1959 году. Если при упоминании этих фамилий у вас голове возникает алгебра Боуза и Меснера, то вы совершенно правильно о них подумали, о них мы также будем говорить. Конечно же, ключевой вклад в развитие теории схем отношений внес Дельсарт. В его знаменитой диссертации он привел к одному знаменателю теорию кодирования и теорию комбинаторных дизайнов, таким образом предложив единый подход и единые методы для решения, казалось бы, задач про разные объекты разной природы. Тем самым он привлек к схемам отношений исследователей со всего мира, что в итоге привело к бурному развитию как самой теории схем отношений, так и множества смежных дисциплин. В качестве мотивации, почему определение схем отношений именно такое и какую природу объектов, скажем так, оно описывает, я бы хотела привести пример, позаимствованный из книги Питера Камерона и ван Линта. Давайте вспомним про сильно регулярный граф и его дополнение. Вы помните, что сильно регулярный граф, конечно же, далеко не всегда совпадает с дополнением к самому себе, однако в каком-то смысле можно сказать, что сам граф и его дополнение несут в себе одну и ту же информацию, потому что по параметрам одного мы автоматически можем вычислить параметры другого и, как следствие, различные инварианты соответствующего графа. Таким образом, мы можем рассматривать оба этих графа в связке как некоторое множество, на котором определены три отношения: совпадение, смежность и несмежность. И оказывается, такой подход применим не только к сильно регулярным графам, но и ко многим другим объектам. Неформально говоря, можно сказать, что схемы отношений описывают некоторые взаимосвязи между парами элементов из некоторого множества Ω. В данном модуле мы с вами рассмотрим аж три эквивалентных определения схем отношений, каждое из которых имеет свои достоинства и некоторые недостатки в плане наглядности, но в совокупности, я надеюсь, они позволят вам довольно хорошо познакомиться с объектами и уже представлять более интуитивно все те свойства, которые записываются иногда немного громоздкими формулами. Но, прежде чем приступить к определениям, давайте вспомним несколько понятий, а также договоримся об их значениях. Множество Ω у нас всегда будет конечным, непустым и состоять как минимум двух элементов. Напомню, что разбиением множества называется такой набор попарно непересекающихся подмножеств, которые в объединении дают в точности исходное множество. Декартовым произведением Ω * Ω, как вы помните, мы называем множество упорядоченных пар вида (x, y), где каждый из элементов принадлежит нашему множеству Ω. Итак, что же такое отношение? Отношением R назовем произвольное подмножество декартова произведения Ω * Ω и будем говорить, что x и y связаны отношением R, если пара (x, y) принадлежит множеству R. Простым примером отношения в контексте нашего курса будет, конечно же, отношение смежности, то есть в качестве R у нас выступает просто множество ребер E. Отметим, что отношение — это множество упорядоченных пар. Таким образом, поменяв порядок во всех пар отношения, мы получим отношение R', которое будем называть дуальным к R. Если R и R' совпадают, то отношение R называют симметричным. Возвращаясь к примеру с отношением смежности, случай несимметричного отношения у нас будет соответствовать, конечно же, ориентированному графу, а дуальным отношением будет множество всех ребер, взятых с обратным направлением. А случай симметричного отношения будет соответствовать уже неориентированному графу, то есть графу симметричной матрицы смежности. Итак, мы готовы переходить к первому определению схем отношений, которое у нас будет в терминах разбиения. Схемой отношений с d классами на множестве Ω называется разбиение декартова произведения Ω * Ω на d + 1 множество R0, R1, ..., Rd, удовлетворяющих следующим условиям. Первое условие: отношению R0 у нас соответствует диагональное отношение, которое состоит в точности из пар вида (x, x) для всех x из нашего множества Ω. Второе условие: что каждое из отношений Ri является симметричным, то есть Ri равно своему дуальному отношению Ri' для любого i от 1 до d. R0, конечно же, по определению будет симметричным отношением. И наконец третье условие: что для любых i, j, k из множества от 0 до d существует такое число Pijk, что какую бы пару (x, y) из отношения Rk мы ни выбрали, число элементов z таких, что (x, z) принадлежит отношению Ri, а пара (z, y) принадлежит отношению Rj будет в точности равно этому числу Pijk и, иными словами, не зависит от выбора исходной пары (x, y), а зависит только от i, j и k. Числа Pijk называются индексами пересечений или параметрами схемы отношений. Давайте добавим немного наглядности этому определению, которое в формальной записи может выглядеть немного громоздким и пугать. Представим декартово произведение Ω * Ω в виде квадратной матрицы, строки и столбцы которой занумерованы некоторым фиксированным образом элементами из Ω. О чем нам говорит условие 1? Условие 1 нам говорит, что главная диагональ представляет собой в точности наше отношение R0. Отметим все элементы этого отношения, например, красным цветом. Условие 2 требует, чтобы любое отношение Ri было симметрично относительно главной диагонали. Таким образом, тривиальный пример схемы отношений можно привести, если мы возьмем все внедиагональные элементы в качестве какого-то отношения R1. Гораздо сложнее интерпретировать на этой картинке третье условие, но тут как раз нам на помощь придет второе определение в терминах графа, о котором мы поговорим в следующей лекции. Стоит отметить, что существует несколько обобщений понятия схем отношений. Вместо требования симметричности часто накладывают условие на замкнутость множества отношений относительно транспонирования. То есть если мы возьмем дуальное отношение к Ri, мы получим еще какое-то отношение, не обязательно совпадающее с исходным Ri. При таком определении мы как раз получим гомогенные когерентные конфигурации из работы Хигмана, и к этому понятию мы еще с вами обязательно вернемся в завершении нашего модуля. А Дельсарт же в своей диссертации добавлял еще одно дополнительное условие, что Pijk = Pjik для любых i, j, k, тем самым определяя коммутативные схемы отношений. Однако для некоторого упрощения изложения материала в рамках нашего курса мы будем рассматривать только симметричные схемы отношений, хотя многие утверждения, которые у нас возникнут, будут, конечно, верны и в общем случае.
