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

\DeclareMathOperator{\girth}{girth}
\DeclareMathOperator{\la}{la}
\renewcommand{\cap}{\bigcap}

\begin{document}


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

Локальная лемма Ласло Ловаса.
\end{center}
Если события $A_1,\,A_2,\dots,A_n$
взаимно независимы и вероятность каждого меньше 1,
то с положительной вероятностью ни одно из них
не происходит.

Локальная лемма Ловаса (1975) обобщает это наблюдение
на случай ``не сильно зависимых'' событий и имеет множество
подчас неожиданных применений.

Для семейства событий $A_1,\,A_2,\dots,A_n$ построим
\textbf{орграф зависимостей} следующим образом:
вершинами этого графа будут события $A_i$,
а множество событий $N_+(A_i)$, в которые ведут
стрелки из события $A_i$, таково, что $A_i$
не зависит от всех событий, кроме событий, входящих
в множество $N_+(A_i)$. Это означает, что для
любого события $B$, выражаемого через множество событий
$\{A_j,j\notin N_+(A_i)\}$, события $A_i$
и $B$ независимы. Через $\bar{A}$ будем обозначать
дополнение события $A$.

\textbf{Локальная лемма.}
Предположим, что нашлись такие числа $x_i\in (0,1)$,
что для всех $i$ выполняется неравенство
$p(A_i)\le x_i \prod_{j\in N_+(A_i)} (1-x_j)$.
Тогда $p(\cap \bar{A_i})\ge \prod (1-x_i)$ ---
в частности, с положительной вероятностью ни одно
из событий $A_i$ не происходит.

\textbf{Доказательство.} Докажем более
сильное утверждение: если $I=I_1\sqcup I_2$,
где $I_1,\,I_2$ --- множества индексов, то
$$
p\left(\cap\limits_{i\in I} \bar{A_i}\right)\ge
p\left(\cap\limits_{i\in I_2} \bar{A_i}\right)\cdot
\prod_{j\in I_1} (1-x_j).
$$
Для пустого $I_2$ получаем требуемое.
Докажем индукцией по $|I|$. Если $|I|=1$, то при $I_2=I$, $I_1=\emptyset$
имеет место равенство, а при $I_1=I$, $I_2=\emptyset$
имеем $p(\bar{A_i})=1-p(A_i)\ge 1-x_i$.
Теперь предположим, что для всех множеств индексов мощности
меньше $|I|$
и любых их подразбиения на два подмножества
неравенство имеет место. Докажем его для $I$.
Рассмотрим сначала случай $|I_1|=1$, $I_1=\{k\}$.
Обозначим $p(\cap_{i\in I_2} \bar{A_i})=p_0$.
Имеем
$$
p\left(\cap\limits_{i\in I} \bar{A_i}\right)
=p_0-p\left(\cap\limits_{i\in I_2} \bar{A_i}\cap A_k\right)\ge
p_0-p\left(\cap\limits_{i\in I_2\setminus N_+(A_k)} \bar{A_i}\cap A_k\right)=
$$

$$
p_0-p\left(\cap\limits_{i\in I_2\setminus N_+(A_k)} \bar{A_i}\right)p(A_k)\ge
p_0 (1-x_k).
$$

Чтобы проверить выполнение последнего неравенства, перепишем
его в равносильном виде
$$
p_0 x_k\ge p\left(\cap\limits_{i\in I_2\setminus N_+(A_k)} \bar{A_i}\right) p(A_k).
$$

Это неравенство следует из оценки $p(A_k)\le x_k \prod_{j\in N_+(A_k)} (1-x_j)$
и индукционного предположения.

Пусть теперь
$I_1=\{k\}\sqcup I_3$, $|I_3|>0$. Имеем

$$
p\left(\cap\limits_{i\in I} \bar{A_i}\right)\ge
p\left(\cap_{i\in I_2\cup I_3} \bar{A_i}\right)(1-x_k)
\ge p\left(\cap_{i\in I_2} \bar{A_i}\right)(1-x_k)\prod_{j\in I_3} (1-x_j),
$$
что и требовалось (здесь первое неравенство уже доказано, а второе
следует из индукционного предположения).

Доказательство леммы таким образом завершено.

\textbf{Замечание}. Как видно из доказательства, вместо независимости
каждого события $A_i$ от событий, не входящих в $N_+(A_i)$
достаточно требовать для любого множества $I$ такого, что
$I\cap (N_+(A_i)\cup \{i\})=\emptyset$ оценки
$$
p\left(A_i|\cap_{j\in I} A_j\right)\le x_i\prod_{j\in N_+(A_i)} (1-x_j).
$$

Иногда используется именно такая версия локальной леммы.

В случае, когда оценки на вероятности всех событий совпадают,
получаем следующее утверждение, известное как

\textbf{Симметричная версия локальной леммы}. Предположим, что
$ep(d+1)\le 1$, каждое событие $A_i$ происходит с вероятностью
не больше, чем $p$ и исходящая степень каждого события в орграфе
зависимостей не больше $d$. Тогда с положительной вероятностью ни
одно событие $A_i$ не происходит.

\textbf{Доказательство}. Выберем $x_i=x=1/(d+1)$.
Тогда $(1-x)^d\ge 1/e$ --- это следует, например, из определения
числа $e$. Тогда $p\le x(1-x)^d$, так что выполняются условия локальной
леммы.

\vskip 0.2 cm

Перейдем к применениям локальной леммы.


\textbf{Предложение.} Пусть $G$ --- граф, степени всех которого не больше $d$,
$P_i$ --- непересекающиеся подмножества множества вершин графа
$G$ такие, что $|P_i|>2ed$. Тогда можно выбрать в каждом $P_i$
по вершине так, что никакие две соединенные ребром
вершины не выбраны.

\textbf{Доказательство}. Уменьшим при необходимости некоторые $P_i$ так,
чтобы для всякого $i$ было $|P_i|=k:=[2ed]+1$. Будем выбирать
вершины $x_i\in P_i$ случайно и независимо. Каждому ребру
$e=v_1-v_2$ графа $G$ сопоставим \emph{событие} $A_e$: оба конца $v_1$, $v_2$
этого ребра выбраны.
Очевидно, что вероятность каждого такого события не больше, чем $1/k^2$.
В случае, если концы ребра принадлежат одному и тому же $P_i$ или
один из них не принадлежит ни одному $P_i$, вероятность равна 0
и такие события мы далее не рассматриваем.
Для ребра $e=v_1-v_2$, для которого, скажем $v_1\in P_1$, $v_2\in P_2$,
рассмотрим все ребра, выходящие из вершин множеств $P_1$ и $P_2$.
Всего будет не более, чем $2kd-2$ таких ребер (не считая ребра $e$).
Заметим, что событие $A_e$ не зависит от всех других событий типа
$A_{e'}$, где $e'$ --- ребро, соединяющее вершины множеств, отличных
от $P_1$ и $P_2$. Таким образом, для применения симметричной версии
локальной
леммы достаточно проверить, что $e(2kd-1)/k^2<1$, что имеет место.

\textbf{Пример}. Пусть за круглым столом сидит по сто представителей
каждой из $n$ стран. Тогда можно выбрать в каждой
стране по представителю так, чтобы никакие двое выбранных не сидели рядом.

Покажем, как локальная лемма может
применяться для нижней оценки чисел Рамсея.

Попробуем доказать, что при некотором --- желательно
как можно большем --- $k$
при некоторой покраске ребер полного графа на $k$ вершинах
в красный и синий цвета не найдется ни синего треугольника,
ни красного полного подграфа на $n$ вершинах
(это будет означать, что $R(3,n)\ge k$).

Будем красить ребро в синий цвет с вероятностью $p$
и в красный с вероятностью $1-p$.
Для каждого треугольника рассмотрим событие ``все его ребра синие'',
а для каждых $n$ вершин событие ``все ребра между этими вершинами красные''.
Мы хотим, чтобы  с положительной вероятностью ни одно
из этих событий не произошло. Попробуем применить
локальную лемму. Заметим, что два события зависимы,
если соответствующие множества из трех либо $n$
вершин пересекаются хотя бы по двум элементам.
Так что каждое ``синее'' событие зависит не больше
чем от $3(k-3)$ синих и $C_k^n$ красных (последнее число можно
чуть уменьшить, но пользы такое улучшение не принесет), каждое
красное --- не более чем от $n^2k/2$ ``синих'' и $C_n^k$
красных. Теперь для применения локальной леммы следует
найти числа $x_i=x$ и $y_i=y$ такие, что

$$
p^3\le x(1-x)^{3k} (1-y)^{C_k^n},\,
(1-p)^{C_n^2}\le y (1-x)^{n^2k/2} (1-y)^{C_k^n}.
$$

Утомительное вычисление показывает, что следует брать
$p=c_1 k^{-1/2}$, $n=c_2\sqrt{k} \log k$, $x=c_3 k^{-3/2}$,
$y=c_4 e^{-\sqrt{n} \log^2 n}$.

Это дает оценку $R(3,n)>c n^2/\log^2 n$. В действительности
$R(3,n)$ растет как $c n^2/\log n$, что было выяснено
в результате многолетнего труда многих математиков.

Перейдем к следующему сюжету. Он интересен тем,
что локальная лемма для установления результата применяется
дважды в совершенно различных ситуациях.

\emph{Линейным лесом} назовем граф, каждая компонента связности
которого есть простая цепь. \emph{Линейная древесность} $\la(G)$
графа $G$ есть наименьшее количество линейных лесов, покрывающих
все ребра графа $G$.

\emph{Гипотеза линейной древесности} (Akiyama, Exoo и Harary, 1981)
утверждает, что линейная древесность любого $d$-регулярного графа равна
$[d/2]+1$.

Нижняя оценка очевидна, трудность состоит в том, чтобы покрыть
ребра любого $d$-регулярного графа таким количеством линейных лесов.

Нам понадобится ориентированная версия гипотезы линейной
древесности. Ориентированный граф называется линейным лесом, если
каждая его компонента (слабой) связности есть ориентированная цепь.
Рассмотрим ориентированный граф, в котором степени исходя и захода
каждой вершины равны $d$ --- такие
орграфы будем называть $d$-регулярными.
\emph{Ориентированная гипотеза линейной древесности}
утверждает, что ребра $d$-регулярного орграфа
можно покрыть $d+1$ линейным лесом (легко видеть, что
меньшим количеством линейных лесов не обойтись).

Назовем ориентированным обхватом орграфа длину наименьшего
ориентированного цикла в этом орграфе.

Для графов с большим ориентированным обхватом ориентированная
гипотеза линейной древесности устанавливается в следующем утверждении:

\textbf{Теорема}. Если ориентированный обхват $g$
$d$-регулярного орграфа $G$ удовлетворяет неравенству
$g> 8ed$, то $\la(G)=d+1$, то есть для
такого графа выполняется ориентированная версия гипотезы
линейной древесности.

\textbf{Доказательство}. Мы воспользуемся
тем известным фактом, что ребра орграфа
$G$ можно разбить на $d$ непересекающихся
подмножеств $M_1$, $M_2,\dots,M_d$ так, что
для всякого $i$ ребра подмножества $M_i$
образуют 1-регулярный подграф (то есть $M_i$
есть дизъюнктное объединение циклов). [Это следует, например,
из леммы о девушках. Рассмотрим неориентированный
двудольный граф, доли которого есть две копии
множества вершин графа $G$. Проведем ребро
между вершиной $a$ первой доли и вершиной $b$ второй доли,
если в графе $G$ было ребро из $a$ в $b$. Получим $d$-регулярный
двудольный граф. Для него выполняются условия леммы о девушках,
так что найдется совершенное паросочетание. В графе $G$
оно соответствует 1-регулярному подграфу. Дальше по индукции.]

Каждый цикл в каждом $M_i$ содержит по предположению больше,
чем $8ed$ вершин. Рассмотрим граф ребер нашего орграфа, в котором
вершинами будут ребра орграфа, и соединены будут смежные ребра.
Ясно, что он будет $(4d-2)$-регулярным. отсюда применяя доказанное
несколько выше предложение получаем, что можно во всех этих циклах
выбрать по ребру так, чтобы не было смежных выбранных ребер.
Определим $M_{d+1}$ как (вообще говоря, неполное)
паросочетание, образованное этими циклами. Переопределяя
$M_i:=M_i\setminus M_{d+1}$ для $i=1,2,\dots,d$
получаем требуемое покрытие ребер графа $G$ линейными лесами
в количестве $d+1$.

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

\textbf{Утверждение}. Пусть $10\sqrt{d}<p<20\sqrt{d}$. Тогда
существует такая раскраска $f:\ V(G)\rightarrow \{1,2,\dots,k\}$
вершин графа $G$ в цвета $1,\,2,\dots,k$,
для которой соседи всякой вершины окрашены ``равномерно'' ---
а именно, $|N_+(v)\cap f^{-1}(i) -d/p|<10\sqrt{d/p}\log d$
и аналогично для $N_(v)$ при всех $v\in V(G)$.

Доказательство основано на том, что при случайной раскраске
указанные события очень вероятны для каждой вершины и при этом
слабо зависимы в смысле локальной леммы. Подробности опускаются.

Выберем в указанном интервале $[10\sqrt{d},20\sqrt{d}]$
простое $p$.
Обозначим за $E_i$ множество тех ориентированных ребер $v_1-v_2$
графа $G$, для которых $f(v_2)-f(v_1)\equiv i$ по модулю $p$.

Заметим, что при $i\ne 0$ все ориентированные циклы в графе,
образованном ребрами $E_i$, имеют длину, кратную $p$. Легко видеть,
что выполняются условия на большой ориентированный обхват,
так что для каждого $i\ne 0$ покроем соответствующие ребра
не более чем $d/p+10\sqrt{d/p}\log d+1$ линейными лесами,
при $i=0$ покроем ребра множества $E_0$ $2d/p+o(d/p)$
линейными лесами (например, так: покроем $d/p+o(d/p)$
1-регулярными графами, каждый из которых разделим на два линейных
леса).

Получим покрытие всех ребер графа $G$ линейными лесами
в количестве $d+o(d)$.














\end{document}
