О больших подграфах графа расстояний, имеющих маленькое хроматическое число

Аннотация

В настоящей работе доказано, что в каждом дистанционном графе на плоскости есть индуцированный подграф, содержащий более 91 процента вершин исходного графа и имеющий хроматическое число, не большее четырех. С помощью этого результата найден порядок роста пороговой вероятности для свойства случайного графа быть изоморфным некоторому дистанционному графу на плоскости. Предложены обобщения результатов на другие размерности.

Полный текст

1. ВВЕДЕНИЕ И ФОРМУЛИРОВКИ ГЕОМЕТРИЧЕСКИХ РЕЗУЛЬТАТОВ Хроматическое число χ(Rd) пространства Rd - это наименьшее количество цветов,в которые можно так покрасить Rd, чтобы среди точек одного цвета не нашлось пары точек на расстоянии единица, т. е. χ(Rd)= min {k ∈ N : ∃V1,..., Vk , Rd = V1 LJ ... LJ Vk, ∀i, ∀x, y ∈ Vi, ρ(x, y) /= 1}, где ρ - обычное евклидово расстояние. Легко показать, что для любого d величина χ(Rd) конечна. Проблема отыскания хроматического числа пространства была впервые поставлена на рубеже 40-х - 50-х годов ХХ века (см. [3, 5, 8, 9, 12, 17, 20, 21]). Несмотря на значительный интерес, вызванный этой проблемой, она до сих пор, по существу, остается нерешенной. Конечно, χ(R1) = 2, однако уже для плоскости лучшее, что мы знаем, это оценка Для трехмерного пространства мы имеем 4 χ(R2) 7. 6 χ(R3) 15 (см. [13, 19]), наконец для растущей размерности (1.239 ... + o(1))d χ(Rd) (3 + o(1))d (см. [3, 4, 6, 18]). Поставленная задача может быть переформулирована в терминах теории графов. Прежде всего, дистанционным графом (или графом расстояний) назовем конечный граф G = (V, E), вершины которого суть точки евклидова пространства, а ребра соединяют только пары точек, отстоящих друг от друга на расстояние единица. Иными словами, V ⊂ Rd, |V | < ∞, E ⊆ {(x, y) ∈ V × V : ρ(x, y)= 1}. Напомним, что хроматическое число χ(G) графа G = (V, E) - это наименьшее количество цветов, в которые можно так покрасить его вершины, чтобы вершины одного цвета не соединялись ребром, т. е. χ(G)= min {k ∈ N : ∃V1,..., Vk , V = V1 LJ ... LJ Vk, ∀i, ∀x, y ∈ Vi, (x, y) ∈/ E}. П. Эрдеш и Н. де Брёйн фактически доказали (см. [15]), что χ(Rd)= max χ(G), где максимум берется по всем графам расстояний в Rd. Таким образом, изучение хроматических чисел графов расстояний играет исключительную роль при исследовании проблемы отыскания хроматического числа пространства. В основной части настоящей работы мы будем рассматривать только случай евклидовой плоскости. Тот факт, что χ(R2) 7, означает, конечно, что для любого графа расстояний G = (V, E) Qc 2013 РУДН 64 О БОЛЬШИХ ПОДГРАФАХ ГРАФА РАССТОЯНИЙ, ИМЕЮЩИХ МАЛЕНЬКОЕ ХРОМАТИЧЕСКОЕ ЧИСЛО 65 на плоскости χ(G) 7. Как следствие, α(G) |V | , коль скоро через α(G) мы обозначили число 7 независимости графа G, т. е. наибольшее количество его вершин, никакие две из которых не соединены ребром: α(G)= max {|V ×| : V × ⊂ V, ∀x, y ∈ V ×, (x, y) ∈/ E}. Таким образом, в любом «двумерном» графе расстояний на n вершинах найдется индуцированный подграф, имеющий не менее n вершин и хроматическое число 1. Это утверждение допускает 7 ряд нетривиальных обобщений и уточнений. Нам удалось доказать следующие результаты для графов расстояний на плоскости. Теорема 1. В любом графе расстояний G = (V, E) на n вершинах найдется такой индуциn рованный подграф G× = (V ×, E×), что |V ×| κ и χ(G×)= 1, где κ = 4.36 ... Теорема 2. В любом графе расстояний G = (V, E) на n вершинах найдется такой индуци- 2n рованный подграф G× = (V ×, E×), что |V ×| κ и χ(G×) 2. Теорема 3. В любом графе расстояний G = (V, E) на n вершинах найдется такой индуци- 3n рованный подграф G× = (V ×, E×), что |V ×| κ и χ(G×) 3. Теорема 4. В любом графе расстояний G = (V, E) на n вершинах найдется такой индуци- 4n рованный подграф G× = (V ×, E×), что |V ×| κ и χ(G×) 4. Наиболее интересной является теорема 4. Фактически в ней утверждается, что в каждом графе расстояний на плоскости есть индуцированный подграф, который почти целиком совпадает с исходным графом (содержит не менее 91.7% его вершин) и допускает раскраску в 4 цвета. Если бы в этом утверждении величину 91.7 удалось заменить на 100, то, ввиду теоремы Эрдеша-де Брёйна, это бы означало, что χ(R2)= 4. Заметим, что, конечно, теоремы 1-3 являются следствиями теоремы 4. Однако мы будем доказывать их именно в таком порядке из соображений удобства. Заметим также, что теорема 1 встречалась ранее в литературе, но мы начнем именно с ее доказательства в разделе 3: так проще будет описывать общий подход. Итак, дальнейшая структура статьи следующая. В разделе 2 мы сформулируем задачу о реализации случайного графа графом расстояний на плоскости. Там же мы приведем соответствующие основные утверждения - теоремы 5 и 6. В третьем разделе мы докажем теоремы 1-4, а также новую теорему 8, являющуюся главным инструментом в наших доказательствах. В разделе 4 мы докажем теоремы 5, 6. Пятый раздел мы посвятим обобщениям полученных результатов на другие размерности. 2. ПОСТАНОВКА ВЕРОЯТНОСТНОЙ ЗАДАЧИ И ФОРМУЛИРОВКИ СООТВЕТСТВУЮЩИХ РЕЗУЛЬТАТОВ Зачастую задачи теории графов допускают нетривиальную интерпретацию в терминах случайного графа. Напомним, что одной из наиболее популярных моделей случайного графа является модель, предложенная П. Эрдешем и А. Реньи на рубеже 50-х - 60-х годов XX века (см. [1, 7, 10, 11, 16]). Речь идет о вероятностном пространстве G(n, p)= (Ωn, Bn, Pn). Здесь Ωn = {G = (V, E): |V | = n} - множество всевозможных графов на n вершинах (без петель и кратных ребер), сигма-алгебра Bn представляет собой множество всех подмножеств Ωn, а 2 Pn(G)= p|E|(1 - p)Cn-|E|. Иначе говоря, можно считать, что ребра случайного графа появляются независимо друг от друга с вероятностью p. Заметим, что в модели Эрдеша-Реньи величина p может зависеть от n. Нас будет интересовать в дальнейшем, с какой вероятностью случайный граф в модели G(n, p) допускает реализацию на плоскости в качестве графа расстояний. Как это часто бывает в науке 66 А. А. КОКОТКИН, А. М. РАЙГОРОДСКИЙ o случайных графах, при одних значениях p эта вероятность будет стремиться к нулю, а при других - к единице. Определим некоторую критическую величину p, отвечающую за вышеупомянутый «фазовый переход», следующим образом: ( 1 p∗(n)= sup p ∈ [0, 1] : Pn(G реализуется на плоскости как граф расстояний) > 2 . Такая величина называется пороговой вероятностью, и она определена корректно ввиду классических результатов о существовании пороговых вероятностей для монотонных свойств случайных графов (см. [11]). Мы можем доказать следующие результаты. Теорема 5. При p = c , где c < 1, выполнено n Pn(G реализуется на плоскости как граф расстояний) → 1, n → ∞. Теорема 6. При p = c , где c > t = 14.797 ..., выполнено n 0 Pn(G реализуется на плоскости как граф расстояний) → 0, n → ∞. Теоремы 5 и 6 означают, что 1 - ε p∗(n) t0 + ε со сколь угодно малым положительным ε и n n n n0(ε). Тем самым, мы знаем порядок роста пороговой вероятности. 3. ДОКАЗАТЕЛЬСТВА ГЕОМЕТРИЧЕСКИХ РЕЗУЛЬТАТОВ 1. Доказательство теоремы 1. Доказательство. Прежде всего напомним, что верхней плотностью измеримого множества S ⊂ Rd называется величина ν = ν(S)= lim sup μ(S ∩ Cs) , s→∞ Cs μ(Cs) где супремум берется по всем кубам со стороной s, а μ - это мера Лебега. Будем говорить, далее, что на множестве S реализуется расстояние a, если найдутся такие точки x, y ∈ S, что ρ(x, y)= a. Нам понадобится следующая теорема, доказанная Д. Ларманом и К. А. Роджерсом в 1972 году (см. [18]). Теорема 7. Пусть в Rd существует граф расстояний G = (V, E), |V | = n, с числом независимости α(G) < D. Тогда, если измеримое множество в Rd имеет верхнюю плотность ν D/n, то все расстояния a > 0 на этом множестве реализуются. Сами Ларман и Роджерс формулировали теорему в несколько иных терминах, но нам потребуется именно такая переформулировка. Из нее мы немедленно получаем Следствие 1. Если в Rd найдется такое измеримое множество с верхней плотностью ν ν0, что на нем какое-либо расстояние a > 0 не реализуется, то для любого графа расстояний G в Rd, имеющего n вершин, выполнено α(G) ν0n. В действительности следствие 1 - это просто еще одна переформулировка теоремы 7. Х. Крофт в своей работе (см. [14, 18]) 1967 года приводит пример измеримого множества на плоскостис верхней плотностью ν = ν0 = 0.2293 ... и без расстояния единица. Из этого примера и следствия 1 немедленно получаем существование в каждом n-вершинном дистанционном графе на плоскости индуцированного подграфа G× = (V ×, E×), у которого |V ×| ν0n и χ(G×) = 1. Замечая, 1 что ν0 = , завершаем доказательство теоремы 1. κ Подчеркнем, что результат Крофта по-прежнему остается лучшим из известных, а потому в рамках предложенного подхода теорема 1 дает наиболее точную оценку. Поскольку конструкция Крофта нам еще понадобится, опишем ее подробнее. О БОЛЬШИХ ПОДГРАФАХ ГРАФА РАССТОЯНИЙ, ИМЕЮЩИХ МАЛЕНЬКОЕ ХРОМАТИЧЕСКОЕ ЧИСЛО 67 Пусть на плоскости дана правильная треугольная решетка Λε, в которой расстояние между ближайшими узлами равно 2 - 2ε. Здесь ε - достаточно маленькое число, которое будет опти- 1 мально подобрано позднее. Рассмотрим круг Bε радиуса 2 - ε и правильный шестиугольник H, центр симметрии которого совпадает с центром Bε и длина диагонали которого равна единице. Положим Tε = (Bε ∩ H) \ ∂(Bε ∩ H) - открытая «черепаха». Для каждого x ∈ Λε обозначим через ϕx(Tε) копию множества Tε, получающуюся в результате параллельного переноса, при котором центр симметрии Tε переходит в x. Множество Крофта - это Kε = J x∈Λ ϕx(Tε). Выбор величины ε осуществляется так, чтобы значение ν(Kε) было наибольшим. 2. Доказательства теорем 2-4. Доказательство. Для доказательства нам потребуется новый результат, являющийся усилением теоремы Лармана-Роджерса. Теорема 8. Пусть в Rd задан некоторый граф расстояний G = (V, E), |V | = n. Предположим, что существуют такие числа k ∈ N и ν0 ∈ (0, 1), что для любого индуцированного подграфа G× = (V ×, E×) c |V ×| [ν0n] выполнено χ(G×) > k. Тогда для всякого набора измеримых множеств S1, S2,..., Sk в Rd с условием, что множество S = S1 ∪ S2 ∪ ... ∪ Sk имеет верхнюю плотность ν ν0, верно, что каково бы ни было a > 0, найдется Si, на котором реализуется расстояние a. Следствие 2. Если для данного ν0 ∈ (0, 1) найдутся такие k множеств S1, S2,..., Sk в Rd, что верхняя плотность множества S = S1 ∪ S2 ∪ ... ∪ Sk не меньше ν0 и некоторое расстояние a > 0 не достигается ни на одном из Si, то для любого графа расстояний G в Rd, имеющего n вершин, найдется индуцированный подграф G× = (V ×, E×) с |V ×| [ν0n], для которого выполнено χ(G×) k. Следствие очевидно (собственно, оно является переформулировкой теоремы), а теорему 8 мы докажем в пункте 3.3. Сейчас мы с помощью следствия завершим доказательства теорем 2-4. Сделаем параллельный перенос множества Крофта Kε вдоль линий решетки на расстояние 1-ε. Получим четыре конгруэнтных непересекающихся множества. Берем 2, 3, 4 из них и получаем, с помощью следствия, доказательство теоремы 2, 3, 4 соответственно. 3. Доказательство теоремы 8. Доказательство. Пусть x1, x2,..., xn - вершины данного графа. Зафиксируем измеримые множества S1, S2, ..., Sk, удовлетворяющие условию теоремы. Тогда для S = S1 ∪ S2 ∪ ... ∪ Sk выполнено lim sup μ(S ∩ Cs) 1 ν0 > ν0 - , s→∞ Cs μ(Cs) n где супремум, напомним, берется по всем кубам со стороной s. Значит, по определению верхнего предела существует δ > 0, прикотором для любого s0 найдется такое s > s0, что sup Cs μ(S ∩ Cs) μ(Cs) 1 δ > ν0 - n + n. Далее по определению супремума получаем, что при прежних ограничениях на δ, s0 и s существует такой куб Cs, что μ(S ∩ Cs) > ν - 1 + δ . (∗) μ(Cs) 0 n n Пусть a > 0 - произвольное фиксированное число. Мы хотим доказать, что найдется Si, на котором реализуется расстояние a. Рассмотрим векторы ax1, ax2,..., axn. Покажем теперь, что существуют такие s и Cs, с которыми для любого i = 1,...,n выполнено - . μ({S + axi}∩Cs) > ν 1 μ(Cs) 0 n 68 А. А. КОКОТКИН, А. М. РАЙГОРОДСКИЙ Введем обозначения: axi = (x1,..., xd), b = max{xj }, где i = 1,..., n, j = 1,..., d. i i Возьмем s0 настолько большим, что sd i,j i d d 0 - (s0 - 2b) < δ . s 0 n Это, конечно, можно сделать, так как выражение в левой части неравенства с ростом s0 стремится к нулю. Мы знаем (см. (*)), что для этого s0 найдутся такие s > s0 и Cs, что - + . μ(S ∩ Cs) > ν 1 δ Положим μ(Cs) 0 n n B = {y ∈ Cs : ρ(y, ∂Cs) < b}, C˜s = Cs \ B. Заметим, что та часть S, которая содержалась в C˜s, после сдвига на axi останется в Cs. Тогда для каждого i получаем: μ({S + axi}∩Cs) μ(S ∩ C˜s) = μ(S ∩ Cs) μ(S ∩ B) μ(S ∩ Cs) μ(B) > μ(Cs) μ(Cs) μ(Cs) - μ(Cs) μ(Cs) - μ(Cs) ( 1 δ \ sd - (s - 2b)d 1 > ν0 - n + n - sd > ν0 - n. Итак, мы доказали, что существуют такие s и Cs, с которыми для любого i выполнено - . μ({S + axi}∩Cs) > ν 1 μ(Cs) 0 n Суммируем полученные неравенства по i: n \ μ({S + axi}∩ Cs) > (ν0n - 1)μ(Cs). i=1 Стало быть, найдется такая точка x∗ ∈ Cs, что x∗ принадлежит по крайней мере [ν0n] множествам вида {S + axi}. Без ограничения общности можно считать, что найдется m, не меньшее [ν0n], для которого имеет место x∗ ∈ {S + axi} при всех i = 1, 2,..., m. Или, что то же самое, x∗ - axi ∈ S при i = 1, 2,..., m. Но по условию индуцированный подграф G× на вершинах x1, x2,..., xm имеет хроматическое число χ(G×) > k. Рассмотрим изоморфный ему граф G∗ = (V ∗, E∗), где V ∗ = {x∗ - axi : i = 1, 2,..., m}, E∗ = {(x∗ - axi1 , x∗ - axi2 ): (xi1 , xi2 ) ∈ E}. Поскольку его хроматическое число также больше k, то найдется множество Sj и точки x∗ - axi1 , x∗ - axi2 ∈ Sj, соединенные ребром. Но тогда на множестве Sj реализуется расстояние a. Теорема доказана. 4. ДОКАЗАТЕЛЬСТВА ВЕРОЯТНОСТНЫХ РЕЗУЛЬТАТОВ 1. Доказательство теоремы 5. Доказательство. Нам понадобится теорема, доказанная в [11] в несколько более общей формулировке. Теорема 9. Пусть p = c ,c < 1. Тогда с вероятностью, стремящейся к единице, все компоn ненты случайного графа в G(n, p) суть деревья или одноцикловые графы. Осталось заметить, что любое дерево или одноцикловый граф очевидным образом реализуются на плоскости как графы расстояний, и тем самым завершить доказательство теоремы. О БОЛЬШИХ ПОДГРАФАХ ГРАФА РАССТОЯНИЙ, ИМЕЮЩИХ МАЛЕНЬКОЕ ХРОМАТИЧЕСКОЕ ЧИСЛО 69 2. Доказательство теоремы 6. Доказательство. В теореме 4 утверждается, что в любом графе расстояний G = (V, E) на плоскости найдется большой индуцированный подграф с хроматическим числом, не превосходящим четырех. Иными словами, в таком графе всегда есть четверка непересекающихся независимых множеств вершин большой суммарной мощности. В связи с этим рассмотрим случайную величину Zs = Zs(G), равную количеству упорядоченных четверок непересекающихся независимых множеств вершин суммарной мощности s в графе G: Zs(G)= |{(V1, V2, V3, V4): Vi ⊂ V, Vi ∩ Vj = ∅, ∀ i, ∀x, y ∈ Vi, (x, y) ∈/ E, |V1 LJ ... LJ V4| = s}|. Мы доказали, что для любого плоского графа расстояний Z4k (G) > 0, где k = [νn] - 1, ν = 0, 2293 .... Стало быть, если Z4k (G)= 0, то G не реализуется на плоскости как граф расстояний. Это означает, что если мы покажем, что при p = c , где c > t = 14, 797 ... и n → ∞, выполнено n 0 MZ4k → 0, то мы докажем теорему. Нетрудно видеть, что MZ4k = \ Ck1 Ck2 Ck3 Ck4 4 ki C2 (1 - p)i=1 . n k1+...+k4=4k n-k1 n-(k1+k2) n-(k1+k2+k3) В силу выпуклости биномиального коэффициента 4 \ C2 2 i=1 ki 4Ck. Очевидно также, что максимальное значение величины Ck1 k2 k3 k4 n Cn-k1 Cn-(k1+k2)Cn-(k1+k2+k3) достигается тогда и только тогда, когда максимален полиномиальный коэффициент (4k)! P (k1, k2, k3, k4)= k !k !k !k ! , т. е. при k1 = k2 = k3 = k4 = k. Отсюда MZ4k n3Ck Ck Ck 1 2 3 4 2 Ck (1 - p)4Ck = n n-k n-2k n-3k 2 2 2k2-2k ( n )n (1 - c )(2n ν -2nν) = n3 n! 1 - c = Q (n) e n = f (n), (k!)4(n - 4k)! n 1 ( nν )4nν ( n-4nν )n-4nν e e где Q1(n) - функция, растущая не быстрее некоторого полинома. Далее, очевидно, e-2cnν2 f (n)= Q2(n) ν4nν (1 - 4ν)n-4nν = Q2(n)e -n(4ν ln ν+(1-4ν) ln(1-4ν)+2cν2), где Q2(n) - тоже функция, имеющая полиномиальный порядок роста. Для того, чтобы последнее выражение стремилось к нулю, достаточно, чтобы - - ⇔ 4ν ln ν + (1 4ν) ln(1 4ν)+ 2cν2 > 0 c > 4ν ln ν + (1 - 4ν) ln(1 - 4ν) . -2ν2 Подставляя значение ν, убеждаемся, что при c > t0 это условие выполнено. Теорема доказана. 5. ОБОБЩЕНИЯ ВЕРОЯТНОСТНЫХ РЕЗУЛЬТАТОВ В этом разделе мы сначала поговорим про обобщения полученных нами вероятностных результатов на случай d 3. Затем мы отдельно рассмотрим случай d = 1. 70 А. А. КОКОТКИН, А. М. РАЙГОРОДСКИЙ 1. Пороговые вероятности для реализации графом расстояний в размерностях d 3. Положим p∗ ( d 1 d(n)= sup p ∈ [0, 1] : Pn(G реализуется в R как граф расстояний) > . 2 2 В частности, p∗(n)= p∗(n). Сразу ясно, что для любого d 3 выполнен аналог теоремы 5, откуда ∗ pd(n) 0 ∗ 1 - ε со сколь угодно малым положительным ε и n n (ε). n Для получения верхних оценок величины pd(n) нам понадобятся обобщения теоремы 4. Как мы помним, доказательство теоремы 4 основано на результате Крофта и теореме 8. Понятно, что и сейчас мы сможем использовать последнюю теорему; нам лишь нужны аналоги результата Крофта в размерностях d 3. Этианалогинедавно былиполучены в работе [2]. А именно, пусть m1(Rd) - это супремум верхних плотностей таких измеримых множеств S ⊂ Rd, что в S не реализуется расстояние 1. В этих терминах конструкция Крофта дает неравенство m1(R2) 0.2293 .... Подобные неравенства установлены в статье [2] для d ∈ {3,..., 8}: m1(R3) 0.09877, m1(R4) 0.04413, m1(R5) 0.01833, m1(R6) 0.00806, m1(R7) 0.00352, m1(R8) 0.00165. Напомним, что в конце пункта 3.2 мы использовали 4 конгруэнтных копии множества Крофта. На самом деле конструкции из работы [2] устроены совершенно аналогично: они тоже имеют решетчатую природу, и для каждого d в Rd умещаются 2d их конгруэнтных копий. В итоге обобщением теоремы 4 служит следующий результат. Теорема 10. Положим ν3 = 0.09877, ν4 = 0.04413, ν5 = 0.01833, ν6 = 0.00806, ν7 = 0.00352, ν8 = 0.00165. Тогда для любого d ∈ {3,..., 8} в любом n-вершинном графе расстояний G = (V, E) в Rd найдется такой индуцированный подграф G× = (V ×, E×), что |V ×| 12dνdnl и χ(G×) 2d. Дальнейшая технология полностью совпадает с той, что была разработана в пункте 4.2 для доказательства теоремы 6. Теперь для данного d нужно брать k = [νdn] - 1 и добиваться того, чтобы величина MZ2dk стремилась к нулю (или хотя бы была меньше 1/2 при больших n). Пусть p = c . Тогда выкладки из пункта 4.2 преобразуются к виду n - n! MZ2dk Q1(n)(k!)2d (n 2dk)! c 2d-1k2-2d-1k - 1 = n = Q2(n)e-n(2 νd ln νd+(1-2 νd) ln(1-2 νd)+2 cνd ). d d d d-1 2 В итоге нам нужно Теорема 11. Положим - - 2dνd ln νd + (1 2dνd) ln (1 2dνd) c > . d -2d-1ν2 c3 = 55.272 ..., c4 = 164.528 ..., c5 = 504.285 ..., c6 = 1365.170 ..., c7 = 3624.758 ..., c8 = 8675.785 ... c Тогда при каждом d и p = n, где c > cd, выполнено Pn(G реализуется в Rd как граф расстояний) → 0, n → ∞. О БОЛЬШИХ ПОДГРАФАХ ГРАФА РАССТОЯНИЙ, ИМЕЮЩИХ МАЛЕНЬКОЕ ХРОМАТИЧЕСКОЕ ЧИСЛО 71 Иными словами, 1 - ε d n p∗(n) cd + ε. n Из выкладок, приведенных в статье [2], а также из неравенства, определяющего величины cd через величины νd, следует, что cd растет как экспонента. В этой связи интересно установить более сильные нижние оценки пороговой вероятности, нежели не зависящая от d нынешняя оценка 1 - ε ∗ pd n . 2. Пороговые вероятности для реализации графом расстояний в размерности d = 1. 1 d Здесь мы изучим величину p∗(n). Любопытно, что ее поведение будет разительно отличаться от поведения всех остальных величин p∗(n). А именно, зависимость от n будет другой. Теорема 12. Для любого ε > 0 существует такое n0, что при всех n n0 выполнено √3 3 - ε 1(n) √3 12 + ε . n4/3 p∗ n4/3 Доказательство. Начнем с доказательства нижней оценки. Пусть p = c n4/3 , где c < √3 3. Хорошо известно, что при любом p = o ( 1 \ n случайный граф с асимптотической вероятностью 1 не содержит циклов, т. е. является лесом. Значит, и при нашем p случайный граф - «почти наверняка» лес. Допустим, мы доказали, что к тому же степень каждой вершины случайного графа не превосходит двойки с вероятностью, которая при больших n строго больше половины. Тогда нужная оценка получена: лес, у которого каждая вершина имеет степень 0, 1 или 2, - это линейный лес, т. е. граф, компоненты которого суть простые цепи или изолированные вершины; ясно, что такой граф реализуется как граф расстояний на прямой. Итак, пусть Y3 - случайная величина, равная количеству вершин случайного графа, имеющих степень не ниже тройки. В силу классического неравенства Маркова нам достаточно убедиться в том, что MY < 1 + o(1). В самом деле, 3 2 n-1 n-1 MY3 = n \ Ci pi(1 - p)n-1-i = i=3 ( \ 2 = n 1 - (1 - p)n-1 - (n - 1)p(1 - p)n-2 - (n - 1)(n - 2) p2(1 - p)n-3 = \ ( p = n 1 - ( 1 - (n - 1)p + (n - 1)(n - 2) 2 2 - (n - 1)(n - 2)(n - 3) p3 6 + O (n4p4) - -(n - 1)p ( 1 - (n - 2)p + p (n - 2)(n - 3) 2 2 - (n - 2)(n - 3)(n - 4) p3 6 + O (n4p 4)\ - \\ p (n - 1)(n - 2) - 2 2 ( 1 - (n - 3)p + p (n - 3)(n - 4) 2 2 - (n - 3)(n - 4)(n - 5) p3 6 + O (n4p4) = = n(n - 1)(n - 2)(n - 3) 6 p3 + O (n5p4) = n4p3 6 + o(1) = n4c3 6n4 + o(1) < 1 + o(1). 2 Нижняя оценка доказана. Для доказательства верхней оценки применим неравенство Чебышёва: DY3 3 Pn(Y3 = 0)= Pn(Y3 0) = Pn(-Y3 0) = Pn(MY3 - Y3 MY3) (MY )2 . Допустим, мы показали, что DY3 (MY3)2 1 < + o(1). Тогда с вероятностью, большей половины при 2 больших n, в случайном графе есть вершины степени 3 или выше. Но графы с такими вершинами нельзя реализовать на прямой. 72 А. А. КОКОТКИН, А. М. РАЙГОРОДСКИЙ Итак, мы уже знаем, что при p = c n4/3 выполнено MY3 n4p3 = 6 + o(1). В книге [11] на с. 69 (лемма 3.10) приведено неравенство n-2 DY3 MY3 + n2p(1 - p) (C2 p2(1 - p)n-4)2 . Заметим, что n-2 0 < n2p(1 - p) (C2 p2(1 - p)n-4)2 < n2p ( n2 \2 p2 2 n6p5 = 4 = o(1). Значит, c учетом условия c > √3 12 имеем 2 - DY3 (MY3)2 n-2 MY3 + n2p(1 - p) (C2 (MY3)2 p2(1 p)n-4) = Теорема доказана. = MY3 + o(1) = (MY3)2 6 n4p3 + o(1) = 6 + o(1) < c3 1 + o(1). 2 Теорема 12 допускает уточнение. А именно, можно показать, что √3 6 ln2 - ε 1(n) √3 6 ln2 + ε . n4/3 p∗ n4/3 Иными словами, в одномерном случае мы знаем точное значение пороговой вероятности. Этот факт является прямым следствием теоремы 3.5 из книги [11]. В нашем случае теорема 3.5 утверждает, ∼ что при p x вероятность того, что максимальная степень вершины случайного графа не больn4/3 ше двух, асимптотически равна e-x3/6. В частности, если x = √3 6 ln 2, то последняя величина - это 1/2. Дальнейшие рассуждения совпадают с рассуждениями из доказательства теоремы 12. Стоит отметить, что, когда мы говорим о реализации графа G дистанционным графом H, мы не просто требуем наличия гомоморфизма из G в H, мы хотим, чтобы в образе не было совпадающих вершин. Для случаев d 2 это замечание не является принципиальным. Однако для текущего случая это имеет значение. Если бы мы разрешили совпадающие вершины, то реализация графа на прямой была бы просто равносильна двудольности, и тогда пороговая вероятность снова имела бы порядок 1 .