Файл: Элементы комбинаторики.pdf

подмножеств?
5.1.3.
Теорема Эрдеша—Ко—Радо. Пусть F — любое семейство k- элементных подмножеств n-элементного множества.
(a) Если 2k
6 n и любые два подмножества из F пересекаются,
то |F| 6
(
n
− 1
k
− 1
)
(b) Если 2k
> n и объединение никаких двух подмножеств из F
не есть все n-элементное множество, то |F| 6
(
n
− 1
k
)
5.1.4.
Любое семейство из двадцати 5-элементных подмножеств 15- элементного множества можно так разбить на 6 подсемейств, чтобы любые два непересекающихся подмножества лежали бы в разных подсемействах.
Замечание. В таких ситуациях (см. §7.1) обычно вместо разби- ении на подсемейства говорят о раскраске в разные цвета. Тогда вопреки наглядному представлению о раскраске красятся множе- ства, но при этом не красятся их элементы.
5.1.5.
Для l < k обозначим через M(n, k, l) минимальное количе- ство таких k-элементных подмножеств множества R
n
, что любое l
-элементное подмножество множества R
n целиком содержится хо- тя бы в одном из них. Например, задача 1.6.2.a утверждает, что
M (n, k, l)
>
(
n l
)
/
(
k l
)

6. АНАЛИТИЧЕСКИЕ И ВЕРОЯТНОСТНЫЕ МЕТОДЫ
153 6 Аналитические и вероятностные методы
6.1 Асимптотики
Если не оговорено противное, то o, O (рукописные обозначе- ния: o, O), асимптотики и пределы рассматриваются при n → ∞.
Запись f(n) ≪ g(n) означает, что f(n) = o(g(n)), т.е. lim n
→∞
f (n)
g(n)
= 0
Запись f(n)
& g(n) означает, что f(n) > (1 + o(1))g(n).
Найти асимптотику для функции f(n) означает найти «явную»
функцию a(n), для которой lim n
→∞
f (n)
a(n)
= 1 6.1.1.
Найдите асимптотику для
(a,b,c) сумм из задачи 1.1.6;
(d) количества A
n подмножеств множества {1, 2, . . . , n}, не содер- жащих двух подряд идущих чисел;
(e)* То же, что в (d), для трёх подряд идущих чисел.
В ответе можно использовать функцию x
P
(a, b)
, которая по числам a, b и многочлену P , имеющему единственный корень на отрезке
[a, b]
, выдает этот корень.
6.1.2.
Найдите асимптотику наибольшего количества рёбер в графе с n вершинами, не содержащем k-клики. Здесь k = k n
= o(n)
6.1.3.
Докажите следующие соотношения, предполагая в асимпто- тиках, что n → ∞, а k фиксировано. (Число ex
H
(n)
определено в задаче 2.7.6.)
(a) ex
P
k
(n)
&
k
−2 2
n
. (b) ex
C
2k+1
(n)
&
n
2 4
. (c) ex
K
1,k
(n)
∼
k
−1 2
n
Замечание. Знаменитая теорема Эрдеша-Стоуна-Шимоновича утверждает, что для любого фиксированного H такого, что χ(H) >
2
, при n → ∞ выполнено ex
H
(n)
∼
n
2 2
χ(H)
− 2
χ(H)
− 1
. (Для двудольных
H
известно лишь, что ex
H
(n) = o(n
2
)
.) То есть, если мы запрещаем графу иметь некоторый фиксированный подграф H, то доля рё- бер, которые при этом можно провести, среди всевозможных рёбер определяется хроматическим числом графа H. Удивительно, что

154
Элементы дискретной математики в задачах хроматическое число возникает в этой задаче! Доказательство тео- ремы можно прочесть по ссылке [1]. (Этой теоремой нельзя поль- зоваться при решении задачи 6.1.3.b.)
6.1.4.
(a) n
2
(
2 +
1
n
)
n
= (2+o(1))
n
. По определению, это означает,
что существует функция ψ(n) = o(1), для которой n
2
(
2 +
1
n
)
n
=
(2 + ψ(n))
n
; или, что то же самое,
n
√
n
2
(
2 +
1
n
)
n
− 2 = o(1).
(b) 3
√
n
(
2 +
1
n
)
n
= (2 + o(1))
n
6.1.5.
(a) Найдите асимптотику для n
√(
n
[n/2]
)
(ср. с задачами
1.4.3.b и 6.1.10.b).
(b)
2
n n + 1
<
(
n
[n/2]
)
< 2
n
(c) Найдите асимптотику для m
√(
3m m
)
(d)
3 3m
3m + 1
< 2 2m
(
3m m
)
< 3 3m
(e)
(
n
[an]
)
= (a
−a
(1
− a)
a
−1
+ o(1))
n
(f)
n!
[a
1
n]! . . . [a s
n]!
=
(e
−a
1
ln a
1
−...−a s
ln a s
+ o(1))
n
,
где a
1
+ . . . + a s
= 1 6.1.6.
(a) Найдите асимптотику для ln(n!).
(b) Найдите асимптотику для n
√
n!
(c) n n
e
−n+1 6 n! 6 n n+1
e
−n+1
;
(d) n!
6 n n
e
−n+1
√
n
(e)* Формула Стирлинга. n! ∼ n n
e
−n
√
2πn
, т. е. lim n
→∞
n!
n n
e
−n
√
2πn
=
1 6.1.7.
(a)
(
n k
)
<
n k
k!
(b) ln
(n
− 1)(n − 2) . . . (n − k)
n k
=
−
k(k + 1)
2n
(
1 + O
(
k n
))
для k =
k n
< n/2
. Это означает, что существует функция ψ(n) = O
(
k n
)
, для

6. АНАЛИТИЧЕСКИЕ И ВЕРОЯТНОСТНЫЕ МЕТОДЫ
155
которой ln
(n
− 1)(n − 2) . . . (n − k)
n k
=
−
k(k + 1)
2n
(1 + ψ(n))
;
или, что то же самое, −1 −
2n k(k + 1)
ln
(n
− 1)(n − 2) . . . (n − k)
n k
=
O
(
k n
)
(c)
(
n k
)
=
n k
k!
e
−
k(k
−1)
2n
+O(k
3
/n
2
)
для k = k n
< n/2
(Сформулируйте сами, что здесь означает e
−
k(k
−1)
2n
+O(k
3
/n
2
)
.)
(d)
(
n k
)
∼
n k
k!
для k = k n
= o(
√
n)
Неформально, это означает, что для k ≪
√
n вероятность выпа- дения ровно k орлов при n подбрасываниях монеты приближенно равна n
k k!
2
−n
. В неформальном замечании к этому и следующему пунктам достаточно интуитивного понимания того, что такое веро- ятность.
(e)
(
2n n
− k
)
/
(
2n n
)
= e
−
k2
n
(1+o(1))
для k = k n
= o(n)
(Сформулируйте сами, что здесь означает e
−
k2
n
(1+o(1))
.)
Неформально, это означает, что для k ≪ n вероятность P
k выпаде- ния ровно n−k орлов при 2n подбрасываниях монеты приближенно равна P
0
e
−k
2
/n
(нормальное распределение).
6.1.8.
(a) Верно ли, что записи e o(n)
и o (e n
)

«равнозначны»?
т. е., верно ли, что для любой функции f : Z → (0, +∞) условия lim n
→∞
ln f (n)
n
= 0
и lim n
→∞
f (n)e
−n
= 0

равносильны?
(b) Подберите функции f, g : Z → (0, +∞) такие, что f(n) ∼ g(n),
но e f (n)
̸= O(e g(n)
)

(c) Могут ли функции f, g : Z → (0, +∞) одновременно удовле- творять соотношениям f(n) = o(g(n)) и g(n) = o(f(n))?
(d) Могут ли функции f, g : Z → (0, +∞) одновременно удовле- творять соотношениям f(n) = O(g(n)) и g(n) = O(f(n))?

(e) Следует ли из двух соотношений из (d), что f(n) ∼ g(n)?
6.1.9.
(a) Какая функция растет быстрее: x
(x x
)
или (x!)
(2
x
)
? т. е.
найдите lim x
→∞
x
(x x
)
(x!)
(
−2
x
)

156
Элементы дискретной математики в задачах
(b) Существует ли функция ψ(n) = o(1), для которой
(2 + ψ(n))
n
2
−n e
−
√
n
→ ∞?
(Как в любой математической задаче, нужно обосновать ответ: при- вести пример такой функции или доказать её существование или доказать, что такой функции не существует.)
В задачах 6.1.10.bcde и 6.1.11.cef, в отличие от остальных, можно пользоваться без доказательства формулой Стирлинга 6.1.6.e.
6.1.10.
Найдите асимптотику для
(a) ln
(
n
2
n
)
;
(b)
(
n
[n/2]
)
(c)
(
n
2
n
)
;
(d)*
(
n
[n
α
]
)
, α
∈ (0, 1);
(e) (2n−1)!! := (2n−1)·(2n−3)·. . .·3·1;
(f)
n
∑
k=0
(
n k
)
2
;
(g)*
n
∑
k=0
(
n k
)
4 6.1.11.
Найдите асимптотику функции s = s(n), заданной как
(a) s s
= n
;
(b) s s
3
= n
;
(c) s(n) := max{k | k! 6 n};
(d) s(n) := min
{
m
∈ N |
(
n m
)
< 2(
m
2
)
}
;
(e) s(n) := min {m ∈ N | 2
m
/m > n
} (функция 2
m
/m возникает как сложность реализации функций алгебры логики);
(f) s(n) := min
{
m
∈ N |
(
m
[m/2]
)
> n
}
(ср. с задачей 1.4.3.b).
6.1.12.
* В ответах можно использовать константы, заданные в виде суммы рядов. Найдите асимптотику для
(a) количества линейных подпространств в Z
n
2
(см. задачу 1.4.7 и определение перед ней);
(b) количества унициклических графов с n вершинами (см. задачу
2.2.5.b и определение перед ней).
6.2 Независимость и доказательства существования
Введение
Цель этого раздела — продемонстрировать метод доказатель- ства некоторых интересных комбинаторных результатов (пункты

174
Элементы дискретной математики в задачах доказательство вместо локальной леммы Ловаса использует ква- зислучайные графы, неравенства плотной концентрации и пр.
6.3 Случайные графы
Начнем с интересных задач, которые можно решить при помощи случайных графов. (Более простые решения без случайных графов неизвестны. Известны такие же или более сложные, и то не для всех задач.)
6.3.1.
Если в графе G = (V, E) с n вершинами минимальная сте- пень вершины равна δ, то
(a) Для любого p ∈ (0, 1) существует такое множество вершин A ⊂
V
, что в объединении A и множества всех вершин, не соединённых ни с какой вершиной из A, имеется не более np+n(1−p)
δ+1
вершин.
(b) Существует такое множество вершин D ⊂ V , что любая вер- шина из V \D соединена ребром с некоторой вершиной из D, и
|D| 6 n
1 + ln(δ + 1)
δ + 1
Для решения следующих задач 6.3.2 и 6.3.3.c нужна приведен- ная ниже теория. К их решению разумно вернуться после задачи
6.3.9.
6.3.2.
(a) Eсли
(
k m
)
p(
m
2
) +
(
k n
)
(1
− p)(
n
2
) < 1 для некоторого p ∈
(0, 1)
, то R(m, n) > k.
(b)* R(4, n)
> Ω
(
n
2
ln
2
n
)
(мы пишем g
> Ω(f), если f = O(g)).
6.3.3.
(a) Cherchez la femme. На русско-французской встрече не было представителей других стран. Суммарное количество денег у французов оказалось больше суммарного количества денег у рус- ских, и суммарное количество денег у женщин оказалось больше суммарного количества денег у мужчин. Обязательно ли на встре- че была француженка?
(b) Денежные купюры разного достоинства и разных стран упако- ваны в два чемодана. Средняя стоимость купюры равна 100 рублей.

6. АНАЛИТИЧЕСКИЕ И ВЕРОЯТНОСТНЫЕ МЕТОДЫ
175
Общее число купюр в левом чемодане больше, чем в правом. Обяза- тельно ли в левом чемодане найдется купюра стоимостью не более
200 рублей? (Ср. с неравенством Маркова 6.3.9.a.)
(c) Для любых целых l, q > 0 существует граф, не содержащий об- ходов длины менее l и который невозможно правильно раскрасить в q цветов. (См. определение правильности раскраски в §3.1.)
Зафиксируем p ∈ (0, 1) и назовем вероятностью графа (в моде- ли, или в вероятностном пространстве, Эрдеша-Реньи) c n вершина- ми {1, 2, . . . , n} и e рёбрами число P(G) = P
p
(G) := p e
(1
−p)
n(n
−1)
2
−e
Вероятностью семейства (или, что то же самое, свойства) графов с вершинами 1, 2, . . . , n называется сумма вероятностей входящих в него графов.
Случайной величиной называется функция, определённая на мно- жестве графов c вершинами 1, 2, . . . , n.
Например, количество рёбер графа — случайная величина.
Пусть случайная величина Y принимает k различных значе- ний y
1
, . . . , y k
. Тогда математическим ожиданием (мат. ожида- нием) случайной величины Y называется её «взвешенное среднее»
EY :=
k
∑
s=1
y s
P(Y
−1
(y s
))
, где Y
−1
(y s
)
– множество всех графов G, для которых Y (G) = y s
. Последнюю вероятность обозначают P(Y = y s
)
6.3.4.
Для данных n и p вероятность наличия k вершин, между которыми нет рёбер, меньше e k ln n
−pk(k−1)/2 6.3.5.
Для данных n и p найдите мат. ожидание количества
(a) изолированных вершин;
(b) треугольников;
(c) k-клик;
(d) k-клик, являющихся компонентами связности;
(e) гамильтоновых циклов;
(f) обходов длины k;
(g) обходов длины k, являющихся компонентами связности;
(h) деревьев с k вершинами;
(i) древесных компонент данного размера k, т.е. деревьев с k вер- шинами, являющихся компонентами связности.

176
Элементы дискретной математики в задачах
6.3.6.
Для данного p найдите асимптотику (при постоянном k и n
→ ∞) функции E
(k)
(Y ) :=
E (Y (Y − 1) . . . (Y − k + 1)) (т. е. k-го факториального момента), если Y — число изолированных вер- шин.
Дисперсией случайной величины X называется число DX :=
E(X − EX)
2 6.3.7.
Для данных n и p найдите дисперсию количества (a) изо- лированных вершин; (b) треугольников.
6.3.8.
(a) E(ξ + η) = Eξ + Eη;
(b) D(ξ + η) = Dξ + Dη, если ξ и η независимы.
6.3.9.
Пусть X — случайная величина (определенная выше) и a >
0
(a) Неравенство Маркова. P(|X| > a) 6 E|X|/a. (Ср. с задачей
6.3.3.a.)
(b) Неравенство Чебышева. P(|X − EX| > a) 6 DX/a
2
Событие A
n происходит асимптотически почти наверное (или с асимптотической вероятностью 1) относительно последователь- ности f(n), если P
f (n)
(A
n
)
→ 1. Общепринятое сокращение: при p(n) = f (n)
событие A
n происходит а.п.н. (формально, эта фраза не имеет смысла, поскольку означает «если p(n) = f(n), то собы- тие A
n происходит а.п.н.», а без указания последовательности f(n)
фраза «событие A
n происходит а.п.н.» не может быть определена как надо). Напомним, что здесь n — число вершин графа.
6.3.10.
При p(n) = 1/(2n)
(a) а.п.н. имеется более n/2 изолированных вершин.
(b) для некоторого C > 0 а.п.н. каждая компонента связности имеет менее C ln n вершин (специалисты говорят: менее O(ln n) вер- шин).
(c)* а.п.н. каждая компонента связности является деревом или уни- циклическим графом.
(d)* для некоторого C > 0 а.п.н. имеется менее C унициклических компонент.

6. АНАЛИТИЧЕСКИЕ И ВЕРОЯТНОСТНЫЕ МЕТОДЫ
177 6.3.11.
(a) При p(n) = o
(
n
−3/2
)
а.п.н. рёбра попарно не пересека- ются.
(b) При p = p(n) = o
(
n
−3/2
)
и pn
2
→ ∞ существует такая функ- ция 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 а.п.н. случайный граф связен (несвязен).
6.3.13.
(a) Найдите хотя бы одну такую функцию p
∗
(n),
что
• при p(n)/p
∗
(n)
→ 0 а.п.н. граф не содержит треугольника, и
• при p(n)/p
∗
(n)
→ +∞ а.п.н. граф содержит треугольник.
(b) То же с заменой треугольника на подграф, изоморфный K
4
Замечание. Такая функция p
∗
называется пороговой вероятно- стью. Пороговая вероятность существует для любого монотонно- го семейства. Монотонно возрастающим (убывающим) семейством графов называется такое семейство графов, которое вместе с каж- дым графом содержит любой его надграф (подграф).
6.3.14.
Хроматическое число графа а.п.н. не больше
(a) одного при p(n) = o(1/n
2
)
;
(b) двух при p(n) = o(1/n);
(c) трёх при p(n) = c/n, где c < 1.
6.3.15.
*
(a) Жадный алгоритм раскраски (см. задачу 3.2.3) для любого положительного ε а.п.н. ошибается не более чем в 2 + ε раз.
(b) Для любых ε, δ > 0 существует такая последовательность G
n графов с n вершинами, что при случайной нумерации вершин гра- фа G
n вероятность того, что отношение числа цветов в жадной рас- краске к χ(G
n
)
больше n
1
−ϵ
, больше δ. (Иными словами, с одной стороны, почти для любого графа в любой нумерация жадная рас- краска хороша, но, с другой стороны, есть графы, которые почти как ни нумеруй, а все дрянь получится!)
(Приведите аккуратные формулировки самостоятельно.)
Замечание. См. подробнее [R3, R4, R5]. В частности, в [R4] до- казаны следующие результаты.

7. АЛГЕБРАИЧЕСКИЕ МЕТОДЫ
195 7 Алгебраические методы
7.1 Линейно-алгебраический метод в комбинаторике
Напомним, что для множества F
F
n
:=
{(a
1
, a
2
, . . . , a n
) : a
1
, a
2
, . . . , a n
∈ F }.
Элементы этого множества называются векторами (или наборами или точками). Если F ∈ {Z
2
,
Z, Q, R}, то векторы можно покомпо- нентно складывать:
(x
1
, . . . , x n
) + (y
1
, . . . , y n
) := (x
1
+ y
1
, . . . , x n
+ y n
).
Если F ∈ {Z, Q, R}, то вектор можно покомпонентно умножить на число λ ∈ F :
λ(x
1
, . . . , x n
) := (λx
1
, . . . , λx n
).
(Это можно делать и для F = Z
2
, но не интересно.)
7.1.1.
Теорема о линейной зависимости.
(Z
2
) Среди любых n + 1 наборов длины n из нулей и единиц найдется несколько (не ноль) наборов, покомпонентная сумма по модулю два которых есть нулевой набор.
(Q) Для любых n + 1 векторов v
1
, . . . , v n+1
∈ Q
n найдутся ра- циональные числа λ
1
, . . . , λ
n+1
, не все равные нулю, для которых
λ
1
v
1
+ . . . + λ
n+1
v n+1
= (0, . . . , 0).
(R) Аналог теоремы (Q) справедлив для вещественных, ком- плексных и целых чисел.
Наборы из задач 7.1.1.(Z
2
),(Q) называются линейно зависимы- ми — над Z
2
и над Q соответственно. Линейная независимость
— отрицание линейной зависимости. Аналогично определяется ли- нейная (не)зависимость многочленов над Z
2
и Q соответственно.
(Эти и следующие понятия используются в формулировках задач
7.1.4.c, 7.1.5.c, 7.1.7.b и в решениях некоторых задач.)
Для F ∈ {Z
2
,
Z, Q, R} скалярное произведение F
n
× F
n
→ F
определяется формулой
(x
1
, . . . , x n
)
· (y
1
, . . . , y n
) := x
1
y
1
+ . . . + x n
y n

196
Элементы дискретной математики в задачах
Векторы x, y ∈ F
n называются ортогональными, если x · y = 0.
Расстояние между точками пространства R
n определяется фор- мулой
|(x
1
, . . . , x n
), (y
1
, . . . , y n
)
| :=
√
(x
1
− y
1
)
2
+ . . . + (x n
− y n
)
2
Линейным подпространством называется подмножество L ⊂
Q
n
, замкнутое относительно сложения векторов и умножения на рациональные числа. Линейное подпространство L называется n- мерным, если найдутся такие линейно независимые векторы v
1
, . . . , v n
∈ L, что любой вектор v ∈ L линейно выражается через данные векторы, т. е. найдутся числа λ
1
, . . . , λ
n
∈ Q, для которых v = λ
1
v
1
+. . .+λ
n v
n
. Число n называют размерностью пространства
L
. Ср. с определением перед задачей 1.4.7.
Замечание. Аналогичные определения можно дать и в более об- щей ситуации — это приводит к понятию кольца и модуля над ним.
Попытка доказать (и использовать!) аналог теоремы о линейной зависимости (задачи 7.1.1.(Z
2
),(Q)) приводит к понятиям поля и линейного пространства над ним. (Для случая целых чисел уже не все обобщения проходят.) Подробности можно найти в учебнике по линейной алгебре.
7.1.2.
Дано семейство F подмножеств множества R
n
(a) Если в каждом подмножестве из F нечётное число элементов,
а в пересечении любых двух подмножеств из F чётное число эле- ментов, то |F| 6 n.
(b) Постройте пример, когда эта оценка достигается.
(c) Если в пересечении любых двух подмножеств из F ровно q элементов и в каждом подмножестве из F более q элементов, то
|F| 6 n.
(d) Если q > 0 и в пересечении любых двух подмножеств из F
ровно q элементов, то |F| 6 n.
7.1.3.
(a) Существуют 2
k подмножеств 2k-элементного множества,
в каждом из которых чётное число элементов и в пересечении лю- бых двух из которых чётное число элементов.
(b) Больше, чем 2
k подмножеств, в условиях пункта (a) быть не может.

7. АЛГЕБРАИЧЕСКИЕ МЕТОДЫ
197 7.1.4.
(a) Наибольшее число точек в R
n с равными попарными расстояниями равно n + 1.
(b) Постройте n(n − 1)/2 точек в R
n
, попарные расстояния между которыми принимают только два различных значения.
(c) Для a ∈ R и точек v = (v
1
, . . . , v n
)
∈ R
n
, x = (x
1
, . . . , x n
)
∈ R
n обозначим P
v
(x) :=
|x − v|
2
− a
2
. Если попарные расстояния меж- ду k точками u
1
, . . . , u k
∈ R
n равны a, то многочлены P
u
1
, . . . , P
u k
линейно независимы над Q.
(d) Если попарные расстояния между k точками в R
n принимают только два различных значения, то k
6 (n + 1)(n + 4)/2.
7.1.5.
(a) Среди любых 327 попарно пересекающихся 9-элементных подмножеств 25-элементного множества найдутся два подмноже- ства, в пересечении которых ровно 3 или ровно 6 элементов.
(b) Для n, k ∈ Z обозначим
V
n,k
:=
{(x
1
, . . . , x n
)
∈ {0, 1}
n
:
∑
s x
s
= k
}.
Среди любых 327 точек в V
25,9
есть две, скалярное произведение которых лежит в {0, 3, 6}.
(c) Для любого ⃗a ∈ V
25,9
раскроем скобки в произведении
(⃗a
· (x
1
, x
2
, . . . , x
25
)
− 1)(⃗a · (x
1
, x
2
, . . . , x
25
)
− 2),
где x
1
, x
2
, . . . , x
25
— переменные. С каждым из полученных од- ночленов проведём следующую операцию: для каждого i если в од- ночлене есть множитель x n
i
, то заменим этот множитель на x i
. По- лученный многочлен обозначим F
⃗a
(x
1
, . . . , x
25
)
. Докажите, что если скалярное произведение никаких двух векторов среди ⃗a
1
, . . . , ⃗a s
∈
V
25,9
не делится на 3, то многочлены F
⃗a
1
, . . . , F
⃗a s
линейно независи- мы над Q.
(d) Укажите 326 многочленов, линейными комбинациями которых с рациональными коэффициентами можно получить каждый мно- гочлен F
⃗a
, ⃗a ∈ V
25,9 7.1.6.
(a) Среди любых 107 пятиэлементных подмножеств 14-эле- ментного множества найдутся два подмножества, в пересечении ко- торых ровно 2 элемента.

198
Элементы дискретной математики в задачах
(b) То же для 93 подмножеств.
(c) То же для 92 подмножеств.
(d) Невозможно раскрасить в 21 цвет все пятиэлементные подмно- жества 14-элементного множества так, чтобы любые два пятиэле- ментные подмножества, пересекающиеся ровно по двум элементам,
были разноцветны.
(Ср. с замечанием в задаче 5.1.4. Вот эквивалентная формулиров- ка. Вершинами графа являются все пятиэлементные подмножества
14-элементного множества. Его ребрами являются пары подмно- жеств, пересекающиеся ровно по двум элементам. Докажите, что этот граф нельзя правильно раскрасить в 21 цвет.)
7.1.7.
(a) Для простого p и целого t число G(t) := (t − 1)(t −
2) . . . (t
−p+1) делится на p тогда и только тогда, когда t не делится на p.
(b) Пусть p простое и n = 4p. Обозначим
M =
{(1, y
2
, y
3
. . . , y n
)
|
| y k
∈ {1, −1} и среди y
2
, . . . , y n
число минус единиц чётно}.
Обозначим G(t) := (t − 1)(t − 2) . . . (t − p + 1). Для любого ⃗a ∈ M
раскроем скобки в произведении G(⃗a · (1, x
2
, . . . , x n
))
, где x
2
, . . . , x n
— переменные. В каждом из полученных одночленов для каждого i будем заменять x
2
i на 1, пока это возможно. Полученный многочлен обозначим F
⃗a
(x
2
, . . . , x n
)
Докажите, что если скалярное произведение никаких векторов сре- ди ⃗a
1
, . . . , ⃗a s
∈ M не равно нулю, то многочлены F
⃗a
1
, . . . , F
⃗a s
линей- но независимы над Q.
(c) Существуют n и ограниченное подмножество в R
n
, которое невозможно разбить на n + 1 непустых частей меньшего диаметра.
7.1.8.
(a) Теорема Франкла-Уилсона. Если t простое, то cреди лю- бых различных 1+
t
−1
∑
j=0
(
n j
)
подмножеств n-элементного множества,
в каждом из которых k-элементов, найдутся два подмножества, чис- ло элементов в пересечении которых делится на t.
(b) То же, только задано целое q и ‘делится на t’ заменено на
‘сравнимо с q по модулю t’.

218
Элементы дискретной математики в задачах
10 Графы: задачи для исследования
10.1 Степенные последовательности. А. Скопенков
0.*
(a) Можно ли опустить какие-нибудь неравенства из зада- чи 5 так, чтобы достаточность (т.е. утверждение задачи 10) оста- лась верной? Если да, попробуйте найти минимальный набор нера- венств.
(b) Если слить две степенные последовательности, то обязатель- но получится степенная последовательность. А какие степенные по- следовательности обладают тем свойством, что их нельзя разбить на две степенные последовательности?
Граф называется планарным, если его можно нарисовать на плоскости так, чтобы внутренности ребер (то есть ребра без их концов) не пересекались и не самопересекались. Подробнее см. §3,
[P, S1].
1.
(abcd*) То же, что в задаче 2 предыдущей темы, для планар- ных графов.
2.
(abcd*) То же, что в задаче 2 предыдущей темы, для связных планарных графов.
Тор, лист Мебиуса и сфера с ручками изображены на рис.
Тор, лист Мебиуса, цилиндр и сфера с ручками
Пусть на торе (или на сфере с ручками, или на диске с листа- ми Мебиуса) нарисован без самопересечений граф. Назовем гранью замкнутую область на торе, ограниченную ребрами этого графа.
Реализация графа на торе (или на сфере с ручками) называ- ется клеточной, если каждая грань разбивается любой ломаной с концами на границе этой грани (т.е. топологически эквивалентна замкнутому диску на плоскости).
3.
(abcd*) То же, что в задаче 2 предыдущей части, для связных клеточно реализуемых на торе графов.
4.
(abcd*) То же, что в задаче 2 предыдущей части, для связных клеточно реализуемых на сфере с g ручками графов (g дано вместе с n и d
1
, . . . , d n
).

10. ГРАФЫ: ЗАДАЧИ ДЛЯ ИССЛЕДОВАНИЯ
219
Для получения необходимых условий в задачах 3 и 4 нужен сле- дующий факт.
Формула Эйлера для сферы с g ручками.
Пусть на сфере с g ручками нарисован без самопересечений клеточно связный граф с V вершинами и E ребрами. Пусть F — число граней. Тогда V −
E + F = 2
− 2g.
Для решения следующих задач 5 и 6 полезен аналог этого факта для диска с m листами Мебиуса.
Реализация графа на листе Мебиуса (или на диске с листами Ме- биуса, нарисованном на лекции) называется клеточной, если одна грань топологически эквивалентна кольцу, а каждая из оставшихся остальных — замкнутому диску на плоскости.
5.
(abcd) То же, что в задаче 2 предыдущей части, для связных клеточно реализуемых на листе Мебиуса графов.
6.
(abcd) То же, что в задаче 2 предыдущей части, для связных клеточно реализуемых на диске с m листами Мебиуса графов (m дано вместе с n и d
1
, . . . , d n
).
7-11.
(abcd) То же, что в задачах 3-6, если требуется построить граф с n гранями, в границе которых d
1
, . . . , d n
ребер, соответствен- но.
Пункты (a,b) задач 3-6 известны [Mo]. По-видимому, пункты (c)
этих задач неизвестны Пункты (d) этих задач неизвестны.
[Mo] B. Mohar, 2-cell embeddings with prescribed face lengths and genus,
Ann.
Combin.
14
(2010)
525-532.
http://www.fmf.uni-lj.si/mohar/Reprints/Inprint/BM06_AC_Mohar_
2cellEmbeddings.pdf.
10.2 Гамильтоновость (А. Веснин, А. Скопенков)
Цикл (путь) называется гамильтоновым, если он проходит че- рез каждую вершину графа ровно по одному разу. Граф называется гамильтоновым, если в нем есть гамильтонов цикл. См. подробнее
§2.6.
1.
(a) Нарисуйте гамильтоновы циклы в графах правильных многогранников.

220
Элементы дискретной математики в задачах
(b) Никакой граф, гомеоморфный букве θ (т.е. графу K
3,2
), не является гамильтоновым.
Пусть H — граф. Граф X называется H-гамильтоновым, ес- ли в X существует подграф, содержащий все вершины графа X и гомеоморфный графу H.
Следующая задача (кроме (f)) проста и приводится для того,
чтобы помочь решателю войти в курс дела. Задачи, отмеченные звездочкой, являются нерешенными.
2.
(a) Любой гамильтонов граф, отличный от окружности, яв- ляется θ-гамильтоновым.
(b) Существует θ-гамильтонов граф, не являющийся гамильто- новым.
(c) Существует гамильтонов граф, отличный от окружности и
θ
, не являющийся K
4
-гамильтоновым.
(d) Существует K
4
-гамильтонов граф, не являющийся θ-гамильтоновым.
(e) Для любых графов G и H существует G-гамильтонов граф,
не являющийся H-гамильтоновым.
(f)* Опишите "иерархию"графов по их гамильтоновости: когда
H

1   2   3   4   5   6