\documentclass[12pt,a4paper]{article}
\usepackage{amssymb, amsmath, amscd, euscript}
\usepackage[cp1251]{inputenc}
\usepackage[russian]{babel}

\DeclareMathOperator{\girth}{girth}

\begin{document}


\begin{center}
\textbf{Занятие 2.}

Графы с большим обхватом и большим хроматическим числом

Большие независимые множества в графах без треугольников

Графы-расширители
\end{center}

Сегодня мы познакомимся с тремя классическими результатами
теории графов, получить которые проще всего,
пользуясь вероятностными методами.


Пусть $G$ --- неориентированный граф без петель и кратных ребер на $n$
вершинах. Напомним, что раскраска вершин графа
$G$ называется \emph{правильной}, если
соединенные ребром вершины имеют разные цвета.
Определим \emph{хроматическое число} $\chi(G)$
графа $G$ как наименьшее количество цветов, необходимое
для правильной покраски вершин графа $G$. Через $\alpha(G)$
обозначим размер максимальной антиклики (пустого подграфа)
в графе $G$. Очевидно, что $$\alpha(G)\ge n/\chi(G), \eqno(1)$$
поскольку
при правильной покраске вершины каждого цвета образуют антиклику.
\emph{Обхватом} $\girth(G)$ графа $G$ назовем длину
наименьшего простого цикла в $G$ (обхват леса
не определен, но он нас интересовать не будет).

Долгое время стоял вопрос о существовании
графов с большим обхватом и большим хроматическим числом.

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

Возьмем $n$ вершин и будем проводить ребро между любыми
двумя вершинами с данной вероятностью $p$, все ребра
проводятся или не проводятся независимо. Случайный граф,
определяемый таким образом, назовем $G(n,p)$.

Зафиксируем $k$ и будем пытаться построить случайный граф без циклов длины,
не большей $k$ (назовем их короткими). Выберем $p=n^{\theta-1}$, где $0<\theta<1/k$.
Оценим математическое ожидание количества коротких циклов.
Для каждого $l$, $3\le l\le k$ имеется $n(n-1)\dots(n-l+1)/(2l)$
возможных циклов длины $l$, вероятность каждого равна $p^l=n^{l\theta-l}$.
Таким образом, математическое ожидание количества циклов длины $l$
равно
$$
\sum_{l=3}^k \frac {n(n-1)\dots(n-l+1)}{2l} n^{l \theta-l}< k n^{k\theta}<n/4
$$
при больших $n$. Таким образом, с вероятностью хотя бы $1/2$
количество коротких циклов не превосходит $n/2$ (иначе бы матемтаическое ожидание
их количества было бы не меньше $\frac12\cdot \frac{n}2=n/4$.

Теперь оценим вероятность наличия большой антиклики.

Зафиксируем $m<n$. Количество способов выбрать множество из
$m$ вершин антиклики
равно $C_n^m<2^n$. Для каждого такого множества вероятность того,
что между его вершинами не проведено ребер, равна
$(1-p)^{C_m^2}$. Воспользуемся полезной оценкой $1-p<e^{-p}$
и получим, что вероятность наличия антиклики размера $m$ не превосходят
$$
2^n e^{-pC_m^2}< e^{n-pm^2/3}=e^{n(1-\frac{1}{3}n^{\theta}m^2/n^2)}
$$
Таким образом, при $m_0=[100 n^{1-\theta/2}]$
и большом $n$ вероятность наличия в графе $G(n,p)$ антиклики размера
$m_0$ будет меньше 1/2 --- стало быть, хроматическое число с вероятностью
больше чем 1/2 будет не меньше чем $n^{\theta/2}/100 \rightarrow \infty$.

Итак, с вероятностью большей половины в графе $G(n,p)$ нет антиклик
мощности $m_0$; также с вероятностью большей половины в нем не
более чем $n/2$ коротких циклов. Значит, с положительной
вероятностью выполняются оба
описанных события. Выкидывая по вершине из
каждого короткого цикла получаем граф не менее чем с $n/2$
вершинами, в котором нет коротких циклов и нет антиклик размера $m_0=o(n/2)$.

\vskip 0.2cm

Перейдем к следующему сюжету.

Если степени всех вершин графа на $n$ вершинах
не превосходят $d$, в нем легко найти антиклику размера $n/(d+1)$.
Например, годится жадный алгоритм: если $k<n/(d+1)$ попарно несоединенных
вершин уже найдено, то всегда можно добавить еще одну.

Оказывается, что для графов без треугольников эта оценка может
быть значительно улучшена.

\textbf{Теорема.} В графе без треугольников на $n$ вершинах, степени
которых не превосходят $d>100$, найдется антиклика мощности
хотя бы $\frac {n\log d}{4d}$.

\textbf{Доказательство} использует весьма хитроумные
вероятностные соображения. Выберем случайно антиклику $X$
в нашем графе (все антиклики равновероятны). Для каждой
вершины $v$ нашего графа $G$ определим случайную величину
$$
\xi_v=d\cdot |{\{v\}\cap X}|+|N(v)\cap X|,
$$
где $N(v)$ --- множество соседей вершины $v$, $|\cdot|$
обозначает мощность множества.
Докажем оценку на математическое ожидание введенной величины:
$E(\xi_v)\ge \log d/2$ для любой вершины $v$.
Зафиксируем пересечение $M$ случайной антиклики $X$ с множеством вершин,
отличных от $v$ и ее соседей. Достаточно доказать,
что при фиксированном $M$ условное математическое ожидание
величины $\xi_v$ не меньше заявленной оценки $\log d/4$
(поскольку полное математическое ожидание есть среднее взвешенное
условных по всем возможным $M$).
Пусть имеется $x$ вершин в множестве $N(v)$, не соединенных
ни с одной вершиной множества $M$. Тогда имеется $2^x+1$
способов дополнить множество $M$ до антиклики во всем графе:
либо добавить к $M$ вершину $v$, либо добавить некоторое
подмножество этих $x$ вершин (именно здесь мы пользуемся
отсутствием треугольников).
Отсюда получаем, что условное математическое ожидание, которое
нас интересует, равно
$$
\frac1{2^x+1}\cdot d+\frac{2^x}{2^x+1}\cdot \frac{x}2
$$
(средняя мощность случайного подмножества в $x$-элементном множестве
очевидно равна $x/2$).

При $x\ge \log d$ второе слагаемое не меньше, чем $\log d/2$,
при $x\le \log d$ первое слагаемое не меньше, чем $d^{1-\log 2}/2$.
В обоих случаях получаем требуемое.

Складывая неравенства $E(\xi_v)\ge \log d/2$
по всем вершинам $v$ получаем, что $E(\sum_v \xi_v)\ge n\log d/2$.
Значит найдется такая антиклика, что $\sum_v \xi_v\ge n \log d/2$.
Пусть она содержит $k$ вершин. Тогда значение случайной величины
$\sum_v \xi_v$ равно $kd$+(сумма степеней вершин, входящих
в эту антиклику), то есть $\le 2kd$. Отсюда $k\ge \frac{n\log d}{4d}$,
что и требовалось.

\vskip 0.2cm

Перейдем к третьему примеру --- вероятностной конструкции графов-расширителей.
Двудольный граф с долями по $n$ вершин
и максимальной степенью $\le d$ назовем $(n,d,c)$-расширителем ($1<c<2$),
если любые $k\le n/2$ вершин графа $G$ из одной доли
имеют в совокупности хотя
бы $ck$ соседей.

Не борясь за значения констант, предъявим вероятностную конструкцию
$(n,100,3/2)$-расширителя.

Пусть вершины первой доли суть $A_1,\,A_2,\dots,A_n$;
второй --- $B_1,\,B_2,\dots,B_n$. Выберем случайно и независимо
перестановки $\pi_1,\,\pi_2,\dots,\pi_{100}$ чисел от 1 до $n$
(все случайные перестановки имеют одинаковую вероятность $1/n!$).
Соединим вершины $A_i$ и $B_{\pi_s(i)}$ для всех $i=1,\,2,\dots,n$
и $j=1,\,2,\dots,100$. При необходимости удалим кратные ребра.

Получим случайный граф, степени
всех вершин которого не больше ста.
Оценим вероятность того, что полученный граф не является расширителем.
Это значит, что найдутся множества из $k$ (синих) вершин в первой доле
и $t=[3k/2]$ (красных) вершин --- во второй такие, что значения каждой
из ста перестановок $\pi_i$ на синих вершинах
являются красными (мы позволяем себе некоторую вольность речи, путая вершины
и их индексы). Если зафиксировать синие и красные вершины,
то для каждой перестановки вероятность указанного события равна
$$
\frac{t}{n}\cdot \frac{t-1}{n-1}\cdot\dots \frac{t-k+1}{n-k+1}\le
\left(\frac{t}{n}\right)^k.
$$
Суммируя по всем выборам красных и синих вершин и вспоминая, что
перестановок у нас 100, получаем оценку на искомую вероятность $p$
не быть
расширителем:

$$
p\le \sum\limits_{k=1}^{[n/2]} C_n^k C_n^{[3k/2]} \left(\frac{3k}{2n}\right)^{100k}
$$

Заметим, что $C_n^k\le n^k/k!\le (n/k)^k e^k$.
Поскольку $\frac{3k}{2n}\le 3/4$, получаем

$$
p\le \sum_{k=1}^{[n/2]} (3/2)^k e^{5k/2} (3/4)^{95k}<1.
$$

\end{document}
