Банк задач по математике

Задача 6.3.1

(1)(2)

Если в графе $G=(V,E)$ с $n$ вершинами минимальная степень вершины равна $\delta$ , то

?

(1)

для любого $p\in (0,1)$ существует такое множество вершин $A\subset V$ , что в объединении $A$ и множества всех вершин, не соединённых ни с какой вершиной из $A$ , имеется не более $np+n(1-p)^{\delta +1}$ вершин;

(2)

существует такое множество вершин $D\subset V$ , что любая вершина из $V\setminus D$ соединена ребром с некоторой вершиной из $D$ и $\left|D\right|\leqslant n\dfrac {1+\ln (\delta +1)}{\delta +1}$ .

Для решения следующих задач 6.3.2 и 6.3.3 (3) нужна приведённая ниже теория. К их решению разумно вернуться после задачи 6.3.9.

Примечание.

?

Зафиксируем $p\in (0,1)$ и назовем вероятностью графа (в модели, или в вероятностном пространстве, Эрдёша--Реньи) с $n$ вершинами $\left\{ 1,2,\ldots ,n\right\}$ и $r$ рёбрами число $\mathbb {P}\left(G\right)=\mathbb {P}_{p}\left(G\right) := p^r(1-p)^{\frac{n(n-1)}{2}-r}$ . Вероятностью семейства (или, что то же самое, свойства) графов с вершинами $1,2,\ldots ,n$ называется сумма вероятностей входящих в него графов.

Случайной величиной называется функция, определённая на множестве графов с вершинами $1,2,\ldots ,n$ .

Например, количество рёбер графа — случайная величина.

Пусть случайная величина $Y$ принимает $k$ различных значений $y_1,\ldots ,y_k$ . Тогда математическим ожиданием (мат.ожиданием) случайной величины $Y$ называется её <<взвешенное среднее>>

\mathbb {E}\left[Y\right] := \sum _{s=1}^{k}y_s\mathbb {P}\left(Y^{-1}(y_s)\right),

где $Y^{-1}(y_s)$ — множество всех графов $G$ , для которых $Y(G)=y_s$ . Последнюю вероятность обозначают $\mathbb {P}\left(Y=y_s\right)$ .

Задача 6.3.2

(1)(2)

?

(1)

Если $\dbinom {k}{m}p^{\binom {m}{2}}+\dbinom {k}{n}(1-p)^{\binom {n}{2}} < 1$ для некоторого $p\in (0,1)$ , то $R(m,n) > k$ (здесь $R(m,n)$ — числа Рамсея, см. п. 4.1).

(2)

$R(4,n) \geqslant \Omega \left(\dfrac {n^2}{\ln^2 n}\right)$ (мы пишем $g \geqslant \Omega (f)$ , если $f=O(g)$ ).

Задача 6.3.3

(1)(2)(3)

?

(1)

Cherchez la femme. На русско-французской встрече не было представителей других стран. Суммарное количество денег у французов оказалось больше суммарного количества денег у русских, и суммарное количество денег у женщин оказалось больше суммарного количества денег у мужчин. Обязательно ли на встрече была француженка?

(2)

Денежные купюры разного достоинства и разных стран упакованы в два чемодана. Средняя стоимость купюры равна 100 рублям. Общее число купюр в левом чемодане больше, чем в правом. Обязательно ли в левом чемодане найдётся купюра стоимостью не более 200 рублей? (Ср. с неравенством Маркова 6.3.9 (1).)

(3)

Для любых целых $l,q>0$ существует граф, не содержащий обходов длины менее $l$ и который невозможно правильно раскрасить в $q$ цветов. (См. определение правильности раскраски в п. 3.1.)

Задача 6.3.4

Для данных $n$ и $p$ вероятность наличия $k$ вершин, между которыми нет рёбер, меньше $e^{k\ln n - pk(k-1)/2}$ .

?

Задача 6.3.5

Для данных $n$ и $p$ найдите мат.ожидание количества

?

(1)

изолированных вершин;

(2)

треугольников;

(3)

$k$ -клик;

(4)

$k$ -клик, являющихся компонентами связности;

(5)

гамильтоновых циклов;

(6)

несамопересекающихся циклов длины $k$ ;

(7)

несамопересекающихся циклов длины $k$ , являющихся компонентами связности с ровно $k$ рёбрами;

(8)

деревьев с $k$ вершинами;

(9)

древесных компонент данного размера $k$ , т.е. деревьев с $k$ вершинами, являющихся компонентами связности.

Задача 6.3.6

Для данного $p$ найдите асимптотику (при постоянном $k$ и $n\to \infty$ ) функции $\mathbb {E}_{(k)}\left[Y\right] := \mathbb {E}\left[Y(Y-1)\ldots (Y-k+1)\right]$ (т.е. $k$ -го факториального момента), если $Y$ — число изолированных вершин.

?

Задача 6.3.7

(1)(2)

Для данных $n$ и $p$ найдите дисперсию количества

?

(1)

изолированных вершин;

(2)

треугольников.

Задача 6.3.8

(1)(2)

Докажите, что для любых случайных величин $X$ и $Y$ выполнены следующие свойства:

?

(1)

$\mathbb {E}\left[X+Y\right] = \mathbb {E}\left[X\right]+\mathbb {E}\left[Y\right]$ ;

(2)

$\operatorname {Var}\left[X+Y\right] = \operatorname {Var}\left[X\right]+\operatorname {Var}\left[Y\right]$ , если $X$ и $Y$ независимы (т.е. для любых $x,y$ выполнено $\mathbb {P}\left(X=x,Y=y\right)=\mathbb {P}\left(X=x\right)\cdot \mathbb {P}\left(Y=y\right)$ ).

Задача 6.3.9

(1)(2)

Пусть $X$ — случайная величина (определённая перед задачей 6.3.4) и $a>0$ .

?

(1)

Неравенство Маркова. $\mathbb {P}\left(\left|X\right|>a\right) \leqslant \mathbb {E}\left[\left|X\right|\right]/a$ . (Ср. с задачей 6.3.3 (1).)

(2)

Неравенство Чебышёва. $\mathbb {P}\left(\left|X-\mathbb {E}\left[X\right]\right|>a\right) \leqslant \operatorname {Var}\left[X\right]/a^2$ .

Событие $A_n$ происходит асимптотически почти наверное (или с асимптотической вероятностью 1) относительно последовательности $f(n)$ , если $\mathbb {P}_{f(n)}\left(A_n\right) \to 1$ . Общепринятое сокращение: при $p(n)=f(n)$ событие $A_n$ происходит а.п.н. (формально, эта фраза не имеет смысла, поскольку означает <<если $p(n)=f(n)$ , то событие $A_n$ происходит а.п.н.>>, а без указания последовательности $f(n)$ фраза <<событие $A_n$ происходит а.п.н.>> не может быть определена как надо).

Напомним, что здесь $n$ — число вершин графа.

Задача 6.3.10

(1)(2)(3)(4)

При $p(n)=1/(2n)$

?

(1)

а.п.н.имеется более $n/2$ изолированных вершин;

(2)

для некоторого $C>0$ а.п.н.каждая компонента связности имеет менее $C\ln n$ вершин (специалисты говорят: менее $O(\ln n)$ вершин);

(3)

а.п.н.каждая компонента связности является деревом или уницикличным графом;

(4)

для некоторого $C>0$ а.п.н.имеется менее $C$ уницикличных компонент.

Задача 6.3.11

(1)(2)

?

(1)

При $p(n)=o(n^{-3/2})$ а.п.н.рёбра попарно не пересекаются.

(2)

При $p=p(n)=o(n^{-3/2})$ и $pn^2\to \infty$ существует такая функция $r=r(n)=o(pn^2)$ , что а.п.н.число вершин степени 1 больше $pn^2-r$ и меньше $pn^2+r$ , а степени всех остальных вершин равны нулю.

Задача 6.3.12

Если $c>1$ ( $0<c<1$ ), то при $p(n)=c\ln n/n$ а.п.н.случайный граф связен (несвязен).

?

(1)

(2)

(3)

(4)

(5)

Примечание.

?

Приведём результат [B, с.100, теорема 5.4]. Пусть $p_n=p(n)$ . Для $k\geqslant 2$ обозначим через $T_k=T_{k,p_n}$ число компонент связности в случайном графе, являющихся деревьями с $k$ вершинами.

(1)

Если $p_n=o(n^{-k/(k-1)})$ , то а.п.н. $T_k=0$ .

(2)

Если $\lim_{n\to \infty }p_nn^{k/(k-1)}=c>0$ , то последовательность случайных величин $T_k=T_{k,p_n}$ сходится при $n\to \infty$ к случайной величине, имеющей распределение Пуассона с параметром $\lambda := c^{k-1}k^{k-2}/k!$ , т.е. для любого $s\in \mathbb {Z}$ , $s\geqslant 0$ , $\lim_{n\to \infty }\mathbb {P}\left(T_k=s\right)=\dfrac {\lambda^s}{s!}e^{-\lambda }$ .

(3)

Если $n^{k/(k-1)}=o(p_n)$ и $\lim_{n\to \infty }(p_nkn-\ln n-(k-1)\ln \ln n)=-\infty$ , то $\lim_{n\to \infty }\mathbb {P}\left(T_k\geqslant L\right)=1$ для любого $L>0$ .

(4)

Если $\lim_{n\to \infty }(p_nkn-\ln n-(k-1)\ln \ln n)=x\in \mathbb {R}$ , то последовательность случайных величин $T_k=T_{k,p_n}$ сходится при $n\to \infty$ к случайной величине, имеющей распределение Пуассона с параметром $\lambda := e^{-x}/(k\cdot k!)$ .

(5)

Если $\lim_{n\to \infty }(p_nkn-\ln n-(k-1)\ln \ln n)=+\infty$ , то а.п.н. $T_k=0$ .

Задача 6.3.13

(1)(2)

?

(1)

Найдите хотя бы одну такую функцию $p^*(n)$ , что

при $p(n)/p^*(n)\to 0$ а.п.н.граф не содержит треугольника,
при $p(n)/p^*(n)\to +\infty$ а.п.н.граф содержит треугольник.

(2)

То же с заменой треугольника на подграф, изоморфный $K_4$ .

Примечание.

?

Такая функция $p^*$ называется пороговой вероятностью. Пороговая вероятность существует для любого монотонного семейства графов. Монотонно возрастающим (убывающим) семейством графов называется такое семейство графов, которое вместе с каждым графом содержит любой его надграф (подграф).

Задача 6.3.14

(1)(2)(3)

Хроматическое число графа а.п.н.не больше

?

(1)

одного при $p(n)=o(1/n^2)$ ;

(2)

двух при $p(n)=o(1/n)$ ;

(3)

трёх при $p(n)=c/n$ , где $c<1$ .

Задача 6.3.15

(1)(2)

?

(1)

Жадный алгоритм раскраски (см.задачу 3.2.3: вершины графа перебираются в некотором порядке, и каждой присваивается наименьший цвет, не встречающийся среди уже раскрашенных соседей) для любого положительного $\varepsilon$ а.п.н.(при $p(n)=1/2$ ) ошибается не более чем в $2+\varepsilon$ раз.

(2)

Для любых $\varepsilon ,\delta >0$ существует такая последовательность $G_n$ графов с $n$ вершинами, что при случайной нумерации вершин графа $G_n$ (т.е. для вероятности каждой нумерации, равной $1/2$ ) вероятность того, что отношение числа цветов в жадной раскраске к $\chi (G_n)$ больше $n^{1-\varepsilon }$ , больше $\delta$ . (Иными словами, с одной стороны, почти для любого графа в любой нумерации жадная раскраска хороша, но, с другой стороны, есть графы, которые почти как ни нумеруй, а всё дрянь получится!)

Примечание.

?

См.подробнее [R3, R4, R5]. В частности, в [R4] доказаны следующие результаты.

Первая теорема Боллобаша. Существует последовательность $f_n = o\left(\dfrac {n}{2\log_2 n}\right)$ , для которой при $p(n) = 1/2$ а.п.н. $\left|\chi (G) - \dfrac {n}{2\log_2 n}\right| < f_n$ . (Эта теорема обобщается на практически любые значения $p$ [JLR].)

Вторая теорема Боллобаша. Для любого $\alpha > 2/3$ существуют последовательности $a_n$ и $b_n$ , для которых при $p(n) = n^{-\alpha }$ а.п.н. $\chi (G) \in \left\{ a_n, b_n\right\}$ . (В этой теореме для некоторых $\alpha$ последовательности $a_n$ и $b_n$ могут быть выбраны так, что $\lim_{n \to \infty } a_n = \lim_{n \to \infty } b_n = \infty$ .)

Случайные графы