Математика, которая мне нравится

В начале 70-х годов прошлого века Джон Пирс предложил коммуникационную сеть, состоящую из соединенных между сосбой в различных точках направленных циклов. Чтобы сообщение попало из исходной точки одного цикла в точку назначения на другом цикле, необходимо было понять, в каких точках нужно переходить на следующие циклы.

Рональд Грэм и Генри Поллак предложили считать каждый цикл вершиной графа, которую отмечали последовательностью символов из алфавита таким образом, чтобы расстояние Хэмминга между строками соответствовало расстояниям в графе. Тогда переходить на другой цикл следовало, когда адрес нового цикла имел меньшее расстояние Хэмминга до точки назначения.

Расстояние между строками символов трехэлементного алфавита определялось следующим образом. Расстояние между двумя символами и равно

Далее это определение распространяется на строки длины и следующим образом:

В целях более эффективной работы желательно было сделать строки-адреса как можно более короткими. Грэм и Поллак предположили, что длины строк , где — число вершин графа, всегда достаточно. Это предположение было доказано П. Уинклером десять лет спустя.

Грэм и Поллак свели данную задачу к задаче о наименьшем числе полных двудольных графов, на которые можно разбить полный граф с вершинами. (Разбиение происходит так, чтобы раные двудольные графы не имели общих ребер).

Теорема (Грэм, Поллак, 1972 г.). Если множество ребер полного графа с вершинами есть объединение непересекающихся множеств ребер полных двудольных графов, то .

Доказательство. Предположим, что полный граф с набором вершин разбит на полные двудольные графы . Обозначим через — две части множества вершин графа . Заметим, что множества и не имеют общих элементов.

Свяжем с каждым графом матрицу размерности следующим образом. Элемент матрицы, стоящий в -й строке и -м столбце положим равным , если , и в противном случае.

Ясно, что каждая такая матрица имеет ранг . Пусть . Для всех в точности один из элементов или отличен от нуля в . Следовательно, , где — матрица , все элементы которой равны , а — единичная матрица.

Докажем, что если матрица удовлетворяет данному уравнению, то ее . Отсюда сразу же следует неравенство , поскольку для ранга матриц справедливо неравенство .

Предположим, что . В этом случае существует ненулевой вектор , удовлетворяющий системе линейных уравнений

Для этого вектора имеем и, следовательно, . Тем самым . Получили противоречие, которое и доказывает теорему.

Источник: László Babai, Péter Frankl, Linear Algebra Methods in Combinatorics with Applications to Geometry and Computer Science, Preliminary Version 2 (September 1992), The University of Chicago.