«Друг моего друга мне не друг» или две теоремы теории графов. Часть 2

Окончание. Начало здесь

Граф может содержать треугольники, но не содержать полных подграфов бо́льшего размера. Такой случай был рассмотрен венгерским математиком Палом Ту́раном [Pál Turán].

Как утверждают знатоки венгерского языка, диакритический знак над á означает не ударение, а длительное произношение гласной. Правильно произносить фамилию следует с ударением на первом слоге.

Согласно традиции (а также для того, чтобы нижеприведенные формулы не отличались от тех, которые можно найти в других публикациях), для количества вершин (отсутствующих) полных подграфов мы будем употреблять не $k$, а $k+1$. Как выяснится чуть позже, в этом есть определенное удобство.

Следующее утверждение часто называют теоремой Турана, хотя на самом деле оно является следствием из теоремы Турана, которую обсудим ниже:

В $n$-вершинном графе не содержащем полных $(k+1)$-вершинных подграфов количество ребер не превосходит $\left(1-\dfrac{1}{k}\right)\dfrac{n^2}{2}$.

Обозначив через $r(n,k)$ количество ребер $n$ - вершинного графа без полных $k+1$-вершинных подграфов, данное утверждение можно записать в виде: $$ r(n,k) \leslant \left(1-\dfrac{1}{k}\right)\dfrac{n^2}{2} \qquad(7) \label{eq:Turan} $$

Заметим, что неравенство (5) (теорема Мантеля), доказанное в первой части, является частным случаем неравенства (7) при $k=2$.

Докажем индукцией по $k$.

При $k=1$ неравенство (7) принимает вид $r \leslant 0$. Проверим, верно ли оно. Полный граф размера 2 — это две вершины, соединенные ребром. Следовательно отсутствие полного подграфа размера 2 означает отсутствие ребер. Поэтому $r=0$ и неравенство имеет место.

Пусть неравенство (7) справедливо для некоторого $k$. Докажем его справедливость для $k+1$. Рассмотрим граф размера $n$, не содержащий полных подграфов размера $k+2$. Пусть $A$ — вершина максимальной степени $m$, а $M$ множество вершин смежных с $А$. Множество $M$ содержит $m$ элементов. Рассмотрим порожденный подграф, образованный вершинами из $M$. В таком подграфе не должно быть полных подграфов порядка $k+1$, так как если такой граф найдется, то присоединив к нему вершину A с инцидентными ребрами (как мы помним, вершина A соединена со всеми вершинами из $M$), получим полный подграф порядка $k+2$, что не допускается условием. Поэтому к такому подграфу можно применить индукционное предположение. Получим: $$ r' \leslant \left(1-\frac{1}{k}\right)\frac{m^2}{2} $$

Оценим количество остальных ребер $r''$. Каждое из таких ребер инцидентно хотя бы одной вершине, не содержащейся в $M$. (Говоря по-простому. хотя бы один из концов каждого из остальных ребер находится вне $M$.) Пусть $N$ - множество вершин, дополнительное к $M$ (содержащее все вершины, не содержащиеся в $M$). Обозначим суммарную степень вершин из $N$ через $D$. Так как каждое из $r_2$ ребер инцидентно хотя бы одной вершине из $N$, то $r'' \leslant D$. С другой стороны, в силу максимальности вершины А, степень каждой из $m-n$ вершин в $N$ не превосходит $m$, поэтому: $D \leslant m(n-m)$. Из этих неравенств получаем: $$ r'' \leslant m(n-m) $$.

Теперь можно оценить общее количество ребер: $$ r(n,k+1)=r'+r'' \leslant \left(1-\frac{1}{k}\right)\frac{m^2}{2} + m(n-m) = -\left(1+\frac{1}{k}\right)\frac{m^2}{2}+mn $$.

Выделив полный квадрат в правой части, получаем: $$ r(n,k+1) \leslant -\frac{k+1}{2k}\left(m-\frac{nk}{k+1}\right)^2+\frac{n^2k}{2(k+1)} $$ Отсюда $$ r(n,k+1) \leslant \frac{n^2}{2}\frac{k}{k+1} = \left(1-\frac{1}{k+1}\right)\frac{n^2}{2} $$

Получили неравенство (7) для $k+1$, чем завершается доказательство.

Как вы наверное заметили, в доказательстве использована та же идея, что и в доказательстве теоремы Мантеля, что неудивительно.

Граф Турана

На самом деле, теорема Турана не только дает оценку количества ребер, но указывает $n$-вершинный граф без полных $k+1$-вершинных подграфов, дающий максимальное количество ребер.

В первой части нам удалось найти исчерпывающий ответ для $k=2$: полный двудольный граф с долями почти равной мощности. По аналогии можно предположить, что при большем значении $k$, максимальное количество ребер дает $k$-дольный граф с долями почти равной мощности.

.

Для построения такого графа разделим $n$ на $к$ с остатком. Получим: $$ n=ak+b, \text{  где  } 0\leslant b \lt k \qquad(8) $$

Разбиваем все множество вершин на $b$ подмножеств по $a+1$ вершине в каждом и $k-b$ подмножеств по $a$ вершин в каждом. Легко убедиться, что $$ (a+1)b+a(k-b)=n \qquad(9) $$, то есть множество вершин графа действительно развивается на $k$ подмножеств, причем количества вершин (мощности) каждой пары множеств отличаются по абсолютной величине не более чем на единицу.

Чтобы получить полный $n$-дольный граф, достаточно соединить каждую вершину каждой доли с каждой из вершин других долей (но не своей доли!). Полученный граф называется графом Турана и обозначается $T(n, k)$.

Нижеследующий рисунок дает пример графа Турана для $n=10$ и $k=3$.

Теперь можно сформулировать теорему Турана:

Теорема Турана.(P. Turán, 1943). Граф $T(n, k)$ дает максимальное количество ребер среди всех $n$-вершинных графов не обладающих полными $k+1$-вершинными подграфами.

Теорема Турана была впервые опубликована на венгерском языке в 1941 году:

Turán, P. (1941). Egy gráfelméleti szélsőértékfeladatról (Об экстремальных проблемах теории графов). Matematikai és Fizikai Lapok. 48: 436–452.

Ведь были времена, когда отнюдь не все серьезные математические журналы печатали статьи на английском языке! «Свежо предание, но верится с трудом.» Парадоксальнее всего то, что именно тогда перевести статью было совсем не просто: ведь нужен был не просто переводчик, а математический эксперт, владеющий языком. И все же статья была замечена и теорема Турана стала одной из фундаментальных теорем теории графов. Так стоит ли писать статьи на примитивном английском языке, когда только на родном языке можно выразить мысль четко и однозначно?! На самом деле, больше всего от гегемонии английского языка страдает ... сам английский язык. То и дело на англоязычных сайтах можно найти пожелание: «Не пишите на сложном языке, потому что люди, не владеющие языком в совершенстве, вас не поймут.» Некоторые «корифеи грамматики» додумались до того, что предлагают отказаться от страдательного залога или использования сложных дополнений с предлогом на конце. То ли еще будет! Даже читая английскую литературу 1930х годов, можно заметить, как обеднел язык за эти годы и в лексике, и в стилистике, а если говорить о произведениях, XIX века, то скоро их понять будет не легче, чем Шекспира.

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

Здесь я только покажу, что неравенство (7) является следствием теоремы Турана

Заметим что каждая вершина $(а+1)$-вершинной доли соединяется с $n-(а+1)$ вершинами других долей. Поскольку таких долей $b$, суммарная степень вершин, находящихся в этих долях равна $b(n-a-1)(a+1)$. Каждая вершина $а$-вершинной доли соединяется с $n-а$ вершинами других долей. Таких долей $k-b$, суммарная степень вершин, находящихся в этих долях равна $(k-b)(n-a)a$. Вспомнив лемму о рукопожатиях, согласно которой сумма степеней равна удвоенному количеству ребер, получим: $$ 2r_{max}(n,k) = b(n-a-1)(a+1) + (k-b)(n-a)a = [b(a+1)+(k-b)a](n-a) - b(a+1) $$ где $r_{max}(n,k)$ — количество ребер графа Турана $T(n,k)$, то есть максимальное количество ребер, возможное для графа порядка $n$ без полных подграфов порядка $k+1$.

Согласно (9) выражение в квадратных скобках есть $n$. Производя замену получаем: $$ 2r_{max}(n,k) = n(n-a)-b(a-1) = n^2-a(n+b)-b $$

Сделав, согласно (8), постановку $a=\frac{n-b}{k}$, приходим к $$ 2r_{max}(n,k) = n^2-\frac{n^2-b^2}{k}-b = n^2\left(1-\frac{1}{k}\right) - \frac{b(k-b)}{k} $$

Наконец, $$ r_{max}(n,k) = \left(1-\frac{1}{k}\right)\frac{n^2}{2} - \frac{b(k-b)}{2k} \qquad (10) $$

Легко видеть, результат (9) из части 1 является частным случаем полученного равенства, соответствующем $k=2$.

Так как $0 \leslant b \lt k$, вычитаемое в (10) является числом неотрицательным, откуда в силу максимальности графа Турана, следует неравенство (7).

Из (10) следует, что что при $b=0$ (то есть, если $k$ является делителем $n$), неравенство (7) становится равенством:  $r_{max}(n,k)=\left(1-\dfrac{1}{k}\right)\dfrac{n^2}{2}$

Воспользуемся неравенством (10) для оценки нижней границы $r_{max}(n,k)$ при $b>0$. Согласно теореме о средне-арифметическом и средне-геометрическом $b(k-b) <= \dfrac{k^2}{4}$, поэтому: $$ \left(1-\frac{1}{k}\right)\frac{n^2}{2} - \frac{k}{8} \leslant r_{max}(n,k) \leslant \left(1-\frac{1}{k}\right)\frac{n^2}{2} $$

Неравенство показывает, что число $r$ находится в интервале длиной $\dfrac{k}{8}$. Если $k \leslant 8$, длина интервала не превосходит 1, поэтому в нем может находиться одно целое число. Отсюда, если $k \leslant 8$ и не является делителем $n$, $$ r_{max}(n,k) = \begin{cases} \left(1-\dfrac{1}{k}\right)\dfrac{n^2}{2} - 1, & \text{если  } \left(1-\dfrac{1}{k}\right)\dfrac{n^2}{2} \text{— целое} \\ \left\lfloor\left(1-\dfrac{1}{k}\right)\dfrac{n^2}{2}\right\rfloor, & \text{если  } \left(1-\dfrac{1}{k}\right)\dfrac{n^2}{2} \text{— дробное}\end{cases}\qquad (11) $$

ЗАДАЧИ

1. В шахматном турнире принимает участие 15 шахматистов. Возможна в течении турнира ситуация, когда каждый шахматист сыграл ровно 7 партий?

2. На плоскости даны 60 точек. Какое наибольшее количество отрезков можно провести, чтобы в любом множестве из $n$ точек нашлись две точки, не соединенные между собой отрезком. Рассмотрите случаи $n=3,4,5,9,10,11$.

3. На плоскости даны 60 точек, так что никакие три из них не лежат на одной прямой. Какое наименьшее количество отрезков следует провести, чтобы в любом множестве из $n$ точек нашлись две точки, соединенные между собой отрезком. Рассмотрите случаи $n=3,4,5,9,10,11$.

4. В пространстве расположено $2n$ ($n\geslant 2$) точек (так что никакие 4 не лежат в одной плоскости) и проведено $n^2+1$ отрезков с концами в этих точках. Докажите, что проведенные отрезки образуют: а) хотя бы один треугольник; б)* не менее $n$ треугольников.

Решения задач: здесь