Ранее мы с вами говорили, что с помощью схем отношений и соотношений на их параметры можно доказывать различные утверждения про объекты совершенно разной природы. В этой лекции мы продемонстрируем это на примере, который позаимствуем из первого модуля. Но сначала нам потребуются кое-какие предварительные замечания. Пусть Пи — автоморфизм схемы отношений. Обозначим за Ni число точек x таких, что x и Пи от x принадлежат одному и тому же отношению Ri. Важным для нашего примера является следующая теорема: для любого j число, указанное на слайде, является всегда целым алгебраическим числом. Напомню, что целое алгебраическое число — это корень какого-то многочлена с целыми коэффициентами и со старшим коэффициентом, равным единице. Итак, пусть у нас Гамма — это сильно регулярный граф с параметрами, указанными на экране. Я надеюсь, что эти параметры кажутся вам знакомыми, потому что в четвертой лекции первого модуля вам рассказывали, что неизвестно, существует ли граф с такими параметрами или нет. Но если он существует, то это будет граф Мура диаметра два. И мы с вами докажем, что этот граф не является вершинно- транзитивным, как это сделал Хигман. Для этого рассмотрим матрицу Q, которую мы можем вычислить по параметрам нашего сильно регулярного графа, и рассмотрим произвольную нетривиальную группу автоморфизмов такого графа. Выделим в графе множество вершин, которые остаются на месте под действием группы G, и рассмотрим индуцированный на них подграф. Оказывается, он будет либо сильно регулярным графом Мура, а следовательно, в нем будет меньше вершин, то есть 5, 10 или 50, потому что мы знаем все графы Мура с меньшим числом вершин, либо звездой, как указано на экране, и в таком случае таких вершин может быть не больше, чем степень графа плюс единица, то есть 58. Рассмотрим инволюцию Пи. Напомню, что инволюция — это элемент, совпадающий с обратным к себе. Если инволюция не меняет между собой вершины некоторого ребра, тогда мы получаем, что N1 равно нулю, а N0 в сумме с N2 дает 3250. Рассмотрим пару несмежных вершин (x, y), таких, что одна из вершин этой пары под действием Пи переходит в другую. Так как параметр Мю у нас равен единице (а Мю, напомню, это число общих "соседей" у двух несмежных вершин, как в нашем случае), тогда мы получаем, что единственный общий "сосед" z вершин x и y останется на месте. А кроме того, он возникнет не в более, чем в 28 таких парах (x, y). Отсюда получаем оценку на число N2. А сейчас мы с вами отвлечемся немного от букв и посчитаем конкретные циферки. Итак, что мы к этому моменту имеем? Мы имеем, что N0 равно 58, N1 равно нулю, а N2 равно 3192. Это значит, мы получаем следующее выражение, и если мой счет в уме меня не подводит, это должно быть равно 133/5. Мы получили рациональное число. Рациональное число может быть алгебраическим целым, только когда оно само по себе целое число. Таким образом, мы пришли к противоречию, а это значит, что наша инволюция Пи должна менять местами две смежные вершины x и y. Но в таком случае она также меняет оставшиеся 56 "соседей" вершины x с оставшимися 56 вершинами, соседними с y. Для любой такой пары (u, v), где u у нас из окрестности x, а v из окрестности y, мы получим, что единственный общий "сосед" этих вершин остается на месте под действием нашей инволюции. Таким образом, мы получаем все оставшиеся на месте вершины, что дает нам значение N0, равное 56. Следовательно, инволюция Пи будет являться нечетной перестановкой, так как она является произведением нечетного числа транспозиций в виде 1597. Далее нам потребуется всего парочка утверждений, позаимствованных из теории групп, чтобы прийти к финальному противоречию и доказать, что группа нетранзитивна, но их мы оставим заинтересованному читателю в качестве домашнего упражнения.