City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Вероятностный метод: средние
Lovasz local lemma and probabilistic method

What: Lecture
When: Saturday, 28 February 2015, 17:20–18:55
Where: ПОМИ РАН

Description

Вероятностный метод: средние

Если среднее (математическое ожидание) больше $\alpha$, то некоторые значения больше $\alpha$

  • Если сумма десяти чисел больше $100$, то сумма некоторых трёх из них больше $30$
  • Вариант: если у дерева $1500$ листьев, можно оборвать $800$ из них так, чтобы осталось не меньше $7/15$ тени. (С какой-то из московских олимпиад, кажется.)
  • Та же задача, если числа стоят по кругу и нужна сумма трёх соседних
  • Любой граф с $E$ рёбрами можно разрезать на две части так, чтобы в разрез попало не меньше $E/2$ рёбер
  • В клетках шахматной доски написаны числа, сумма положительна. Докажите, что можно расставить ладьи, не бьющие друг друга, чтобы сумма была положительной
  • Для любой 3-кнф можно удовлетворить не менее $7/8$ дизъюнктов
  • Поверхность тела меньше $4$; докажите, что можно его повернуть так, чтобы тень была не больше $1$ (на экране, перпендикулярном направлению света)
  • Фигуру площади $n$ можно поместить на клетчатой бумаге так, чтобы она покрыла не менее $n$ узлов, а можно так, чтоб не больше $n$ узлов

Вероятностный метод: оценка суммы

Если сумма вероятностей событий меньше $1$, то иногда ни одного из них не происходит.

  • В окружность, где не более $30\%$ грязные, можно вписать правильный треугольник с чистыми вершинами. (Рассуждение со средними и с вероятностью.)
  • В сферу, где не больше $10\%$ поверхности грязные, можно вписать куб с чистыми вершинами
  • Числа Рамсея
    • $R(k,l)$: сколько вершин нужно в графе, чтобы гарантировать или независимое множество из $k$, или клику из $l$;
    • оценка $R(3,3)=6$;
    • верхняя оценка $R(k,l)\le R(k-1,l)+R(k,l-1)$
    • оценка $R(n,n)\le 2^{2n}$ (биномиальные коэффициенты)
    • нижняя оценка: случайный граф
    • оценка вероятности
    • пересказ в виде оценки количеств
    • пересказ в виде сжатия: если в графе из $n$ вершин есть монохроматический граф размера $k$, то можно вместо $k(k-1)/2$ битов обойтись $1+k\log n$ битами, получаем выигрыш при $k>\log n/2$ (примерно)
  • Обход лабиринта на шахматной доске: существует последовательность команд (влево, вправо, вверх, вниз), при исполнении которой (невыполнимые команды пропускаются) мы обойдём доступную часть любого лабиринта на доске $8\times 8$ (при любом начальном положении).
    • есть такое $N$, что вероятность обхода за $N$ случайных шагов положительна (для всех досок) --- не меньше $\varepsilon$;
    • вероятность не обойти (данный лабиринт с данным началом) за $N$ шагов не больше $(1-\varepsilon)$;
    • вероятность не обойти (данный лабиринт с данным началом) за $kN$ шагов не больше $(1-\varepsilon)^k$;
    • при большом $k$ произведение $(1-\varepsilon)^k$ на число лабиринтов будет меньше $1$.
  • Монотонная схема полиномиального размера и логарифмической глубины для функции majority:
    • Постановка задачи: схемы, глубина, размер, монотонные схемы, универсальность, монотонная универсальность.
    • Достаточно логарифмической глубины
    • Схема: дерево с элементами $\mathrm{MAJ}_3$ логарифмической глубины и случайными переменными на листьях
    • Оценка вероятности: функция $p\mapsto 3p^2-2p^3$ и её итерации. $O(\log n)$ шагов, чтобы отойти от середины; $O(1)$ шагов чтобы дойти до края; $O(\log n)$ чтобы сойтись к краю на расстояние $2^{-n}$

Video