ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ

Том 55

2019

Вып. 4

УДК 629.391.1 : 519.1

А.А. Сагдеев

ОБ ОДНОЙ ТЕОРЕМЕ ФРАНКЛА - УИЛСОНА¹

Получен аналог теоремы Франкла - Уилсона о числах независимости неко-

торых дистанционных графов. Полученные результаты применены к задаче о

хроматическом числе пространства Rⁿ с запрещенным равносторонним тре-

угольником, а также к задаче о хроматических числах дистанционных графов

с большим обхватом.

Ключевые слова: дистанционный граф, теорема Франкла - Уилсона, теорема

Франкла- Рёдля, хроматическое число, евклидова теория Рамсея, обхват.

DOI: 10.1134/S0555292319040041

§1. Введение и формулировка центрального результата

Пусть n ≥ k ≥ t - произвольные целые неотрицательные числа. Определим

дистанционный граф G(n, k, t) = (V (n, k), E(n, k, t)) следующим образом. Его вер-

шинами являются все точки Rⁿ, у которых в точности k координат равны единице,

а оставшиеся n - k равны нулю. Ребро в G(n, k, t) соединяет две вершины тогда и

только тогда, когда их радиус-векторы имеют ровно t общих единиц. Отметим, что

на параметры естественно наложить дополнительное ограничение n - 2k + t ≥ 0,

так как если последнее неравенство не выполнено, то множество E(n, k, t) является

пустым.

Графы G(n, k, t) являются одними из наиболее важных графов для современной

экстремальной комбинаторики. Во-первых, с их помощью доказываются наиболее

сильные на сегодняшний день нижние оценки в задачах, родственных задаче Нель-

сона о вычислении хроматического числа плоскости χ(R²) (см. [1-5]). Во-вторых,

с помощью графов G(n, k, t) строятся асимптотически наиболее сильные контрпри-

меры к гипотезе Борсука (см. [6]). Наконец, изучение графов G(n, k, t) имеет значе-

ния для теории множеств и теории кодирования, так как эти графы тесно связаны

с задачей о кодах с запрещенным расстоянием (см. [7,8]).

Наиболее интересным для приложений является случай k = k(n) ∼ κn, t = t(n) ∼

∼ τn при n → ∞, где 0 ≤ τ ≤ κ ≤ 1 - некоторые фиксированные заранее константы.

С помощью формулы Стирлинга легко показать, что

Cbn+o(n)an+o(n) = (c^ba + o(1))ⁿ при n → ∞, где c^ba =

b^b(a - b)(a-b)

Значит, в интересующем нас случае при n → ∞ верно, что

|V (n, k)| = C^kn = (cκ1 + o(1))ⁿ,

|E(n, k, t)| =

C^knC^tkC^k-tn-k = (cκ1c^τκcκ-τ1-κ + o(1))ⁿ.

¹ Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных

исследований (номер проекта 18-01-00355), гранта Президента Росийской Федерации для государ-

ственной поддержки ведущих научных школ (номер гранта НШ-6760.2018.1) и Фонда Саймонса.

Результаты, касающиеся асимптотических верхних оценок чисел независимости

графов G(n, k, t), приведены в следующей теореме.

Теорема 1. Пусть k = k(n) ∼ κn, t = t(n) ∼ τn при n → ∞, где 0 ≤ τ ≤ κ ≤ 1

и 1 - 2κ + τ ≥ 0. Пусть при каждом n величина k - t является простым числом.

Тогда при n → ∞ справедливо неравенство

α(G(n, k, t)) ≤ (α(κ, τ) + o(1))ⁿ,

где

⎧

⎪cκ-τ1 ,

если 2κ ≤ 1, 2τ ≤ κ,

⎨

cκ1cκ-τ1

α(κ, τ) =

если 2κ ≤ 1, 2τ > κ,

⎪

2κ-2τ

⎩^c

α(1 - κ, 1 - 2κ + τ), если 2κ > 1.

Замечание 1. Результат теоремы 1 в случае 2κ > 1 является тривиальным след-

ствием ее применения к случаям 2κ ≤ 1. Это следует из очевидного равенства

α(G(n, k, t)) = α(G(n, n - k, n - 2k + t)), которое доказывается заменой всех еди-

ничных координат вершин графа G(n, k, t) на нули, а всех нулевых - на единицы.

Замечание 2. Формулировка теоремы 1 допускает незначительное обобщение.

Пусть n = n(m) ∼ νm, k = k(m) ∼ κm, t = t(m) ∼ τm при m → ∞, где 0 ≤ τ ≤ κ ≤ ν

и ν - 2κ + τ ≥ 0. Пусть при каждом m величина k - t является простым числом.

Тогда теорема 1 гарантирует, что при m → ∞ справедливо неравенство

(

)_n

⁽κ

τ⁾

α(G(n, k, t)) ≤ α

+ o(1)

= (α(ν, κ, τ) + o(1))^m,

)_ν

⁽κ

где α(ν, κ, τ) = α

. Подставив в последнее равенство явную формулу для

α(· , ·) и упростив, можно показать, что

⎧

⎪cκ-τν ,

если 2κ ≤ ν, 2τ ≤ κ,

⎨

c^κνc^κ-τν

α(ν, κ, τ) =

если 2κ ≤ ν, 2τ > κ,

⎪

2κ-2τ

⎩^c

α(ν, ν - κ, ν - 2κ + τ), если 2κ > ν.

Несколько раз в настоящей статье нам потребуется воспользоваться оценкой числа

независимости графа G(n, k, t) именно в виде, приведенном в данном замечании.

Результат теоремы 1 в случае 2τ ≤ κ ≤ 1/2 был получен Франклом и Уислоном

в их знаменитой работе [9]. В работе [10] показана неулучшаемость оценки Франк-

ла - Уилсона. Результат теоремы 1 в случае 2τ > κ, κ ≤ 1/2, был впервые получен

в работе [11] в другой, намного более сложной, форме. В том виде, в каком этот

результат представлен в теореме 1, он был получен в работе [12]. Точность приве-

денной выше верхней оценки в случае 2τ > κ не доказана.

Нетрудно видеть, что при любых допустимых значениях параметров κ и τ тео-

α(G(n, k, t))

рема 1 гарантирует, что величина

экспоненциально быстро стремится к

|V (n, k)|

нулю при n → ∞. Из этого, в частности, вытекает

Следствие 1. Пусть k и t те же, что и в теореме 1. Пусть δ = δ(κ,τ) -

произвольное достаточно маленькое положительное число. Тогда любое подмно-

жество W вершин графа G(n, k, t) мощности не менее (1 - δ)ⁿ|V (n, k)| содержит

хотя бы одно ребро.

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

выше следствие 1. А именно, хотелось бы, чтобы во всяком “достаточно большом”

подмножестве вершин графа G(n, k, t) гарантировалось бы наличие не одного ребра,

а “достаточно большого” количества ребер. В работе [13] было доказано следующее

конструктивное утверждение такого типа.

Теорема 2. Пусть k = k(n) ∼ n/2, t = t(n) ∼ n/4 при n → ∞. Пусть при

каждом n величина k - t является простым числом. Тогда для любого ε > 0 суще-

ствует δ = δ(ε) > 0, такое что при всех достаточно больших n любое подмноже-

ство W вершин графа G(n, k, t) мощности не менее (1 - δ)ⁿ|V (n, k)| содержит не

менее (1 - ε)ⁿ|E(n, k, t)| ребер. Кроме того, найдется такая стремящаяся к нулю

⁽1 + α(ε)⁾ ε

при ε → 0 функция α(ε), что можно положить δ(ε) =

ln² ε

Центральными результатами настоящей статьи являются сформулированная ни-

же универсальная, но громоздкая техническая теорема 3, а также ее следствие,

являющееся усилением и обобщением теоремы 2.

Теорема 3. Пусть n ≥ k ≥ t - произвольные целые неотрицательные числа,

такие что n-2k+t ≥ 0. Пусть ρ_V и ρ_E - произвольные числа из интервала (0; 1).

Для всех целых неотрицательных значений a и b, удовлетворяющих неравенствам

0 ≤ b ≤ t,

0 ≤ a ≤ n - 2k + t,

(1)

определим величины M₁, M₂, M₃ следующими равенствами:

M₁ = ρ_V |V (n, k)|C^bkC^an-k, M₂ = ρ_E|E(n, k, t)|C^btCan-2k+t, M₃ = C^bnC^an-b.

Предположим, что существуют целые числа a, b, удовлетворяющие неравен-

ствам (1), такие что

M₁ ≥ 2M₂, M₁ ≥ 2M₃α(G(n - a - b, k - b, t - b)).

(2)

Тогда любое подмножество W множества вершин графа G(n, k, t) мощности не

менее ρ_V |V (n, k)| содержит не менее ρ_E|E(n, k, t)| ребер.

Следствие 2. Пусть k = k(n) ∼ κn, t = t(n) ∼ τn при n → ∞, где 0 < τ <

< κ < 1 и 1 - 2κ + τ > 0. Пусть при каждом n величина k - t является простым

числом. Тогда для любого ε > 0 существует δ = δ(ε) = δ(ε, κ, τ) > 0, такое что

при всех достаточно больших n любое подмножество W вершин графа G(n, k, t)

мощности не менее (1 - δ)ⁿ|V (n, k)| содержит не менее (1 - ε)ⁿ|E(n, k, t)| ребер.

Кроме того, найдется такая стремящаяся к нулю при ε → 0 функция α(ε) =

⁽1 + α(ε)⁾ ε

= α(ε, κ, τ), что можно положить δ(ε) =

4κ - 4τ ln² ε

Отметим, что, во-первых, следствие 2 применимо к любым значениям 0 < τ <

< κ ≤ 1/2, а не только к τ = 1/4, κ = 1/2, как этого требует ранее известная тео-

рема 2. Во-вторых, даже при применении к значениям τ = 1/4, κ = 1/2 следствие 2

сильнее теоремы 2.

Такого результата удалось достичь благодаря тому, что доказательство теоре-

мы 3 удалось провести без использования теоремы Франкла - Рёдля (см. [14]), в то

время как в доказательстве теоремы 2 результат Франкла и Рёдля не только ис-

пользовался, но и являлся его “узким местом”, не позволявшим улучшить оценку

величины δ(ε).

Оставшаяся часть статьи имеет следующую структуру. В §2 рассказано о прило-

жении нашего основного результата к двум задачам экстремальной комбинаторики.

В §3 показано, как можно получить значительно более слабые аналоги теорем 1

и 3, которые, однако, применимы ко всем графам G(n, k, t), а не только к таким,

для которых k - t является простым числом. В §4 приведены доказательства всех

результатов настоящей статьи.

В заключение отметим, что смежные задачи экстремальной комбинаторики рас-

сматривались в работах [15-25].

§ 2. Приложения теоремы 3

Теорема 3 и следствие 2 представляют не только самостоятельный интерес, но и

позволяют продвинуться в решении некоторых других задач. Одна из таких задач

формулируется следующим образом.

Определим для каждого m ≥ 3 величину ξ_m(Rⁿ), равную максимуму хромати-

ческих чисел дистанционных графов в Rⁿ, обхват которых строго больше m. В [26]

Купавский доказал, что при n → ∞ справедливо неравенство

ξ_m(Rⁿ) ≥ (c(m) + o(1))ⁿ,

(3)

где c(m) > 1 - некоторая константа. Определим величину ξ_m, равную максимальной

константе c(m), с которой неравенство (3) все еще в силе. Более формально,

ξ_m = liminf

ξ_m(Rⁿ)1/n.

n→∞

Наилучшая известная нижняя оценка величины ξ_m при m → ∞, полученная

в работах [13, 27], имеет следующий вид.

Теорема 4. При m → ∞ справедливо неравенство

(

)₂

1 + o(1)

0,0133 . . . + o(1)

ξ_m ≥ 1 +

=1+

6m log₂ m

m² ln² m

В настоящей статье мы доказываем теорему, устанавливающую связь между ве-

личинами ξ_m и следствием 2, а также получаем из нее конкретное следствие, заметно

усиливающее ранее известную теорему 4.

Теорема 5. Пусть k = k(n) ∼ κn, t = t(n) ∼ τn при n → ∞, где 0 < τ < κ < 1

и 1 - 2κ + τ > 0. Пусть при каждом n величина k - t является простым числом.

Пусть функция δ = δ(ε) = δ(ε, κ, τ) > 0 такова, что при любом ε > 0 при всех

достаточно больших n любое подмножество W вершин графа G(n, k, t) мощности

не менее (1-δ)ⁿ|V (n, k)| содержит не менее (1-ε)ⁿ|E(n, k, t)| ребер. Пусть m ≥ 3,

и пусть ε_m - положительное число, такое что

1 - δ(ε_m)

< (c^τκcκ-τ1-κ )m-1 .

(4)

1-ε_m

Тогда

ξ_m ≥

1 - δ(ε_m)

0,632 . . . + o(1)

Следствие 3. При m → ∞ справедливо неравенство ξ_m ≥ 1 +

m² lnm

При малых значениях m теорема 5 также позволяет заметно улучшить нижние

оценки ξ_m. Соответствующие результаты мы представили в виде табл. 1. Для срав-

нения мы также приводим известные ранее аналогичные оценки из [27].

Отметим, что в частном случае m = 3 в работе [28] была получена более сильная

оценка ξ₃ ≥ 1,058.

Еще одной важной областью, в которой находит применение теорема 3, является

евклидова теория Рамсея. В рамках этой теории для некоторого фиксированного

конечного множества S ⊂ R^d определяется величина χ(Rⁿ; S), равная наименьшему

Таблица 1

Нижние оценки ξm

Оценка из работы [27] Новая оценка

ξm ≥

1,0000294

1,042

1,0000294

1,012

1,0000294

1,0053

1,0000193

1,0028

1,0000128

1,0017

1,00000907

1,0011

1,00000667

1,00077

1,00000507

1,00056

числу цветов, необходимых для такой раскраски пространства Rⁿ, при которой ни

одна копия S^′ ⊂ Rⁿ множества S не является полностью одноцветной.

Множество S называется экспоненциально рамсеевским, если χ(Rⁿ; S) экспо-

ненциально быстро стремится к бесконечности с ростом n. Например, множество

S₁ ⊂ R¹, являющееся парой точек, является экспоненциально рамсеевским. Этот

факт был конструктивно доказан Франклом и Уилсоном в работе [9]. Наилучшая

из известных на сегодняшний день оценок величины χ(Rⁿ; S₁) = χ(Rⁿ) получена

в работе [2] и имеет вид

χ(Rⁿ) ≥ (1,239 . . . + o(1))ⁿ.

Задачи евклидовой теории Рамсея подробно изучались в работах [29-34]. В на-

стоящей статье мы остановимся лишь на рассмотрении случая, в котором S_k ⊂ R^k

является множеством вершин правильного k-мерного симплекса. Франкл и Рёдль

неконструктивно доказали в [14], что при каждом k ≥ 2 множество S_k - экспонен-

циально рамсеевское. Явные нижние экспоненциально растущие оценки величин

χ(Rⁿ; S_k) были получены в работах [13, 27] с использованием теоремы 2.

Теорема 6. При n → ∞ справедливы следующие два неравенства:

χ(Rⁿ; S₂) ≥ (1,00085 . . . + o(1))ⁿ,

(5)

(

)_n

χ(Rⁿ; S_k) ≥

+ o(1)

(6)

22k+4

В работе [33] с помощью принципиально иного метода неравенства (5), (6) были

усилены.

Теорема 7. При n → ∞ справедливы следующие два неравенства:

χ(Rⁿ; S₂) ≥ (1,0126 . . . + o(1))ⁿ,

(7)

(

)_n

χ(Rⁿ; S_k) ≥

+ α₂(k, n)

(8)

(2 + α₁(k))k

где функция α₁(k) стремится к нулю при k → ∞, а функция α₂(k, n) стремится

к нулю при n → ∞ при любом фиксированном k.

С помощью теоремы 3 настоящей статьи, являющейся усилением теоремы 2, мож-

но улучшить оценки (5), (6). Усиление оценки (6) при этом оказывается незначитель-

ным: единственное, что удается сделать таким образом - это заменить k + 4 в по-

казателе степени на k + c, где c - некоторая конкретная константа, строго меньшая

четырех. Видно, что даже после этого улучшения оценка (6) остается значительно

слабее оценки (8) при больших k (на самом деле, при всех k ≥ 3), так что мы не

будем останавливаться на конкретном способе получения этого улучшения.

В случае k = 2 ситуация принципиально иная. Улучшенное неравенство (5), ко-

торое мы формулируем в следствии 4, оказывается даже более сильным, чем оцен-

ка (7). Такой эффект возникает потому, что метод из [33] не позволяет оценивать

снизу величину χ(Rⁿ; S₂) непосредственно. Вместо этого в [33] находится нижняя

оценка величины χ(Rⁿ; S₃) и делается очевидное замечание, что S₂ ⊂ S₃, а значит,

χ(Rⁿ; S₂) ≥ χ(Rⁿ; S₃). За счет этого серьезного огрубления метод из [33] и проигры-

вает методу из настоящей статьи при k = 2 несмотря на то, что он выигрывает при

всех k ≥ 3.

Следствие 4. При n → ∞ верно неравенство χ(Rⁿ;S₂) ≥ (1,014... + o(1))ⁿ.

§ 3. Случай составного k - t

В этом параграфе мы опишем идею, позволяющую избавиться от ограничения

простоты величины k-t в теореме 1. Эта идея была предложена Кивашем и Лонгом

в работе [35] для доказательства некоторых теорем существования и усовершенство-

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

G(n, k, t), приведенных в виде табл. 2 в конце параграфа. Поэтому там, где это воз-

можно, наши обозначения будут близки к обозначениям из [35].

Пусть f : N → 2N - некоторая возрастающая функция, принимающая только

четные значения. Будем говорить, что f представима в виде суммы двух простых

в любой пропорции, если для любых a, b ≥ 0, таких что a + b = 1, верно, что суще-

ствуют функции p_a, p_b : N → N, принимающие только простые значения, такие что

∀n ∈ N p_a(n) + p_b(n) = f(n), p_a(n) = af(n) + o(f(n)), p_b(n) = bf(n) + o(f(n)).

Пусть n = n(m) ∼ νm, k = k(m) ∼ κm, t = t(m) ∼ τm при m → ∞, где 0 ≤ τ ≤

κ ≤ ν и ν-2κ+τ ≥ 0. Оценим число независимости графа G(n,k,t) в предположении,

что функция k - t принимает только четные значения и представима в виде суммы

двух простых в любой пропорции.

Пусть ν₁, ν₂, κ₁, κ₂, τ₁, τ₂ - произвольные вспомогательные параметры, такие что

ν =ν₁ +ν₂, κ=κ₁ +κ₂, τ =τ₁ +τ₂,

(9)

0 ≤ τ_i ≤ κ_i ≤ ν_i, ν_i - 2κ_i + τ_i ≥ 0, i = 1,2.

Разобьем каждую из функций n(m), k(m), t(m) на два слагаемых

n(m) = n₁(m) + n₂(m), k(m) = k₁(m) + k₂(m), t(m) = t₁(m) + t₂(m)

так, что при m → ∞ справедливы асимптотики

n_i = n_i(m) ∼ ν_im, k_i = k_i(m) ∼ κ_im, t_i = t_i(m) ∼ τ_im, i = 1, 2,

и значения функций k₁ - t₁ и k₂ - t₂ являются простыми числами при каждом

значении m (этого можно добиться в силу предположения о том, что функция k - t

представима в виде суммы двух простых в любой пропорции.)

Пусть W

⊂ V (n,k) - произвольное подмножество множества вершин графа

G(n, k, t), такое что |W | = ρ|V (n, k)|. Покажем, что если ρ достаточно велико, то W

обязательно содержит ребро.

Пусть [n] = {1, . . . , n}, и пусть [n] = N₁ ⊔ N₂ - произвольное разбиение n-эле-

ментного множества на два непересекающихся подмножества, таких что |N₁| = n₁,

N₂ = n₂. Положим

{

}

∑

W (N₁, N₂) = v = (v₁, . . . , v_n) ∈ W :

v_i = k₁,

v_i = k₂

i∈N1

i∈N2

множеств

−k

W (N₁, N₂), а значит,

∑

−k

[n]=N1⊔N2

По принципу Дирихле найдется такое разбиение [n] = N₁ ⊔ N₂, что

ρC^knC_k

−k

|W (N₁, N₂)| ≥

= ρCk1n1Cn2 .

Cn1

Пусть X = V (n₁, k₁), Y = V (n₂, k₂). По двум элементам x ∈ X, y ∈ Y мы можем

задать элемент v = x ⊔ y ∈ V (n, k) по следующим правилам. Если i - j-й по воз-

растанию элемент N₁, то v_i = x_j . Если же i - j-й по возрастанию элемент N₂, то

vi = yj. Рассмотрим двудольный граф G = (X,Y,E), в котором ребро соединяет

вершины x ∈ X, y ∈ Y тогда и только тогда, когда x ⊔ y ∈ W(N₁, N₂). Ясно, что

ρ|X||Y |. Воспользуемся общей тео-

количество ребер в этом графе равно ρCk1n1^Cn2 =

ремой о двудольных графах, доказательство которой можно найти, например, в [35]

(см. также [36]).

Теорема 8. Пусть G = (X,Y,E) - произвольный двудольный граф, такой

что |E| = ρ|X||Y |. Тогда для любого натурального s существует подмножество

X^′ ⊂ X, такое что |X^′| ≥ ρ^s|X|/2 и любые два элемента x₁, x₂ ∈ X^′ имеют не

менее ρ|Y ||X|-1/s общих соседей в Y .

Посмотрим на множества X и Y как на множества вершин графов G(n₁, k₁, t₁)

и G(n₂, k₂, t₂) соответственно. Так как k₁ - t₁ и k₂ - t₂ - простые, то числа незави-

симости этих графов могут быть оценены сверху по теореме 1.

Предположим, что значения вспомогательных параметров таковы, что

ρ^s|X|/2 > α(G(n₁, k₁, t₁)), ρ|Y ||X|-1/s > α(G(n₂, k₂, t₂)).

(10)

В таком случае в множестве X^′, существование которого гарантировано теоремой 8,

обязательно найдутся вершины x₁, x₂, соединенные ребром в графе G(n₁, k₁, t₁). Сре-

ди их общих соседей, в свою очередь, найдутся две вершины y₁, y₂, соединенные

ребром в графе G(n₂, k₂, t₂). Положим v₁ = x₁ ⊔ y₁, v₂ = x₂ ⊔ y₂. Нетрудно видеть,

что вершины v₁, v₂ лежат в W и соединены ребром в графе G(n, k, t). Значит, мно-

жество W не является независимым. Таким образом, мы получили оценку сверху

на величину α(G(n, k, t)).

Преобразовав неравенства (10) с помощью формулы Стирлинга и теоремы 1,

получим, что в нашем случае

α(G(n, k, t)) < (c + o(1))^m,

(11)

где

)1/s

}

^{( α(ν₁, κ₁, τ₁)

α(ν₂, κ₂, τ₂)

c = cκν max

(cκ1 )1/s

ν1

cν11

cν22

Так как значения вспомогательных параметров можно варьировать, то при m → ∞

справедливо неравенство

α(G(n, k, t)) < (α₂(ν, κ, τ) + o(1))^m,

(12)

где

{

)1/s

}}

^{(α(ν₁, κ₁, τ₁)

α(ν₂, κ₂, τ₂)

α₂(ν, κ, τ) = inf c^κν max

(cκ1 )1/sν

cν11

cν2

и инфимум берется по всем натуральным s и всем ν₁, ν₂, κ₁, κ₂, τ₁, τ₂, удовлетворя-

ющим (9).

Перейдем к рассмотрению нового случая. Будем говорить, что некоторая функ-

ция f : N → 2N + 1, принимающая только нечетные значения, представима в виде

суммы трех простых в любой пропорции, если для любых a, b, c ≥ 0, таких что

a + b + c = 1, существуют функции p_a,p_b,p_c: N → N, принимающие только простые

значения, такие что при любом n верно, что p_a(n) + p_b(n) + p_c(n) = f(n) и, кроме

того,

p_a(n) = af(n) + o(f(n)), p_b(n) = bf(n) + o(f(n)), p_c(n) = cf(n) + o(f(n)).

Пусть n = n(m) ∼ νm, k = k(m) ∼ κm, t = t(m) ∼ τm при m → ∞, где 0 ≤ τ ≤

≤ κ ≤ ν и ν - 2κ + τ ≥ 0. Оценим число независимости графа G(n,k,t) в предпо-

ложении, что функция k - t принимает только нечетные значения и представима

в виде суммы трех простых в любой пропорции.

Выберем некоторые значения вспомогательных параметров ν₃, κ₃, τ₃, такие что

0 ≤ τ₃ ≤ κ₃ ≤ ν₃, ν₃ - 2κ₃ + τ₃ ≥ 0,

0≤τ-τ₃ ≤κ-κ₃ ≤ν-ν₃,

(13)

(ν - ν₃) - 2(κ - κ₃) + (τ - τ₃) ≥ 0.

Найдем разбиения ν₁ + ν₂ = ν - ν₃, κ₁ + κ₂ = κ - κ₃, τ₁ + τ₂ = τ - τ₃, мини-

мизирующие величину α₂(ν - ν₃, κ - κ₃, τ - τ₃) (такие всегда существуют в силу

соображений компактности). Разобьем теперь каждую из функций n(m), k(m), t(m)

на три слагаемых

n(m) = n₁(m) + n₂(m) + n₃(m), k(m) = k₁(m) + k₂(m) + k₃(m),

t(m) = t₁(m) + t₂(m) + t₃(m)

так, что при m → ∞ справедливы асимптотики

n_i = n_i(m) ∼ ν_im, k_i = k_i(m) ∼ κ_im, t_i = t_i(m) ∼ τ_im, i = 1, 2, 3,

и значения функций k₁ -t₁, k₂ -t₂ и k₃ -t₃ являются простыми числами при каждом

значении m. Применим теперь все описанные выше для четного случая рассужде-

ния к некоторому разбиению множества [n] на непересекающиеся множества N₁ ⊔N₂

и N₃. Аналог неравенств (10) для нашего случая будет выглядеть следующим обра-

зом:

ρ^sCk−n3n3/2>α(G(n-n3^,k-k3^,t-t3)),ρCn3 (Cn−n3 )-1/s >α(G(n3^,k3^,t3)).(14)

Величину α(G(n-n₃, k -k₃, t-t₃)) мы можем оценить сверху по уже обоснованному

неравенству (11). Подставляя теперь эту оценку в (14), а также применяя формулу

Стирлинга и теорему 1, получим, что при m → ∞ справедливо неравенство

α(G(n, k, t)) < (α{1,2}{3}(ν, κ, τ) + o(1))^m,

(15)

где

α{1,2}{3}(ν, κ, τ) =

{

)1/s

}}

^{(α₂(ν - ν₃, κ - κ₃, τ - τ₃)

α(ν₃, κ₃, τ₃)

= inf c^κν max

(cκ-κ3 )1/sν-ν

cν3

cκ−ν3ν3

и инфимум берется по всем натуральным s и всем ν₃, κ₃, τ₃, удовлетворяющим (13).

Разбивая теперь исходное множество [n] на два множества N₁ и N₂ ⊔ N₃, мож-

но совершенно аналогично тому, как мы обосновали неравенство (15), обосновать

неравенство

(

)_m

α(G(n, k, t)) <

α{1}{2,3}(ν, κ, τ) + o(1)

(16)

где

α{1}{2,3}(ν, κ, τ) =

{

)1/s

}}

^{(α(ν₁, κ₁, τ₁)

α₂(ν - ν₁, κ - κ₁, τ - τ₁)

= inf c^κν max

(cκ1 )1/sν

cν11

cκ-κ1

ν-ν1

и инфимум берется по всем натуральным s и всем ν₁, κ₁, τ₁, удовлетворяющим нера-

венствам

0 < τ₁ < κ₁ < ν₁, ν₁ - 2κ₁ + τ₁ > 0,

0<τ-τ₁ <κ-κ₁ <ν-ν₁,

(17)

(ν - ν₁) - 2(κ - κ₁) + (τ - τ₁) > 0.

Из (15) и (16) следует, что при m → ∞ справедливо неравенство

α(G(n, k, t)) < (α₃(ν, κ, τ) + o(1))^m,

(18)

где

{

}

α₃(ν, κ, τ) = min

α{1,2}{3}(ν, κ, τ), α{1}{2,3}(ν, κ, τ)

В работе [37] автором была доказана следующая теорема (см. также [38-40]).

Теорема 9. Пусть a,b,c ∈ [0;1] - три фиксированных произвольных неотри-

цательных числа, таких что a + b + c = 1. Тогда каждое нечетное число n ≥ 7

можно разбить на три простых слагаемых p_a(n) + p_b(n) + p_c(n) = n так, что при

n → ∞ верно

p_a(n) = an + o(n), p_b(n) = bn + o(n), p_c(n) = cn + o(n).

Из теоремы 9 следует, что ограничение о разложимости функции k - t на три

простых в любой пропорции, наложенное нами для получения оценки (18), было

излишним. Достаточно было потребовать нечетности k - t. Итак, нами доказана

Теорема 10. Пусть n = n(m) ∼ νm, k = k(m) ∼ κm, t = t(m) ∼ τm при

m → ∞, где 0 ≤ τ ≤ κ ≤ ν и ν - 2κ + τ ≥ 0. Пусть при каждом m величина k - t

является нечетным числом. Тогда при m → ∞ справедливо неравенство

α(G(n, k, t)) ≤ (α₃(ν, κ, τ) + o(1))^m,

где величина α₃(ν, κ, τ) определена в (18).

Замечание 3. Компьютерные вычисления показывают, что, по-видимому, при

всех допустимых значениях параметров ν, κ и τ значения функций α{1,2}{3}(ν, κ, τ)

и α{1}{2,3}(ν,κ,τ) оказываются равны. Однако доказать это равенство аналитически

не удается.

К сожалению, аналог теоремы 9, позволяющий разбивать любое четное число на

два простых слагаемых в любой пропорции, пока не обоснован. Однако из теоре-

мы 9 легко следует, что любое четное число может быть разбито на четыре простых

в любой пропорции. Действительно, пусть a + b + c + d = 1, и пусть n - четное

число. Доказано (см., например, [41]), что разность между натуральным числом m

и ближайшим к нему простым числом равна o(m) при m → ∞. Из этого следует,

что существует простое p_d(n) = dn + o(n). По теореме 9 разность n - p_d(n) может

быть представлена в виде трех простых слагаемых p_a(n) + p_b(n) + p_c(n) в искомой

пропорции.

Следовательно, для получения верхней оценки величины α(G(n, k, t)) в случае

четного k - t мы можем воспользоваться теми же рассуждениями, которые помогли

нам доказать оценку (18), чтобы установить, что при m → ∞

α(G(n, k, t)) < (α₄(ν, κ, τ) + o(1))^m,

(19)

где

{

}

α₄(ν, κ, τ) = min

α{1,2,3}{4}(ν, κ, τ), α{1,2}{3,4}(ν, κ, τ), α{1}{2,3,4}(ν, κ, τ)

α{1,2,3}{4}(ν, κ, τ) =

{

)1/s

}}

^{(α₃(ν - ν₄, κ - κ₄, τ - τ₄)

α(ν₄, κ₄, τ₄)

= inf c^κν max

(cκ-κ4 )1/s

ν-ν4

cν4

cκ−ν4ν4

α{1,2}{3,4}(ν, κ, τ) =

{

)1/s

}}

^{(α₂(ν^′, κ^′, τ^′)

α₂(ν - ν^′, κ - κ^′, τ - τ^′)

= inf c^κν max

)1/s

(cκ′ν

cκ′ν

cκ-κ′ν-ν′

α{1}{2,3,4}(ν, κ, τ) =

{

)1/s

}}

^{(α(ν₁, κ₁, τ₁)

α₃(ν - ν₁, κ - κ₁, τ - τ₁)

= inf c^κν max

(cκ1 )1/s

ν1

cν11

cκ-κ1

ν-ν1

Имея в виду теорему 10 и неравенство (19), число независимости графа G(n, k, t)

может быть оценено сверху при абсолютно любом значении величины k - t.

Замечание 4. С помощью результатов, полученных в этом параграфе, можно

избавиться от требования простоты величины k - t в формулировке следствия 2.

Явным видом функции δ(ε) в этом случае при ε → 0 будет

δ(ε) = (c(κ, τ) + o(1))

ln² ε

где значение величины c(κ, τ), которое можно вычислить явно, окажется значи-

тельно меньше величины

из формулировки следствия 2. Такое ухудшение

4κ - 4τ

происходит из-за того, что оценки чисел независимости, приведенные в данном па-

раграфе, значительно уступают оценкам из теоремы 1, применимым, однако, только

в случае простоты величины k - t.

В заключение данного параграфа мы приводим табл. 2 численных оценок чисел

независимости графов G(n, k, t) при k = k(n) ∼ κn, t = t(n) ∼ τn при n → ∞.

Каждая клетка таблицы содержит четыре числа:

1. основание экспоненты числа вершин графа G(n, k, t), равное cκ1;

2. α₃(1, κ, τ) - основание экспоненты верхней оценки числа независимости в случае

нечетного k - t;

3. α₂(1, κ, τ) - основание экспоненты верхней оценки числа независимости в случае

четного k - t, представимого в виде суммы двух простых в любой пропорции;

4. α(1, κ, τ) - основание экспоненты верхней оценки числа независимости в случае

простого k - t.

Первое из этих четырех чисел округлено вниз до третьего знака после запятой, три

других числа округлены вверх.

Несмотря на то что, казалось бы, числа независимости графов G(n, k, t) не долж-

ны существенным образом зависеть от того, является ли число k - t простым или

Таблица 2

Оценки чисел независимости графов G(n, k, t)

0,20

0,25

0,30

0,35

0,40

0,45

0,50

1,649

1,754

1,842

1,910

1,960

1,990

2,000

1,642

1,748

1,837

1,907

1,957

1,988

2,000

0,05

1,621

1,731

1,822

1,895

1,949

1,983

1,998

1,527

1,650

1,755

1,843

1,911

1,961

1,991

1,649

1,754

1,842

1,910

1,960

1,990

2,000

1,634

1,742

1,831

1,902

1,954

1,986

1,998

0,10

1,590

1,704

1,800

1,877

1,935

1,973

1,992

1,385

1,527

1,650

1,755

1,843

1,911

1,961

1,649

1,754

1,842

1,910

1,960

1,990

2,000

1,637

1,738

1,825

1,897

1,950

1,983

1,996

0,15

1,604

1,691

1,774

1,855

1,918

1,960

1,982

1,454

1,473

1,527

1,650

1,755

1,843

1,911

1,754

1,842

1,910

1,960

1,990

2,000

1,742

1,825

1,893

1,945

1,979

1,993

0,20

—

1,707

1,776

1,840

1,897

1,943

1,970

1,547

1,546

1,583

1,650

1,755

1,843

1,842

1,910

1,960

1,990

2,000

1,829

1,893

1,942

1,974

1,989

0,25

—

1,792

1,842

1,888

1,926

1,954

1,624

1,604

1,624

1,675

1,755

1,910

1,960

1,990

2,000

1,897

1,942

1,971

1,984

0,30

—

1,858

1,889

1,916

1,935

1,684

1,645

1,649

1,683

1,960

1,990

2,000

1,946

1,971

1,981

0,35

—

1,907

1,918

1,926

1,728

1,670

1,657

составным, из табл. 2

видно, что оценки α₂(1, κ, τ) и α₃(1, κ, τ) существенно уступа-

ют оценке α(1, κ, τ) при всех значениях параметров κ и τ. Однако даже такие слабые

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

Отметим, что численные оценки функции α₄(1, κ, τ) не даны в табл. 2 в связи со

слишком большими вычислительными затратами, необходимыми для их получения.

§ 4. Доказательства

4.1. Доказательство теоремы 3. Доказательство теоремы 3 представляет собой

синтез доказательств двух других теорем. Первое из них приведено в работе [42]

и отличается тем, что в нем по существу используется теорема Франкла - Рёдля.

Второе из используемых доказательств приведено в работе [35] и отличается тем,

что, с одной стороны, обходится без использования теоремы Франкла - Рёдля, а с

другой - использует меньшее число вспомогательных параметров, так как решает

совсем другую, неоднородную задачу. Так что там, где это возможно, мы будем

стараться сохранять обозначения, близкие к использованным в работах [35, 42].

Пусть W - произвольное подмножество V (n, k) мощности не менее ρ_V |V (n, k)|.

Предположим, что утверждение теоремы не верно и мощность множества E(W )

ребер графа G(n, k, t), содержащихся в W , строго меньше чем ρ_E |E(n, k, t)|.

Будем считать, что целые неотрицательные числа a и b таковы, что неравен-

ства (1), (2) выполнены. Пусть S₀, S₁ - произвольные подмножества множества

{1, 2, . . ., n}, такие что S₀ ∩ S₁ = ∅, |S₀| = a, |S₁| = b. Нетрудно видеть, что па-

ру (S₀, S₁) можно выбрать в точности C^bnC^an-b = M₃ способами.

Положим

{

}

w = (w₁,...,w_n) ∈ W : ∀i ∈ S₀ w_i = 0, ∀i ∈ S₁ w_i = 1

XS0,S1 =

Иными словами, множество XS0,S1 состоит из тех и только тех вершин w ∈ W , чьи

координаты w_i равняются нулю при любом i из S₀, а при любом i из S₁ - единице.

Очевидно, что каждая вершина w ∈ W попадает ровно в C^bkC^an-k множеств XS0,S1.

Значит,

∑

|XS0,S1 | = |W |C^kCn-k ≥ ρV |V (n, k)|C^kCn-k = M1.

(20)

(S0,S1)

Положим

{

}

YS0,S1 =

(w¹, w²) ∈ E(W ) : w¹ ∈ XS0,S1, w² ∈ XS0,S1

Можно показать, что каждое ребро (w¹, w²) ∈ E(W ) попадает ровно в C^btCan-2k+t

множеств YS0,S1 . Значит,

∑

Can-2k+t < ρ_E|E(n, k, t)|C^btCan-2k+t = M₂.

(21)

|YS0,S1 | = |E(W )|

(S0,S1)

Из неравенств (20), (21) следует, что

∑(

)

M₁

|XS0,S1 | - |YS0,S1 |

>M₁ -M₂ ≥

(S0,S1)

Так как суммирование здесь ведется по M₃ возможным парам (S₀, S₁), то существует

хотя бы одна пара (S′0, S′1), такая что

M₁

|X_S′,S′1 | - |YS′0,S′1 | >

2M₃

Рассмотрим подмножество X_S′

,S^′

⊂ W и удалим из него некоторые вершины.

А именно, для каждого ребра (w¹, w²) ∈ E(W ), такого что w¹ ∈ X_S′

,S′1 , w² ∈ XS′₀,S′ ,₁

мы произвольно удалим одну из двух его вершин из X_S′,S′ . Получившееся множе-1

ство обозначим через W^′. Легко видеть, что

M₁

|W^′| ≥ |X_S′

,S′1 | - |YS′₀,S′₁ | >

(22)

2M₃

Покажем, что множество W^′ можно рассматривать как независимое подмноже-

ство вершин графа G(n - a - b, k - b, t - b). Действительно, инъективно сопоставим

каждому элементу w ∈ W^′ вектор

w, получающийся из вектора w удалением коор-

динат с индексами, принадлежащими множествам S′0 и S′1. Ясно, что вектор

w имеет

ровно n-a-b координат, из которых ровно k-b единичных. Кроме того, если какие-

то два вектора w₁ и w₂ имеют ровно t - b общих единиц, то векторы w₁, w₂ ∈ W^′

имеют ровно t общих единиц. Это противоречит тому, что внутри множества W^′ по

построению нет ребер графа G(n, k, t).

Итак, на множество W^′ действительно можно смотреть как на независимое под-

множество вершин графа G(n - a - b, k - b, t - b). В частности, из этого следует, что

|W^′| ≤ α(G(n - a - b, k - b, t - b)).

(23)

Для завершения доказательства остается заметить, что из неравенства (2), га-

рантированного формулировкой теоремы, следует, что неравенства (22) и (23) про-

тиворечат друг другу.

Справедливость неравенства (1) гарантирует, что все использованные в доказа-

тельстве биномиальные коэффициенты были корректно определены.

4.2. Доказательство следствия 2. Пусть множество C(κ, τ) состоит из констант

c > 0, таких что найдется функция α(ε) = α(ε,κ,τ), удовлетворяющая следующим

двум условиям. Во-первых, α(ε) → 0 при ε → 0. Во-вторых, функция

δ = (c + α(ε))

ln² ε

удовлетворяет формулировке следствия 2.

Пусть α, β, γ - произвольные положительные вспомогательные параметры, такие

что α + β < 1, γ < αβ. Положим

ω=

b = b(n) = t(n) - ⌊βωn⌋, a = a(n) = n - 2k(n) + t(n) - ⌊αωn⌋,

|ln ε|

( γ

) ε

δ=

ρ_V = (1 - δ)ⁿ, ρ_E = (1 - ε)ⁿ.

κ - τ ln2 ε

Покажем, что неравенства (2) справедливы для только что определенного набора

параметров при каждом достаточно малом ε для всех достаточно больших n. Из

этого будет следовать, что

∈ C(κ,τ).

κ-τ

С помощью теоремы 1, а также стандартного применения формулы Стирлинга

можно показать, что при n → ∞ в нашем случае

(

)_n

M₁ =

(1 - δ)cκ1c^τ-βωκc1-2κ+τ-αω1-κ + o(1)

(24)

(

)_n

2M₂ =

(1 - ε)cκ1c^τκcκ-τ1-κ c^τ-βωτc1-2κ+τ-αω1-2κ+τ + o(1)

(25)

(

)_n

2M₃α(G(n - a - b, k - b, t - b)) ≤

cτ-βω1c1-2κ+τ-αω1-τ+βωcκ-τ2κ-2τ+αω+βω + o(1)

(26)

Благодаря формулам (24)-(26) проверку справедливости неравенств (2) можно

осуществить, сравнив основания экспонент друг с другом с помощью формулы Тей-

лора.

Например, можно проверить, что при ε → 0 в нашем случае

(1 - δ)cκ1c^τ-βωκc1-2κ+τ-αω1-κ

= 1 + ε(1 - α - β) + o(ε) > 1.

(1 - ε)cκ1c^τκcκ-τ1-κ c^τ-βωc1-2κ+τ-αω

1-2κ+τ

Значит, неравенство M₁ ≥ 2M₂ справедливо при каждом достаточно малом ε для

всех достаточно больших n.

Аналогично можно проверить, что

(1 - δ)cκ1c^τ-βωκc1-2κ+τ-αω1-κ

⁽ αβ - γ + o(1)⁾ ε²

=1+

> 1.

cτ-βω1c1-2κ+τ-αω1-τ+βωcκ-τ2κ-2τ+αω+βω

κ-τ

ln² ε

Следовательно, в нашем случае при каждом достаточно малом ε неравенство M₁ ≥

≥ 2M₃α(G(n - a - b, k - b, t - b)) справедливо для всех достаточно больших n.

Мы показали, что для всех положительных значений параметров α, β, γ, таких

что α + β < 1, γ < αβ, верно, что

∈ C(κ,τ). Устремляя α и β к 1/2, а γ - к их

κ-τ

произведению, мы видим, что любое положительное c <

лежит в множестве

4κ - 4τ

C(κ, τ). Однако для доказательства следствия 2 необходимо доказать более сильное

утверждение о том, что

∈ C(κ,τ).

4κ - 4τ

Пусть 0 < c₁ < c₂ < . . . - какая-либо последовательность, возрастающая к c_∞ =

. Для любого i ∈ N имеем c_i ∈ C(κ, τ). Значит, ∀i ∈ N найдется стремяща-

4κ - 4τ

яся к нулю функция α_i(ε), такая что функция δ_i(ε) = (c_i + α_i(ε))

удовлетворяет

ln² ε

условию следствия 2.

Без ограничения общности можно считать, что функции α_i(ε) принимают толь-

ко неположительные значения. Действительно, пусть для некоторого ε^′ верно, что

′2

α_i(ε^′) > 0. Число (c_i+α_i(ε^′))^ε

удовлетворяет условию следствия 2 для данного ε^′.

ln² ε^′

Так как

′2

c_iε′2

(c_i + α_i(ε^′))

ln² ε^′

′2

ciε

то легко видеть, что число

также удовлетворяет условию следствия 2 для

ln² ε^′

данного ε^′. Значит, функцию α_i(ε) можно переопределить в точке ε^′ нулем.

Так как α_i(ε) стремится к нулю при ε → 0, то для каждого i ≥ 2 найдется ε_i, такое

что c_i + α_i(ε) > ci-1 при любом положительном ε < ε_i. Без ограничения общности

будем считать, что последовательность ε_i монотонно убывает к нулю. Действитель-

но, если это не так, то вместо последовательности ε_i рассмотрим последовательность

ε^′i = min(ε_i, ε′i-1, 1.i), которая также будет удовлетворять требуемому свойству.

Определим неположительную функцию α(ε) при каждом положительном ε с по-

мощью следующего равенства:

^{c₁ + α₁(ε), если ε > ε₂,

c_∞ + α(ε) =

c_i + α_i(ε), если ε ∈ (εi+1; ε_i), i ≥ 2.

Положим δ(ε) = (c_∞ + α(ε))

. По построению при каждом фиксированном

ln² ε

положительном ε^′ найдется такое i, что δ(ε^′) = δ_i(ε^′). Значит, число δ(ε^′) удовлетво-

ряет условию следствия 2 для данного ε^′ при любом ε^′.

Следовательно, единственное, что остается проверить для завершения доказа-

тельства того, что c_∞ ∈ C(κ, τ), это стремление к нулю функции α(ε) при ε → 0.

Пусть i ≥ 2 и ε ∈ (εi+1; ε_i). Тогда

α(ε) = c_i + α_i(ε) - c_∞ < c_i - c_∞ < 0,

(27)

α(ε) = c_i + α_i(ε) - c_∞ > ci-1 - c_∞.

(28)

Из неравенств (27), (28) и того факта, что ε_i → 0 и c_i → c_∞ при i → ∞, следу-

ет, что функция α(ε) действительно стремится к нулю при ε → 0. Это завершает

доказательство следствия 2.

4.3. Доказательство теоремы 5. Отметим, что приведенное здесь доказательство

представляет собой улучшенную версию доказательства из работы [26], более кон-

структивную и работающую с большим числом вспомогательных параметров. По-

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

к использованным в [26].

Положим V = cκ1, D = c^τκcκ-τ1-κ, E = VD = cκ1c^τκcκ-τ1-κ. Как было отмечено в § 1,

при n → ∞ граф G(n, k, t) состоит из (V + o(1))ⁿ вершин и (E + o(1))ⁿ ребер. Для

данного доказательства нам также потребуется знать степени всех вершин в гра-

фе G(n, k, t). В силу симметрии этого графа легко видеть, что степень любой его

вершины равняется

D(n, k, t) = C^tkC^k-tn-k = (D + o(1))ⁿ.

Пусть числа m, ε_m, δ_m = δ(ε_m) гарантированы нам формулировкой теоремы 5.

Отметим, что, с одной стороны, формулировка теоремы 5 гарантирует, что про-

извольное подмножество W ⊂ V (n, k) мощности не менее (1 - δ_m)ⁿ|V (n, k)| содер-

жит не менее (1 - ε_m)ⁿ|E(n, k, t)| = ((1 - ε_m)VD + o(1))ⁿ ребер. С другой стороны,

такое подмножество, очевидно, не может содержать в себе больше |W |D(n, k, t) =

= |W |(D + o(1))ⁿ ребер. Так как эти две оценки не должны противоречить друг

другу при больших n, то оказывается, что справедливо неравенство δ_m ≤ ε_m. Для

дальнейшего изложения нам будет удобно переписать это неравенство в виде

1-δ_m

≥

(29)

(1 - ε_m)D

Формулировка теоремы 5 гарантирует, что

1-δ^m <

m-1 , или, что эквивалент-

1 - εm

1 - δm

но,

< D-m−1. Из последнего неравенства легко следует, что существуют

(1 - εm)D

такие положительные значения вспомогательных параметров f и γ, что f < 1 и

1-δ_m

<γ<D

m-1-f .

(30)

(1 - ε_m)D

Рассмотрим случайный подграф графа G(n, k, t), который получает каждое реб-

ро изначального графа с вероятностью p = γⁿ независимо от других ребер.

⌈

⌉

Положим L =

(1 - δ_m)ⁿ|V (n, k)|

и занумеруем все L-элементные подмножества

вершин графа G(n, k, t) числами от 1 до CL|V(n,k)|. Определим семейство случайных

событий:

X_i = {i-е L-элементное подмножество множества V (n, k) независимо},

i = 1,...,CL|V(n,k)|.

Для каждого s ≥ 3 пусть c_s(G(n, k, t)) - количество циклов длины s в графе

G(n, k, t). Определим еще одно семейство случайных событий:

Y sj = {j-й s-цикл графа G(n,k,t) остался s-циклом}, j = 1,...,c_s(G(n,k,t)).

Заметим, что для завершения доказательства теоремы 5 достаточно показать, что

(_CL

(_c

))

⋀

X_i

(31)

i=1

s=3

j=1

для всех достаточно больших n. Действительно, если это так, то при всех достаточно

больших n в дистанционном графе G(n, k, t) существует подграф H_n, такой что для

него справедливо следующее. Во-первых, его обхват строго больше m, так как все

циклы с длинами, не превосходящими m, присутствовавшие в G(n, k, t), в граф H_n не

100

вошли. Во-вторых, мощность любого независимого подмножества вершин графа H_n

строго меньше L. Значит,

(

)_n

|V (n, k)|

χ(H_n) ≥

+ o(1)

1-δ_m

Следовательно,

(

)_n

ξ_m(Rⁿ) ≥

+ o(1)

ξ_m ≥

1-δ_m

Обосновать справедливость неравенства (31) можно с помощью локальной лем-

мы Ловаса (в таком виде ее можно найти, например, в [26]).

Лемма. Пусть A₁,...,An - события в произвольном вероятностном про-

странстве. Пусть J₁, . . ., J_n - подмножества множества {1, . . ., n}, такие что

каждое A_i независимо от алгебры, порожденной событиями A_j , j ∈ J_i ∪{i}. Пусть

существуют положительные числа ρ(A_i), такие что при каждом i ∈ {1, . . . , n}

справедливы неравенства

0 < ρ(A_i)P(A_i) < 0,68,

(32)

∑

ln ρ(A_i) > 2

ρ(A_j ) P(A_j ).

(33)

j∈Ji

Тогда

∏(

)

P A_i

1 - ρ(A_i)P(A_i)

> 0.

i=1

Для того чтобы применить эту лемму к нашему случаю, необходимо оценить

вероятности событий X_i и Y^sj, а также указать зависимости между ними. Пусть a_i -

количество ребер графа G(n, k, t), находящихся в i-м L-элементном подмножестве

его вершин. Формулировка теоремы 5 гарантирует, что a_i ≥ (1 - ε_m)ⁿ|E(n, k, t)| =

= ((1 - ε_m)E + o(1))ⁿ. Ясно, что

P(X_i) = (1 - p)ai < e-pai ≤ e-(γ(1-εm)E+o(1))n ,

(34)

P(Y^sj) = p^s = γ^ns.

(35)

Нетрудно видеть, что все эти вероятности стремятся к нулю с ростом n. Действи-

тельно, для вероятностей из (35) это очевидно, а для вероятностей из (34) это может

быть доказано следующим образом:

1-δ_m

γ(1 - ε_m)E > 1 ⇐ γ >

⇐ γ >

(36)

(1 - ε_m)DV

(1 - ε_m)D

где последнее неравенство в этой цепочке - это неравенство (30), справедливость

которого гарантирована выбором параметров.

Пусть J^sy(X_i′ ) состоит из тех событий Y^sj, соответствующие которым s-циклы

имеют хотя бы одно общее ребро с i^′-м L-элементным подмножеством V (n, k). Пусть

J_x(X_i′ ) состоит из вообще всех событий X_i и

)

⋃

J (X_i′ ) = J_x(X_i′ )

J^sy(X_i′ )

s=3

Нетрудно видеть, что X_i′ не зависит от алгебры, порожденной событиями, не по-

павшими в J(X_i′). Действительно, в эту алгебру не попали только те события Y^sj,

101

соответствующие которым s-циклы не имеют общих ребер с i^′-м L-элементным под-

множеством V (n, k). Ясно, что событие X_i′ независимо со всеми такими Y^sj.

′

) состоит из тех событий Y sj , соответствующие которым

s-циклы имеют по крайней мере одно общее ребро с j^′-м s^′-циклом графа G(n, k, t),

′

) состоит из вообще всех событий X_i. Положим

)

⋃

′

)

′

)

s=3

′

не зависит от алгебры, порожденной событи-

′

Оценим сверху мощности введенных множеств событий. По определению

)_L

⁽e|V (n, k)|

′

)| = CL|V(n,k)| ≤

=e((1-δm)V+o(1))n.

(37)

Для оценки мощности множества J^sy(X_i′) заметим, что ребро, по которому i^′-е L-эле-

ментное множество пересекается с некоторым s-циклом, может быть выбрано не

более чем a_i′ способами. Так как степень каждой вершины в графе G(n, k, t) рав-

на D(n, k, t), то дополнить это выделенное ребро до s-цикла можно не более чем

D(n, k, t)s-2 способами. Значит,

|J^sy(X_i′ )| ≤ a_i′ (Ds-2 + o(1))ⁿ.

(38)

Аналогично

′

)| ≤ s^′D(n, k, t)s-2 = (Ds-2 + o(1))ⁿ.

(39)

Положим ρ(Y^sj) = e, ρ(X_i) = eaiγn(1+f) и убедимся в возможности применения

леммы в нашем случае. Справедливость неравенств (32) для Y^sj следует из того,

что P(Y^sj) → 0 при n → ∞, как гарантирует равенство (35). Тот факт, что неравен-

ства (32) выполнены и для X_i, следует из оценки (34) и цепочки неравенств

ρ(X_i) P(X_i) ≤ eai(γn(1+f)-γn) ≤ e((1-εm)E+o(1))n(γn(1+f)-γn) =

=e-(γ(1-εm)E+o(1))n → 0

(40)

при n → ∞, так как γ(1 - ε_m)E > 1 в силу (36).

Таким образом, для завершения доказательства теоремы 5 остается только убе-

диться в справедливости неравенств (33) в нашем случае. Из (37)-(39) следует, что

для достижения данной цели достаточно обосновать, что

⎧

⎪

CL|V(n,k)|∑

∑

⎨

a_i′ γn(1+f) > 2

ρ(X_i) P(X_i) + 2e a_i′ γ^ns(Ds-2 + o(1))ⁿ,

i=1

s=3

(41)

⎪

CL|V(n,k)|∑

∑

^⎩1 > 2

ρ(X_i) P(X_i) + 2e γ^ns(Ds-2 + o(1))ⁿ.

i=1

s=3

Воспользовавшись неравенством (40) и оценкой (37) для биномиального коэф-

фициента, видим, что (41) вытекает из справедливости системы

⎧

∑

^⎨a_i′ γn(1+f) > e((1-δm)V+o(1))n-(γ(1-εm)E+o(1))n + 2e

a_i′ γ^ns(Ds-2 + o(1))ⁿ,

s=3

(42)

∑

^⎩1 > e((1-δm)V+o(1))n-(γ(1-εm)E+o(1))n + 2e

γ^ns(Ds-2 + o(1))ⁿ.

s=3

102

Из (29) и (30) следует, что γD > 1, а значит, наибольшее слагаемое в суммах по s

в (41) соответствует s = m. Воспользовавшись этим, а также разделив обе части пер-

вого неравенства из (42) на a_i′ ≥ 1, получим, что для обоснования справедливости

системы (42) достаточно показать, что

^{γn(1+f) > e((1-δm)V+o(1))n-(γ(1-εm)E+o(1))n + (γ^mDm-2 + o(1))ⁿ,

(43)

1 > e((1-δm)V+o(1))n-(γ(1-εm)E+o(1))n + (γ^mDm-2 + o(1))ⁿ.

Ясно, что первое неравенство системы (43) сильнее второго. Кроме того, нетрудно

1+f -m

видеть, что с учетом неравенства

> 1, вытекающего из (30), первое нера-

Dm-2

венство системы (43) может быть переписано в виде

⁽γ1+f-m

+ o(1)

> 1 + (γ^mDm-2 + o(1))^-ne((1-δm)V+o(1))n-(γ(1-εm)E+o(1))n. (44)

Dm-2

Левая часть этого неравенства экспоненциально стремится к бесконечности с

ростом n, а правая сверхэкспоненциально быстро стремится к единице, так как

γ(1 - ε_m)E > (1 - δ_m)V в силу неравенства (30). Значит, неравенство (44) верно

при всех достаточно больших n, что и завершает доказательство теоремы 5.

4.4. Доказательство следствия 3 и обоснование оценок из таблицы 1. Пусть κ и τ -

некоторые фиксированные параметры, такие что 0 < τ < κ < 1 и 1 - 2κ + τ > 0.

Покажем, что всегда можно найти натуральнозначные функции k(n) и t(n), такие

что, во-первых, k(n) ∼ κn и t(n) ∼ τn при n → ∞, и во-вторых, k(n) - t(n) является

простым числом для любого n.

Доказано (см., например, [41]), что разность между натуральным числом m и

ближайшим к нему простым числом равна o(m) при m → ∞. С помощью этого

факта построить требуемые функции k(n) и t(n) несложно. Действительно, поло-

жим, например, k(n) = ⌊κn⌋ и определим t(n) как разность между величиной k(n)

и ближайшим к ⌊κn⌋-⌊τn⌋ простым числом. Построенные таким образом функции

удовлетворяют обоим требуемым свойствам.

Теперь для оценки ξ_m мы можем воспользоваться теоремой 5. Заметим, что при

больших m верно

(

)

ln c^τκ + ln cκ-τ1-κ

)

c^τκcκ-τ1-κ

m-1 = 1 +

κ-τ

(

)

ln c^τκ + ln c

1-κ

⁽1⁾

Значит, найдется ε_m =

, такое что

c^τκcκ-τ1-κ

m-1 . При

1 - εm

(

)

1 - δ(εm)

этом неравенство

c^τκcκ-τ1-κ

m-1 , очевидно, также окажется выполнен-

1 - εm

ным, где δ(·) - функция, определенная в следствии 2. Значит, теорема 5 гарантирует,

что

(

)

ln c^τκ + ln c^κ-τ

1 + o(1)

1-κ

ξ_m ≥

=1+

(45)

1 - δ(ε_m)

⁽1 + o(1)⁾ ε2m

4κ - 4τ

m² lnm

4κ - 4τ ln²

εm

Подстановка в (45) значений κ = 0,5, τ = 0,38 завершает доказательство следствия 3.

Доказательства оценок из табл. 1 повторяют только что проделанное доказа-

тельство следствия 3 за тем лишь исключением, что теперь мы будем пользоваться

непосредственно теоремой 3, а не огрубляющим ее следствием 2. Величины a и b,

участвующие в формулировке теоремы 3, мы определим как произвольные функ-

ции a = a(n) ∼ αn, b = b(n) ∼ βn, где α, β - вспомогательные параметры, такие что

103

Таблица 3

Используемые значения вспомогательных параметров

1-δ

1-ε

0,468

0,406

0,408

0,320

0,959376

0,7960

0,478

0,416

0,426

0,382

0,987769

0,8718

0,465

0,409

0,460

0,388

0,994702

0,9113

0,478

0,422

0,452

0,408

0,997185

0,9297

0,481

0,408

0,434

0,396

0,998302

0,9315

0,484

0,404

0,426

0,394

0,998892

0,9381

0,458

0,383

0,459

0,375

0,999229

0,9479

0,464

0,396

0,461

0,390

0,999436

0,9563

0 < β < τ и 0 < α < 1 -2κ+ τ. Плотности ρ_V и ρ_E из теоремы 3 положим равными

(1 - δ)ⁿ и (1 - ε)ⁿ соответственно, где δ и ε - еще два вспомогательных параметра.

Наборы конкретных значений κ, τ, α, β, δ, ε, подстановка которых завершает обосно-

вание оценок из табл. 1, оформлены в виде табл. 3.

4.5. Доказательство следствия 4. Пусть κ и τ - некоторые фиксированные пара-

метры, такие что 0 < τ < κ < 1 и 1-2κ+τ > 0. В п. 4.3 мы показали, что существуют

натуральнозначные функции k(n) и t(n), такие что, во-первых, k(n) ∼ κn и t(n) ∼ τn

при n → ∞, и во-вторых, k(n) - t(n) является простым числом для любого n.

Для применения теоремы 3 нам надо определить значения a, b, ρ_V и ρ_E . Положим

a = a(n) ∼ αn, b = b(n) ∼ βn, где α,β - произвольные вспомогательные параметры,

такие что 0 < β < τ и 0 < α < 1 - 2κ + τ. Плотности ρ_V и ρ_E определим равными

(1 - δ)ⁿ и (1 - ε)ⁿ соответственно, где δ выбирается произвольно, а ε - так, чтобы

α(1, κ, τ )

выполнялось равенство (1 - ε) =

c^κ

Если теперь к набору параметров κ, τ, α, β, δ, ε применима теорема 3, то она га-

рантирует, что любое подмножество W вершин графа G(n, k, t) мощности не менее

(1 - δ)ⁿ|V (n, k)| содержит не менее (α(1, κ, τ)c^τκcκ-τ1-κ + o(1))ⁿ ребер. Так как степень

любой вершины графа G(n, k, t) равна (c^τκcκ-τ1-κ + o(1))ⁿ, то по принципу Дирихле

множество W обязательно содержит вершину w, такую что она имеет не меньше

(α(1, κ, τ) + o(1))ⁿ соседей в W . Из теоремы 1 следует, что по крайней мере два ее

соседа соединены ребром. Значит, любое подмножество W вершин графа G(n, k, t)

мощности не менее (1 - δ)ⁿ|V (n, k)| содержит треугольник.

Покажем, что из этого следует

(

)_n

χ(Rⁿ, S₂) ≥

+ o(1)

(46)

1-δ

Действительно, предположим, что неравенство (46) не верно. Без ограничения общ-

ности будем предполагать, что длина стороны равностороннего треугольника S₂

равняется 1. Рассмотрим множество V (n, k) ⊂ Rⁿ. Нетрудно видеть, что ребро гра-

фа G(n, k, t) соединяет две вершины V (n, k) тогда и только тогда, когда расстояние

√

между ними равно

2k - 2t. После подходящей гомотетии множества V (n, k) можно

считать, что ребра в нем соединяют точки на единичном расстоянии. С одной сто-

роны, в силу нашего предположения, получившееся множество можно раскрасить

(

)_n

менее чем в

+ o(1)

цветов так, чтобы в нем не существовало одноцветных

1-δ

равносторонних единичных треугольников. С другой стороны, принцип Дирихле

гарантирует, что при такой раскраске найдется одноцветное множество W мощно-

сти не менее (1 - δ)ⁿ|V (n, k)|. Как мы доказали выше, в нем обязательно найдется

равносторонний единичный треугольник. Полученное противоречие завершает обос-

нование неравенства (46).

104

Оценка из следствия 4 теперь получается простой подстановкой значений вспо-

могательных параметров

κ=

τ =

α = β = 0,42211,

1 - δ = 0,98617.

Автор благодарит Валентину Рыбникову за существенную помощь в организации

компьютерных вычислений.

СПИСОК ЛИТЕРАТУРЫ

de Grey A.D.N.J. The Chromatic Number of the Plane Is at Least 5 // Geombinatorics.

2018. V. 28. № 1. P. 18-31.

Райгородский А.М. О хроматическом числе пространства // УМН. 2000. Т. 55. № 2.

С. 147-148.

Brass P., Moser W., Pach J. Research Problems in Discrete Geometry. New York: Springer,

2005.

Soifer A. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life

of Its Creators. New York: Springer, 2009.

Raigorodskii A.M. Coloring Distance Graphs and Graphs of Diameters // Thirty Essays on

Geometric Graph Theory. New York: Springer, 2013. P. 429-460.

Raigorodskii A.M. Cliques and Cycles in Distance Graphs and Graphs of Diameters //

Discrete Geometry and Algebraic Combinatorics. Providence, RI: Amer. Math. Soc., 2014.

P. 93-109.

Bassalygo L., Cohen G., Zémor G. Codes with Forbidden Distances // Discrete Math. 2000.

V. 213. № 1-3. P. 3-11.

Raigorodskii A.M. Combinatorial Geometry and Coding Theory // Fund. Inform. 2016.

V. 145. № 3. P. 359-369.

Frankl P., Wilson R.M. Intersection Theorems with Geometric Consequences // Combina-

torica. 1981. V. 1. № 4. P. 357-368.

10.

Бобу А.В., Куприянов А.Э., Райгородский А.М. Асимптотическое исследование задачи

о максимальном числе ребер однородного гиперграфа с одним запрещенным пересече-

нием // Матем. сб. 2016. Т. 207. № 5. С. 17-42.

11.

Пономаренко Е.И., Райгородский А.М. Новые оценки в задаче о числе ребер гипергра-

фа с запретами на пересечения // Пробл. передачи информ. 2013. Т. 49. № 4. С. 98-104.

12.

Райгородский А.М., Сагдеев А.А. Об одной оценке в экстремальной комбинаторике //

ДАН. 2018. Т. 478. № 3. С. 271-273.

13.

Сагдеев А.А. Улучшенная теорема Франкла - Рёдля и некоторые ее геометрические

следствия // Пробл. передачи информ. 2018. Т. 54. № 2. С. 45-72.

14.

Frankl P., Rödl V. Forbidden Intersections // Trans. Amer. Math. Soc. 1987. V. 300. № 1.

P. 259-286.

15.

Kupavskii A., Zakharov D. Regular Bipartite Graphs and Intersecting Families // J. Combin.

Theory Ser. A. 2018. V. 155. P. 180-189.

16.

Frankl P., Kupavskii A. Partition-Free Families of Sets // Proc. Lond. Math. Soc. (3). 2019.

V. 119. № 2. P. 440-468.

17.

Cherkashin D., Kulikov A., Raigorodskii A. On the Chromatic Numbers of Small-Dimen-

sional Euclidean Spaces // Discrete Appl. Math. 2018. V. 243. P. 125-131.

18.

Боголюбский Л.И., Райгородский А.М. Замечание о нижних оценках хроматических

чисел пространств малой размерности с метриками ℓ1 и ℓ2 // Матем. заметки. 2019.

V. 105. № 2. P. 187-213.

19.

Захаров Д.А., Райгородский А.М. Клико-хроматические числа графов пересечений //

Матем. заметки. 2019. V. 105. № 1. P. 142-144.

20.

Костина О.А. О нижних оценках хроматического числа сферы // Матем. заметки.

2019. V. 105. № 1. P. 18-31.

105

21.

Райгородский А.М., Шишунов Е.Д. О числах независимости некоторых дистанционных

графов с вершинами в {-1, 0, 1}ⁿ // ДАН. 2019. V. 485. № 3. P. 269-271.

22.

Райгородский А.М., Шишунов Е.Д. О числах независимости дистанционных графов

с вершинами в {-1, 0, 1}ⁿ // ДАН. 2019. V. 488. № 5. P. 486-487.

23.

Пушняков Ф.А. О количествах ребер в порожденных подграфах некоторых дистанци-

онных графов // Матем. заметки. 2019. V. 105. № 4. P. 592-602.

24.

Frankl N., Kupavskii A. Nearly k-Distance Sets // Acta Math. Univ. Comenian. (N.S.).

2019. V. 88. № 3. P. 689-693.

25.

Sagdeev A.A., Raigorodskii A.M. On a Frankl-Wilson Theorem and Its Geometric Corol-

laries // Acta Math. Univ. Comenian. (N.S.). 2019. V. 88. № 3. P. 1029-1033.

26.

Kupavskii A.B. Distance Graphs with Large Chromatic Number and Arbitrary Girth //

Mosc. J. Comb. Number Theory. 2012. V. 2. № 2. P. 52-62.

27.

Сагдеев А.А. О теореме Франкла - Рэдла // Изв. РАН. Сер. матем. 2018. Т. 82. № 6.

С. 128-157.

28.

Демёхин Е.Е., Райгородский А.М., Рубанов О.И. Дистанционные графы, имеющие

большое хроматическое число и не содержащие клик или циклов заданного размера //

Матем. сб. 2013. Т. 204. № 4. С. 49-78.

29.

Kř´ıž I. Permutation Groups in Euclidean Ramsey Theory // Proc. Amer. Math. Soc. 1991.

V. 112. № 3. P. 899-907.

30.

Leader I., Russell P.A., Walters M. Transitive Sets in Euclidean Ramsey Theory // J. Com-

bin. Theory Ser. A. 2012. V. 119. № 2. P. 382-396.

31.

Просанов Р.И. Верхние оценки хроматических чисел евклидовых пространств с запре-

щенными рамсеевскими множествами // Матем. заметки. 2018. Т. 103. № 2. С. 248-257.

32.

Просанов Р.И. Контрпримеры к гипотезе Борсука, имеющие большой обхват // Матем.

заметки. 2019. V. 105. № 6. P. 890-898.

33.

Сагдеев А.А. Экспоненциально рамсеевские множества // Пробл. передачи информ.

2018. V. 54. № 4. P. 82-109.

34.

Сагдеев А.А. O хроматических числах, соответствующих экспоненциально рамсеев-

ским множествам // Зап. научн. сем. ПОМИ. Т. 475. СПб.: Изд-во ПОМИ, 2018.

С. 174-189.

35.

Keevash P., Long E. Frankl-Rödl-type Theorems for Codes and Permutations // Trans.

Amer. Math. Soc. 2017. V. 369. № 2. P. 1147-1162.

36.

Gowers W.T. A New Proof of Szemerédi’s Theorem // Geom. Funct. Anal. 2011. V. 11.

№ 3. P. 465-588.

37.

Сагдеев А.А. О разбиении нечетного числа на три простых слагаемых в заранее задан-

ной пропорции // Матем. заметки. 2019. V. 106. № 1. P. 95-107.

38.

Виноградов И.М. Представление нечетного числа суммою трех простых чисел // ДАН

СССР. 1937. Т. 15. № 6/7. С. 291-294.

39.

Helfgott H.A. The Ternary Goldbach Conjecture Is True // arXiv:1312.7748 [math.NT],

2013.

40.

Haselgrove C.B. Some Theorems in the Analytic Theory of Numbers // J. London Math.

Soc. 1951. V. 26. № 4. P. 273-277.

41.

Baker R.C., Harman G., Pintz J. The Difference between Consecutive Primes. II // Proc.

London Math. Soc. (3). 2001. V. 83. № 3. P. 532-562.

42.

Звонарев А.Е., Райгородский А.М., Самиров Д.В., Харламова А.А. О хроматическом

числе пространства с запрещенным равносторонним треугольником // Матем. сб. 2014.

Т. 205. № 9. С. 97-120.

Сагдеев Арсений Алексеевич

Поступила в редакцию

Московский физико-технический институт

02.07.2019

(государственный университет), лаборатория

После доработки

продвинутой комбинаторики и сетевых приложений

09.10.2019

xp1@protonmail.com

Принята к публикации

12.11.2019

106