close

Вход

Забыли?

вход по аккаунту

?

Ослабленный закон «Нуля или единицы» для случайных дистанционных графов.

код для вставкиСкачать
Вестник РУДН
Серия Математика. Информатика. Физика.
№ 2 (1). 2010. С. 11–25
УДК 519.175.4
Ослабленный закон «нуля или единицы» для
случайных дистанционных графов
М. Е. Жуковский
Кафедра теории вероятностей
Московский государственный университет им. М.В. Ломоносова
Ленинские горы, д.1, корп. А, ГСП-1, Москва, Россия 119991
В этой работе изучается ослабленный -закон нуля или единицы. Для случайных дистанционных графов получены результаты, схожие с утверждениями, касающимися закона нуля или единицы для случайных графов.
Ключевые слова: закон нуля или единицы, дистанционные графы, игра Эренфойхта.
1.
Введение и история задачи
В работе речь пойдёт об одной известной задаче, которая лежит на стыке теории случайных графов, логики и комбинаторной геометрии. Прежде всего введём
основные объекты.
1.1.
Формулы первого порядка и игра Эренфойхта
Пусть  — конечное множество. Функция  :  × ×. . .× → {0, 1} от  аргументов называется предикатом, величина  — арность предиката . Сигнатура
 — это конечное множество предикатных символов 1 , . . . ,  , каждый с фиксированной арностью  (см. [1]). Конечная -структура  = (  , 1 , . . . ,  ,


1 , . . . ,  ) состоит из:
– конечного пространства   ;
– предикатов  арности  над   ;

– элементов 
 множества  .
Формулы первого порядка над сигнатурой  строятся индуктивно с помощью
– символов из ;
– символа отношения =;
– логических связок ¬, ⇒, ⇔, ∨, ∧;
– переменных , , 1 . . .;
– кванторов ∀, ∃.
Опишем построение формул подробнее (см. [2]). Для начала заметим, что свободной называется переменная, от которой может зависеть истинность формулы.
В противном случае переменная называется связанной. Кроме того, введём понятие атома. Это объект, который либо имеет вид  (1 , . . . ,  ), либо имеет вид
 = , где , , 1 , . . . ,  — переменные. Атом является формулой. Пусть  —

некоторая -структура. Рассмотрим произвольный набор элементов 
1 , . . . ,  .

Если  (
1 , . . . ,  ) = 1, то будем говорить, что формула  (1 , . . . ,  ) истин
на на структуре  на наборе (
1 , . . . ,  ). В противном случае будем говорить,
что формула ложна. Формула  =  истинна только на наборах, состоящих из
двух одинаковых элементов структуры, т.е. на наборах ( ,  ). Каждая из переменных , , 1 , . . . ,  является свободной. Пусть , 1 , 2 — формулы, , 1 , 2
и , 1 , 2 — соответствующие множества свободных и связанных переменных, переменная  принадлежит . Пусть также 1 ∩ 2 = ∅, 2 ∩ 1 = ∅. Конструкции
¬, 1 ∨ 2 , 1 ∧ 2 , 1 ⇒ 2 , 1 ⇔ 2 , ∀ , ∃  являются формулами. При
Статья поступила в редакцию 26 сентября 2009 г.
Работа выполнена при финансовой поддержке гранта РФФИ N 09-01-00294.
12
Жуковский М. Е.
этом  ∖ {} — множество свободных переменных формул ∀ , ∃ , а  ∪ {}
— множество связанных. Так же, как и в случае атома, формула является истинной на некотором наборе элементов, если предикат, выражаемый этой формулой,
принимает значение 1 на этом наборе. Замкнутыми называются формулы, не содержащие свободных переменных. Замкнутая формула либо всегда истинна на
структуре , либо всегда ложна.
Если замкнутая формула  первого порядка истинна на структуре , то будем говорить, что структура  удовлетворяет этой формуле, и писать  .
Формула  определяет класс  конечных -структур, если  ∈  тогда и только
тогда, когда  . В этом случае будем также говорить, что на сигнатуре  задано свойство  первого порядка, которое определяет класс , и что это свойство
определено формулой .
Две формулы  и ′ называются эквивалентными, если для любой -структуры  выполнено   ⇔  ′ .
Говорят, что формула находится в предварённой нормальной форме, если все
кванторы у неё вынесены налево. Известно, что всякая формула эквивалентна
некоторой формуле в предварённой нормальной форме.
Пусть на сигнатуре  задана некоторая структура . Пусть, кроме того,
 ⊆   . Тогда индуцированной подструктурой  ↓  будем называть -структуру, состоящую из множества  , элементов этого множества и предикатов ↓ ,
определённых на  ×  × . . . ×  , если выполнено
)︁
(︁

 

∀ ∀1 , . . . , 
1 , . . . ,  ∈  ⇒ ↓ (
1 , . . . ,  ) =  (1 , . . . ,  ) .



ℬ
ℬ
ℬ
Две -структуры  = (  , 1 , . . . ,  , 
1 , . . . ,  ) и ℬ = ( , 1 , . . . ,  ,
∼
называются изоморфными (пишем  = ℬ), если выполнено условие
ℬ
ℬ
1 , . . . ,  )
∀ ∀1 , . . . , 
ℬ

ℬ ℬ
 (
1 , . . . ,  ) =  (1 , . . . ,  ).


Определим игру EHR(, ℬ, ) на двух -структурах  и ℬ с двумя игроками,
Новатором и Консерватором, и с фиксированным числом раундов . Она носит
название игры Эренфойхта (см. [2,3]). На -ом ходу (1 6  6 ) Новатор выбирает
ℬ
элемент в любой из структур (он выбирает либо 
 , либо ′ ). Затем Консерватор
выбирает элемент из другой оставшейся структуры. Если Новатор выбирает на ℬ
ом ходу, скажем, элемент 
 ,  =  ( < ), то Консерватор должен выбрать ′ .
/ {1 , . . . , −1 },
Если же на этом ходу Новатор выбирает, скажем, элемент 
 ,  ∈
ℬ
′
′
′
то и Консерватор должен выбрать такой элемент ′ , что  ∈
/ {1 , . . . , −1
}. Если
он не может этого сделать, то игру выигрывает Новатор. К концу игры выбраны
ℬ

ℬ
элементы 
1 , . . . ,  структуры , а также элементы 1′ , . . . , ′ структуры ℬ.
Некоторые из этих элементов могут совпадать. Выберем из них только различные:

ℬ
ℬ

ℎ1 , . . . , ℎ ; ℎ′ , . . . , ℎ′ ,  6 . Консерватор побеждает тогда и только тогда, когда
1

ℬ
 ∼
ℬ
 ↓ {
ℎ1 , . . . , ℎ } = ℬ ↓ {ℎ′1 , . . . , ℎ′ }.

В 1960 году А. Эренфойхт (см. [3]) сформулировал и доказал следующую
теорему.
Теорема 1. Пусть  — класс структур над некоторой сигнатурой , определяемый замкнутой формулой  первого порядка. Существует такое , что если  ∈  и ℬ ∈
/ , то у Новатора есть выигрышная стратегия в игре EHR(, ℬ, ).
Ослабленный закон «нуля или единицы» для случайных дистанционных . . .
1.2.
13
Случайные графы и законы «нуля или единицы»
Пусть  является натуральным числом, 0 6  6 1. Рассмотрим множество
Ω = { = (, )} всех неориентированных графов без петель и кратных рёбер с множеством вершин  = {1, . . . ,  }. Назовём случайным графом вероятностное пространство (, ) = (Ω , ℱ , , ), где ℱ = 2Ω , , () =
2
|| (1 − ) −|| . Иными словами, любые две различные вершины графа в пространстве (, ) соединены ребром с вероятностью  независимо от любых двух
других (см. [4]). В дальнейшем мы будем рассматривать модели, в которых вероятность  зависит от количества вершин  , причём нас будет интересовать
асимптотическое поведение вероятностей свойств случайных графов при  → ∞.
Свойства графов первого порядка (классы  ⊆ Ω ) определяются формулами
первого порядка, которые строятся описанным выше способом с помощью:
– символов отношения ∼, =;
– логических связок ¬, ⇒, ⇔, ∨, ∧;
– переменных , , 1 . . .;
– кванторов ∀, ∃.
Рассматриваются, опять же, только замкнутые формулы. Символ отношения ∼ арности 2 выражает свойство двух вершин быть связанными ребром. Будем говорить о событии «граф  обладает свойством », понимая под этим
элемент ℱ , являющийся множеством всех графов из Ω , которые обладают
свойством . Будем обозначать это событие  . Также в дальнейшем, если
lim , ( ) = 1, то будем говорить, что случайный граф почти наверное
 →∞
обладает свойством .
Случайный граф подчиняется закону «нуля или единицы»(см. [5–8]), если для
любого свойства  первого порядка выполняется одно из двух условий
1) lim →∞ , ( ) = 0,
2) lim →∞ , ( ) = 1.
В 1969 году Ю.В. Глебский, Д.И. Коган, М.И. Легонький и В.А. Таланов (см.
[6]) получили следующий закон «нуля или единицы», который в 1976 году был
независимо доказан Р. Фагиным (см. [7]).
Теорема 2. Пусть функция  = ( ) такова, что   → ∞ при  → ∞ и
(1−)  → ∞ при  → ∞ для любого  > 0, тогда случайный граф подчиняется
закону «нуля или единицы».
Также в статье [8] С. Шелла и Дж. Спенсера описан результат, в котором
расширен класс функций, подчиняющихся закону «нуля или единицы».
Теорема 3. Пусть ( ) =  − , где  — иррациональное, 0 <  < 1, тогда
случайный граф подчиняется закону «нуля или единицы».
В следующем разделе сформулируем ещё одну задачу подобного типа, которая
мотивирована классическими вопросами комбинаторной геометрии (см. [9, 10]) и
которой будем заниматься в дальнейшем.
2.
2.1.
Постановка новой задачи
Формулы с одним квантором и новая игра
Пусть определена некоторая сигнатура  = (1 , . . . ,  ). Рассмотрим формулы над сигнатурой , построенные обычным способом с помощью:
– символов из ;
– символа отношения =;
– логических связок ¬, ⇒, ⇔, ∨, ∧;
– переменных , , 1 . . .;
– квантора (либо ∀, либо ∃).
14
Жуковский М. Е.
Таким образом, в записи формулы участвует только один квантор (хотя встречаться один и тот же квантор может сколько угодно раз). Примером такой формулы может послужить ∀ ∀ ((1 (, ) ∧ 2 (, )) ⇒ 1 (, )) . Пусть 1 — подобная формула. Пусть  1 — множество свободных переменных этой формулы,
 1 — множество связанных переменных. Пусть также | 1 | = 1 , | 1 | =  1 .
Пусть  и ℬ — две -структуры. Определим ослабленную игру Эренфойхта
EHR1 (, ℬ, ) с двумя игроками, Новатором и Консерватором, и фиксированным
числом раундов . Она будет отличаться от игры EHR(, ℬ, ) только тем, что
Новатор не имеет права в каждом раунде выбирать структуру, из которой затем
он будет выбирать элемент. Он волен выбирать структуру, из которой впоследствии будет выбирать (произвольные) элементы, только в первом раунде. Во всех
последующих раундах он обязан выбирать элемент только из выбранной в первом
раунде структуры.
2.2.
Дистанционные графы и ослабленный закон «нуля
или единицы»
Если при определении случайного графа считать, что разные пары вершин
соединены независимо друг от друга с различными вероятностями, т.е. ребро
{ ,  }, 1 6 ,  6 , проведено с вероятностью  ∈ [0, 1], то будем обозначать
такое вероятностное пространство (,  ). Одним из важнейших примеров этого случайного графа является случайный граф ( , ), где  = ( , ℰ ) —
неориентированный граф на  вершинах без петель и кратных рёбер, а именно,
( , ) = (,  ), коль скоро
{︂
, { ,  } ∈ ℰ ;
 =
0, { ,  } ∈
/ ℰ .
Иными словами, ( , ) — это вероятностное пространство
( , ) = (Ω , ℱ ,  ,  ) ,
где
0
0
0
0
0
⊆ ℰ },
=  , ℰ
) : 
, ℰ
= (
Ω = {
ℱ = 2Ω ,
0
0
0
 , (
) = |ℰ | (1 − )|ℰ |−|ℰ | .
/2
dist
dist
Пусть  ∈ N,  = 4. Положим  =  . Рассмотрим граф dist
 = ( ,  ),
dist
dist
в{︀ котором  = {x = (1 , . . . , }︀ ) :  ∈ {0, 1}, 1 + . . . +  = /2},  =
{x, y} ∈ dist × dist : ⟨x, y⟩ =  , где ⟨x, y⟩ — евклидово скалярное произведение векторов x и y. Заметим, что |dist | =  . Рассматриваемые графы называются дистанционными, поскольку их ребра отвечают тем парам их вершин,
которые отстоят друг от друга на некоторое наперёд заданное расстояние в R .
Рассмотрение такого рода графов мотивировано классической задачей комбинаторной геометрии о хроматическом числе пространства (см. [9, 10]).
В настоящей работе будем рассматривать случайные дистанционные графы
(dist
 , ). В дальнейшем покажем, что аналог теоремы 2 для него не выполнен. Однако получены и положительные результаты. Для их формулировки нам
потребуется определение ослабленного закона «нуля или единицы».
Скажем, что случайный граф (dist
 , ) подчиняется ослабленному закону
«нуля или единицы», если для любого свойства 1 , определённого замкнутой
формулой 1 с одним квантором, выполняется одно из двух условий
1) lim dist
( 1 ) = 0,
 ,
 →∞
2) lim dist
( 1 ) = 1.
 ,
 →∞
Ослабленный закон «нуля или единицы» для случайных дистанционных . . .
15
Вообще, пусть { } ∈N — последовательность неориентированных графов без
петель и кратных рёбер, | ( )| =  . Будем говорить, что последовательность
случайных графов {( , ( ))} ∈N подчиняется ослабленному закону «нуля
или единицы», если для любого свойства 1 , определённого замкнутой формулой 1 с одним квантором, выполняется одно из двух условий
1) lim  ,  ( 1 ) = 0,
 →∞
2) lim  ,  ( 1 ) = 1.
 →∞
3.
Формулировки результатов
Прежде всего приведём аналог теоремы 1.
Теорема 4. Пусть  — класс структур над некоторой сигнатурой , определяемый замкнутой формулой 1 из пункта 2.1. Существует такое , что если  ∈  и ℬ ∈
/ , то у Новатора есть выигрышная стратегия в игре EHR1 (, ℬ, ).
Теперь дадим формулировку теоремы, аналогичной теореме 2.
Теорема 5. Пусть функция  = ( ) такова, что   → ∞ при  → ∞ и
(1 − )  → ∞ при  → ∞ для любого  > 0, тогда для случайных дистанционных графов (dist
 , ) выполняется ослабленный закон «нуля или единицы».
Сформулируем, наконец, результат, позволяющий отойти от условия замкнутости формулы, с которой мы работаем.
Теорема 6. Пусть функция  = ( ) такова, что   → ∞ при  → ∞ и
(1 − )  → ∞ при  → ∞ для любого  > 0. Пусть 1 — некоторая незамкнутая формула из пункта
2.1, ]︂определяющая свойство 1 . Тогда либо почти навер[︂
ное существует
1
1
1
 2 + +4
2(1 + 1 )
1
индуцированных подграфов графа (dist
 , ) на 
вершинах, которые (вершины) можно занумеровать так, что если подставить
их вместо свободных переменных в формулу 1 , то полученные замкнутые фор̃︀ 1 , для которых будет выполнено
мулы 
̃︀1 будут выражать свойства графов 
]︂
[︂
̃︀ 1 ) = 1, либо почти наверное существует
( 
lim dist
 ,
 →∞
1
1
1
 2 + +4
2(1 + 1 )
ин-
дуцированных подграфов на 1 вершинах, которые (вершины) можно занумеровать так, что если подставить их вместо свободных переменных в формулу 1 ,
̃︀ 1 ,
то полученные замкнутые формулы 
̃︀1 будут выражать свойства графов 
̃︀ 1 ) = 0.
для которых будет выполнено lim dist ,  ( 
 →∞

Наиболее значимым в теореме является тот факт, что упомянутые в ней индуцированные подграфы не просто существуют, но что количество их стремится
к бесконечности с ростом  .
В следующем разделе покажем, почему пришлось ослабить классические законы «нуля или единицы». В разделе 5 приведём доказательства теорем 4–6.
4.
Опровержение закона «нуля или единицы»
для дистанционных графов
Рассмотрим случайный граф (dist
 , ). Докажем, что для него не выполнен
закон «нуля или единицы» ни при каком  = ( ) с условием   → ∞ при
любом положительном , т.е. не выполнена теорема 2. Пусть dist
1 — граф на 1
16
Жуковский М. Е.
 /2
вершинах, 1 = 11 , 1 = 41 и 1 — нечётное число. Пусть также количество
2 /2
вершин графа dist
2 равно 2 , 2 = 2 , 2 = 42 и 2 — чётное число.
Рассмотрим три вершины графа dist
1 :
x1 = (1, . . . , 1,
x2 = (1, . . . , 1,
x3 = (1, . . . , 1,
⏟ ⏞
1
1, . . . , 1,
0, . . . , 0,
0, . . . , 0,
⏟ ⏞
1
0, . . . , 0,
1, . . . , 1,
0, . . . , 0,
⏟ ⏞
1
0, . . . , 0),
0, . . . , 0),
1, . . . , 1).
⏟ ⏞
1
Предположим, что найдётся вершина x4 , соединённая ребром с каждой из
x1 , x2 , x3 . Тогда она должна иметь 1 единиц как среди первых 21 координат,
так и среди оставшихся. Предположим, что она имеет  единиц среди первых 1
координат. В силу того, что она соединена с x2 и x3 , она должна иметь 1 − 
единиц как среди координат с номерами 21 + 1, . . . , 31 , так и среди координат с
номерами 31 + 1, . . . , 41 . Следовательно, 1 = 2(1 − ). Но число 1 — нечётное.
Получили противоречие. Таким образом, не найдётся вершины, соединённой с
каждой из x1 , x2 , x3 .
Пусть теперь x1 , x2 , x3 — три произвольные вершины графа dist
2 . Перенумеруем их координаты следующим образом:
x1 = (1, . . . , 1,
x2 = (1, . . . , 1,
x3 = (1, . . . , 1,
⏟ ⏞
21
1, . . . , 1,
1, . . . , 1,
0, . . . , 0,
⏟ ⏞
22
1, . . . , 1,
0, . . . , 0,
1, . . . , 1,
⏟ ⏞
23
1, . . . , 1,
0, . . . , 0,
0, . . . , 0,
⏟ ⏞
24
0, . . . , 0,
1, . . . , 1,
1, . . . , 1,
⏟ ⏞
25
Здесь, разумеется, для вектора k2 = (21 , . . . , 28 )
⎛
1 1 1 0
⎜ 1 1 0 0
⎜
⎜ 1 0 1 0
⎜
⎜ 1 0 0 0
⎜
=⎜ 0 1 1 1
⎜
⎜ 0 1 0 1
⎜
⎜
⎝ 0 0 1 1
0 0 0 1
0, . . . , 0,
1, . . . , 1,
0, . . . , 0,
⏟ ⏞
26
0, . . . , 0,
0, . . . , 0,
1, . . . , 1,
⏟ ⏞
27
0, . . . , 0),
0, . . . , 0),
0, . . . , 0).
⏟ ⏞
28
и матрицы
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
выполнено k2  = (22 , 22 , 22 , 22 ).
Пусть 2 ≡  (mod 4), 1 6  6 8,  ∈ {0, . . . , 3}. Докажем, что найдутся такие
 ∈ Z+ , что  6  и выполняется равенство
2v = r,
(1)
где v = (1 , . . . , 8 ), r = (1 , . . . , 8 ). Заметим, что r = u, при этом u = (1 , . . . , 4 )
и  ≡ 0 (mod 4), 1 6  6 4.
Предположим, что число 21 + 22 — чётное, тогда, как не сложно заметить,
числа 23 +24 , 25 +26 , 27 +28 тоже чётные. В силу того, что число 21 +23 +25 +27 —
чётное, либо каждое из 21 , 23 , 25 , 27 нечётное, либо ровно два их них, либо все
чётные. Если некоторое 22+1 — чётное, то пусть 2+1 = 2+1 /2, 2+2 = 2+2 /2.
Если все нечётные, то пусть 1 = (1 − 1)/2, 2 = (2 + 1)/2, 3 = (3 + 1)/2,
4 = (4 − 1)/2, 5 = (5 − 1)/2, 6 = (6 + 1)/2, 7 = (7 + 1)/2, 8 = (8 − 1)/2.
Если, скажем, 21 , 23 — нечётные, а 25 и 27 — чётные, то пусть 1 = (1 − 1)/2,
Ослабленный закон «нуля или единицы» для случайных дистанционных . . .
17
2 = (2 +1)/2, 3 = (3 +1)/2, 4 = (4 −1)/2. При таких значениях  равенство (1)
будет выполняться.
Пусть теперь 21 +22 — нечётное. Тогда 23 +24 , 25 +26 , 27 +28 — тоже нечётные.
Опять же либо каждое из 21 , 23 , 25 , 27 нечётное, либо ровно два из них, либо все
чётные. Если все чётные, то определяем вектор v следующим образом:
v = (1 /2, (2 − 1)/2, 3 /2, (4 + 1)/2, 5 /2, (6 + 1)/2, 7 /2, (8 − 1)/2).
В случае, когда все нечётные,
v = ((1 − 1)/2, 2 /2, (3 + 1)/2, 4 /2, (5 + 1)/2, 6 /2, (7 − 1)/2, 8 /2).
Осталось рассмотреть три случая (остальные три им аналогичны):
1) 21 , 23 — нечётные, а 25 , 27 — чётные. Тогда
v = ((1 − 1)/2, 2 /2, (3 + 1)/2, 4 /2, 5 /2, (6 + 1)/2, 7 /2, (8 − 1)/2).
2) 21 , 25 — нечётные, а 23 , 27 — чётные. Тогда
v = ((1 − 1)/2, 2 /2, 3 /2, (4 + 1)/2, (5 + 1)/2, 6 /2, 7 /2, (8 − 1)/2).
3) 21 , 27 — нечётные, а 25 , 23 — чётные. Если 2 = 3 = 5 = 8 = 0, то 1 + 4 =
1 + 6 = 1 + 7 = 6 + 7 = 4, но такого быть не может. Если же 2 = 2, то
v = ((1 + 1)/2, (2 − 2)/2, 3 /2, (4 + 1)/2, 5 /2, (6 + 1)/2, (7 − 1)/2, 8 /2).
Аналогичный подбор осуществляем, если 3 = 2 и т.д.
Итак, всегда найдётся такой вектор v, для которого выполняется (1). Пока8
∑︀
 = 22
жем, что можно подобрать такие числа  ∈ Z+ , 1 6  6 8, что  6 2 ,
=1
и любая вершина, содержащая ровно 1 единиц среди первых 21 координат,. . . ,
ровно 8 единиц среди последних 28 координат, соединена ребром с каждой из
x1 , x2 , x3 . Для этого достаточно положить
 =
2 − 
+  , 1 6  6 8.
2
(2)
Оценим снизу количество вершин 3 , соединённых ребром с каждой из x1 , x2 , x3 .
8
∑︀
В силу того, что
2 = 2 , найдётся такое , что 2 > 2 /8. Заметим, что в си=1
лу (2) выполнено неравенство [(2 − 4)/2] <  6 [(2 + 4)/2]. Следовательно, при

[ /32]
достаточно больших  выполнено неравенство: 3 >  > 22/8 .
2
Рассмотрим замкнутую формулу первого порядка
 = ∀1 ∀2 ∀3 ∃4 ((1 ∼ 4 ) ∧ (2 ∼ 4 ) ∧ (3 ∼ 4 )),
которая выражает следующее свойство  графов: «для любых трёх вершин найдётся четвёртая, соединённая ребром с каждой из них». Случайные графы (dist
1 , )
с вероятностью 1 не обладают этим свойством. Случайный граф (dist
,
)
обла2
дает этим свойством с вероятностью dist
(
),
причём
,

2
(︀
)︀ [2 /32]
3
3 2 /8
1 − dist
(
)
6

1
−

.
,

2

2
18
Жуковский М. Е.
Применив формулу Стирлинга, получим
√︀
2 /8(2 /8)2 /8
[2 /32]
2 /8 ∼ √︀
.
2[2 /32](2 /8 − [2 /32])[2 /32][2 /32] (2 /8 − [2 /32])2 /8−[2 /32]
Следовательно, при достаточно больших 2 выполнены неравенства:
√︀
2 /8(2 /8)2 /8
[2 /32]
2 /8 > √︀
,
22 /16(32 /32)(2 /16)2 /32 (32 /32)32 /32
√︂
32
272 /32
[2 /32]
2 /8 >
· 3 /32 .
32 3 2
[ /32]
Положим  = (128/27)1/32 > 1. Тогда 22/8
при 2 → ∞. Далее,
[2 /32]
2 /8

(1−3 )
< (1−3 )(+1 (2 ))
2
> ( + 1 (2 ))2 , где 1 (2 ) → 0
(︀
)︀
6 exp −3 ( + 1 (2 ))2 = exp (−( + 2 (2 ))2 ) ,
где 2 (2 ) → 0 при 2 → ∞.
√︁
2 2
3
2
Так как 2 ∼ 2 · √
2 , то (2 ) = (8 + (1)) . Поэтому
3
= Θ((2 )3 ) = (8 + 3 (2 ))2 ,

2
где 3 (2 ) → 0 при 2 → ∞. В силу этого при достаточно больших 2 выполнено
неравенство
(︀
)︀ [2 /32]
(8 + 3 (2 ))2
3
1 − 3 2 /8 <

.
2
exp (( + 2 (2 ))2 )
Следовательно,
lim
→∞, 2|
dist
( ) = 1.
 ,
Таким образом, не существует предела у последовательности {dist
(  ,
)}∈N , т.е. теорема 2 для случайных дистанционных графов не выполнена.
5.
Доказательства теорем
Доказательство (теоремы 4). Сформулируем и докажем лемму, которая
понадобится нам для доказательства теоремы 4.
Пусть задана сигнатура  = (1 , . . . ,  ). Рассмотрим формулу 1 , множества
1
 ,  1 и числа 1 ,  1 , определённые в пункте 2.1. Пусть , ℬ — две -структуры.
Лемма 1. Если Консерватор побеждает в игре EHR1 (, ℬ, 1 +  1 ), то для

ℬ
ℬ
любых (не обязательно различных) элементов 
1 , . . . , 1 (элементов  ′ , . . . ,  ′ )
1
ℬ
найдутся такие элементы ℬ
 ′ , . . . ,  ′
1
1
1

1
(элементы 
1 , . . . , 1 ), что формула 

либо одновременно истинна на структуре  на наборе 
1 , . . . , 1 и на структуℬ
ℬ
ре ℬ на наборе  ′ , . . . ,  ′ , либо одновременно ложна на этих двух структурах
1
1
и наборах.
Доказательство. Предположим, что формула 1 содержит только кванторы ∃, т.е. имеет вид ∃1 +1 ∃1 +2 . . . ∃1 + 1 10 (1 , . . . , 1 , 1 +1 , . . . , 1 + 1 ),
где 10 — формула, не содержащая связанных переменных. Пусть 1 истинна на



структуре  на наборе 
1 , . . . , 1 . Тогда найдутся такие 1 +1 , . . . , 1 + 1 , что
Ослабленный закон «нуля или единицы» для случайных дистанционных . . .
19




формула 10 истинна на наборе 
 = 1 , . . . , 1 , 1 +1 , . . . , 1 + 1 . Пусть Но-
ватор в первом раунде выбирает структуру  и элемент 
1 , а в последующих
раундах выбирает все оставшиеся элементы набора 
 . Тогда Консерватор, в сиℬ
ℬ
, . . . , ℬ
лу условия леммы, сможет выбрать такие элементы ℬ
′
 ′ , . . . ,  ′ ,  ′
1
1
1 +1
1 + 1
1
ℬ
структуры ℬ, образующие набор ℬ
 ′ , что формула 0 истинна на наборе  ′ . Слеℬ
довательно, формула 1 истинна на структуре ℬ на наборе ℬ
 ′ , . . . ,  ′ . Если же
1
1

формула 1 ложна на структуре  на наборе 
1 , . . . , 1 , то в силу определения игры EHR1 (, ℬ, 1 +  1 ) и эквивалентных структур она будет ложна и на
ℬ
структуре ℬ на наборе ℬ
 ′ , . . . ,  ′ .
1
1
Если формула 1 имеет вид ∀1 +1 ∀1 +2 . . . ∀1 + 1 10 (1 , . . . , 1 , 1 +1 , . . . ,

1 + 1 ) и, скажем, истинна на структуре  на наборе 
1 , . . . , 1 , то можно
рассмотреть формулу ¬1 = ∃1 +1 ∃1 +2 . . . ∃1 + 1 ¬10 (1 , . . . , 1 , 1 +1 , . . . ,
1 + 1 ), и проделать те же самые рассуждения. Лемма доказана.
Завершим доказательство теоремы 4. Пусть 1 — замкнутая формула, а  —
класс структур, определяемый этой формулой. Будем считать, что выполнено равенство 1 = ∃1 ∃2 . . . ∃ 10 (1 , . . . ,  ), где все переменные формулы 10 являются свободными (в противном случае можно рассмотреть формулу ¬1 ). Пусть
, ℬ — две -структуры и, вопреки утверждению теоремы 4, Консерватор побеждает в игре EHR1 (, ℬ, ). Тогда для формулы 10 выполнено условие леммы 1 с
1 = ,  1 = 0, а следовательно, выполнено свойство (( ∈ ) ∧ (ℬ ∈ )) ∨ (( ∈
/
) ∧ (ℬ ∈
/ )). Имеем противоречие с условием теоремы 4, которая, тем самым,
доказана.
5.1.
Доказательство теоремы 5 и теоремы 6
5.1.1.
Вспомогательные леммы и конструкции
Пусть { }∈N — последовательность неориентированных графов без петель и
кратных рёбер, | ( )| = , при этом для любых различных ,  ∈ N выполнено
 ( ) ∩  ( ) = ∅. Пусть задана некоторая функция  : N → [0, 1]. Рассмотрим
вероятностное пространство
( , ( )) × ( , ( )) = (Ω × Ω , ℱ × ℱ ,  ,  ,  ) ,
0
0
0
0
0
0
где  ,  ,  ((
, 
)) =  , (
) ·  , (
) для любых графов 
и 
,
принадлежащих множествам Ω и Ω соответственно. Под  ×  понимается
декартово произведение множеств  и  . Под событием «Консерватор победит
в EHR(, , )» будем понимать подмножество в Ω × Ω всех пар графов, на
которых Консерватор в игре с  раундами побеждает.
Лемма 2. Если для любого натурального  выполнено
lim
,  →∞
 ,  ,  (Консерватор победит в EHR1 (, , )) = 1,
то для случайного графа ( , ) выполнен ослабленный закон «нуля или единицы».
Доказательство леммы 2 опирается на утверждение теоремы 4 и дословно
повторяет доказательство аналогичной леммы для не ослабленного закона «нуля
или единицы» (см. [5]).
Определим также свойство графов, которое понадобится для доказательства
теоремы 5 и теоремы 6. Граф  обладает свойством расширения полного уровня
, если для любых различных вершин u1 , . . . , u , v1 , . . . , v графа , где  +  6 ,
20
Жуковский М. Е.
найдётся вершина x такая, что {x, u } ∈ (), 1 6  6 , и {x, v } ∈
/ (), 1 6
 6  (см. [5]).
Утверждение 1. Если графы  и  обладают свойством расширения полного уровня  − 1, то Консерватор победит в EHR(, , ).
Доказательство. Консерватору надо придерживаться следующей простой
стратегии. На -ом раунде, если x1 , . . . , x−1 , y1 , . . . , y−1 уже выбраны, и Новатор выбирает x , Консерватор, в силу свойства расширения полного уровня  − 1,
сможет найти вершину y , смежную с теми же y ,  < , что и x — с x ,  < .
Сформулируем похожее утверждения для игры EHR1 (, , ).
Утверждение 2. Пусть в некоторых графах ,  мы можем выбрать со̃︀ ,
̃︀ для которых выполнено
ответственно такие индуцированные подграфы ,
свойство расширения полного уровня  − 1. Тогда Консерватор победит в игре
EHR1 (, , ).
Доказательство. Консерватор сможет на каждом шаге выбрать вершину
по алгоритму из утверждения 1, соединённую с нужными ему, выбирая её из
̃︀ (или  ()),
̃︀
множества  ()
т.е. победит.
Лемма 3. В графе dist
 найдётся полный индуцированный подграф на [log2 ]
вершинах.
Прежде чем перейти к доказательству, сделаем замечание.
Замечание 1. На самом деле, существует сколько угодно большое  , для
которого в графе dist
 найдётся полный индуцированный подграф на  вершинах
(см. [11]). Наша лемма не является следствием этого утверждения, потому что в
ней мы находим полный индуцированный подграф для каждого  .
Перейдём теперь к доказательству леммы.
Доказательство. Определим две вершины, соединённые друг с другом:
x1 = (1, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .., 1, 0, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .., 0),
⏟
⏞
⏟
⏞
2
2
x2 = (1, . . . . . . . . . . . . , 1, 0, . . . . . . . . . . . . , 0, 1, . . . . . . . . . . . . , 1, 0, . . . . . . . . . . . . , 0),
⏟
⏞
⏟
⏞
⏟
⏞
⏟
⏞




x3 = (1, . . . , 1, 0, . . . , 0, 1, . . . , 1, 0, . . . , 0, 1, . . . , 1, 0, . . . , 0, 1, . . . , 1, 0, . . . , 0).
⏟ ⏞
⏟ ⏞
⏟ ⏞
⏟ ⏞
⏟ ⏞
⏟ ⏞
⏟ ⏞
⏟ ⏞
[ 2 ]
[ +1
[ +1
[ 2 ]
[ +1
[ 2 ]
[ 2 ]
[ +1
2 ]
2 ]
2 ]
2 ]
У первой вершины набор координат разбивается на два блока — блок нулей и
блок единиц, у второй — на четыре. В дальнейшем мы определим ещё [log2 ] − 3
вершины, причём у -ой вершины набор координат будет разбит на 2 блоков.
Если занумеровать блоки в порядке их следования, то у  + 1-ой вершины суммарное количество координат, стоящих в 2 − 1-ом и в 2-ом блоке (для любого ),
будет равно количеству координат, стоящих в -ом блоке -ой вершины. Можно
сказать, что при построении следующей после -ой вершины каждый блок будет
разбиваться на два — блок нулей и блок единиц. Поэтому далее будем писать в
каждом блоке только количество единиц.
(︂[︂ ]︂ [︂
]︂ [︂
]︂ [︂
]︂ [︂
]︂ [︂
]︂ [︂
]︂ [︂ ]︂)︂

+1
+2
+3
+3
+2
+1

x4 =
|
|
|
|
|
|
|
4
4
4
4
4
4
4
4
........................................................................
(︂[︂
]︂ [︂
]︂
[︂
]︂ [︂
]︂
[︂
]︂ [︂
]︂)︂
+1
 + 2−2 − 1
 + 2−2 − 1
+1


x =
| −2 | . . . |
|
| . . . | −2 | −2
2−2
2
2−2
2−2
2
2
Ослабленный закон «нуля или единицы» для случайных дистанционных . . .
21
..............................................................................
Очевидно,[︀ что]︀ все такие вершины будут попарно соединены. Заметим, что

неравенство 2−2
> 0 выполнено тогда и только тогда, когда  > 2−2 , т.е.
 6 log2  + 2. Таким образом, лемма доказана.
 /2
Пусть 0 = 4 · 2+2 , 0 = 00 .
log2  (, ) =
[︁  ]︁
.
2+5
(3)
при  > 0 найдется
Лемма 4. Для любого натурального  в графе dist

такой индуцированный подграф  , , что для каждого индуцированного подграфа  в  , на  вершинах найдется индуцированный подграф  в  , на
 =  (, ) вершинах со свойством: любые две вершины x ∈  ( ) и y ∈  ()
соединены ребром в dist
 .
Доказательство. Пусть  — произвольное натуральное число.
1)  = 0 . Тогда в силу леммы 3 найдутся  + 2 вершины, образующие полный индуцированный подграф в dist
 . Функция  (, ) при  = 0 равна
 (0 , ) = 2[1/2] = 1. Но среди рассмотренных  + 2 вершин любая одна будет соединена рёбрами с любыми другими  вершинами. Таким образом, в
этом случае утверждение леммы доказано.
/2
2) Пусть теперь
> 0 . Определим натуральное число  из нера0 ,  =[︀ ]︀
[︀  ]︀ > +2

венства 2+1 < 2
6 2 . Разобьём у каждой вершины набор координат
[︀ +1 ]︀
[︀  ]︀
координат,
во
второй
—
4
координат, . . . , в
на группы: в первой
—
4

2
2
[︁
]︁
последней — 4
+2 −1
2
[︂
координат. Действительно,
]︂ [︂
]︂
[︂
]︂
+1
 + 2 − 1

+
+ . . . .. +
= .
2
2
2
 /2

Всего таких групп 2 . Рассмотрим дистанционный граф dist
 =  ,
 ,[︀ где 
[︀ +−1 ]︀
[︀ +−1
]︀]︀
 = 4 2
и его полный индуцированный подграф на log2
>
2

 + 2 вершинах. Пусть x0 — некоторая вершина этого подграфа. Из векто


ров x10 = (10,1 , . . . , 10,1 ), . . . , x20 = (20,1 , . . . , 20,2 ) составим вектор x0 =


(10,1 , . . . , 10,1 , . . . , 20,1 , . . . , 20,2 ). Таких векторов мы сможем составить не ме
нее, чем ( + 2)2 . Докажем, что построенный на выбранных вершинах индуцированный подграф  , и есть искомый. Если взять произвольные  вершин,
то в каждой группе останется по крайней мере по два набора, а следователь
но, мы сможем найти 22 вершин, соединённых с каждой из  выбранных. При
этом выполнены неравенства:



22 > 2 2+3 > 2[ 2+5 ] .
Лемма доказана.
Замечание 2. В дальнейшем нас будет интересовать лишь √︁
асимптотическое
2
поведение определённой в (3) величины. В силу того, что  = 2 √
(1 + ()),

где () → 0 при  → ∞, получим
log2  +log2
 (, ) > 2
√2
2+5
√

 1+()
(︃√︂
=  ()
)︃()
√
2

,
 1 + ()
22
Жуковский М. Е.
где () =
1
2+5 .
Следовательно,
 () = ( (, )).
(4)
Доказательство (теоремы 5). Пусть  — произвольное натуральное число. Рассмотрим случайный граф (dist
 , ). В силу утверждения 2, леммы 2 и
леммы 4 нужно доказать, что для любого натурального  для случайного графа
( , , ) = (Ω , , ℱ , ,  , ,  )
почти наверное выполняется свойство расширения полного уровня .
Мы знаем, что в графе  , для любых  вершин найдется  (( ), ) вершин,
соединённых с каждой из них. При этом  () = ( (, )), где () не зависит от
 и является положительной величиной. Далее поступаем так же, как и в случае
случайных графов (, ) (см. [5]).
Для любых различных u1 , . . . , u , v1 , . . . v , x ∈  ( , ), где  +  6 , определим событие u1 ,...,u ,v1 ,...,v , x , заключающееся в том, что вершины x и u соединены ребром, если 1 6  6 , а вершины x и v не соединены ребром, если
1 6  6 . Пусть также
 = min(, 1 − ),
⋀︁
u1 ,...,u ,v1 ,...,v =
u1 ,...,u ,v1 ,...,v , x ,
x̸=u1 ,..,u ,v1 ,...,v
=
⋁︁
u1 ,...,u ,v1 ,...,v ,
где дизъюнкция берётся по всем различным u1 , . . . , u , v1 , . . . v .
,
,
Наконец, пусть +
— индуцированный подграф графа  , , причём  (+
)=
{u1 , . . . , u , v1 , . . . v }. Мы знаем, что найдется  (, ) вершин, образующих ин,
дуцированный в  , подграф , такой, что +
и , образуют полный
двудольный подграф в  , . Отсюда имеем
∏︁
 6 (1 −  ) (,) ,
 , ,  (u1 ,...,u ,v1 ,...,v ) 6 (1 −  ) (,)
∈
где за  (︁
обозначено множество
)︁ индексов вершин, принадлежащих множеству
,
 ( , )∖  (, ) ∪  (+
) ,  =  , ,  (u1 ,...,u ,v1 ,...,v ,x ).
Тогда

  (,)

 , ,  () 6 2 |
6  2 
(1 −  ) (,) .
( , )| (1 −  )

В силу (4) и того, что 
=  (  ),

2


(1
  (,)
− )
(︂
=

exp (  (, ))
(︃
)︂
=

(︀
)︀
exp   ()
)︃
,
где   → ∞ при  → ∞ для любого  > 0, а следовательно,  , , () → 0.
Теорема доказана.
Доказательство (теоремы 6). Рассмотрим некоторую формулу 1 , определённую в пункте 2.1. Предположим, что она имеет вид
1 = ∃1 +1 ∃1 +2 . . . ∃1 + 1 10 (1 , . . . , 1 , 1 +1 , . . . , 1 + 1 ),
(5)
Ослабленный закон «нуля или единицы» для случайных дистанционных . . .
23
где 10 — формула, не содержащая связанных переменных. Если же формула 1 не
представляется в таком виде, то можно рассмотреть формулу ¬1 . Пусть формула 1 , представимая в виде (5), выражает некоторое свойство графов 1 , а не содержащая свободных переменных формула ∃1 . . . ∃1 ∃1 +1 ∃1 +2 . . . ∃1 + 1 10
— свойство 10 .
(︀
)︀
(︀
)︀
 10 = 0.
 10 = 1, либо lim dist
По теореме 5 либо lim dist
 ,
 ,
 →∞
 →∞
Предположим, что имеет (︀место первый
вариант. Пусть ℋ1 + 1 — некоторый граф
)︀
на 1 +  1 вершинах,  ℋ1 + 1 = {z1 , . . . , z1 + 1 }. Пусть также формула 10
истинна на наборе z = (z1 , . . . , z1 + 1 ), а следовательно, граф ℋ1 + 1 обладает
свойством 10 .
Всюду далее считаем, что  достаточно велико.
̃︀  :=  ,1 + 1 , определённого в лемПусть x1,1 — некоторая вершина графа 
1
̃︀  , ) ⊆
ме 4. С вероятностью 1 найдется такая вершина x1,2 случайного графа (
1
dist
( , ), что выполнено свойство x1,1 ∼ x1,2 ⇔ z1 ∼ z2 .
̃︀  , ), что
С вероятностью 2 найдется вершина x1,3 случайного графа (
1
выполнено свойство (x1,1 ∼ x1,3 ⇔ z1 ∼ z3 ) ∧ (x1,2 ∼ x1,3 ⇔ z2 ∼ z3 ).
Аналогично вводятся вероятности  , 3 6  6 1 +  1 − 1. Пусть, кроме того, с
̃︀  , ) найдется индуцированный подграф, изовероятностью  (x1,1 ) в графе (
1
морфный графу ℋ1 + 1 , причём вершине x1,1 при этом изоморфизме ставится в
соответствие вершина z1 . Пусть, как и раньше,  = min(, 1−). Тогда выполнены
неравенства
1 −  (x1,1 ) 6
1
1 +
∑︁−1
(1 −  ) 6
=1
1
1 +
∑︁−1
(1 −  ) (,) 6
=1
(︁
)︁ (,1 + 1 −1)
1
1
6 (1 +  1 − 1) 1 −  + −1
.
1
1
̃︀  графа  , + , опредеРассмотрим теперь индуцированный подграф 
2
1
̃︀  ) =  ( , + 1 )∖{x1,1 , x1,2 , . . . , x1,1 + 1 }.
лённый на множестве вершин  (
2
Введём для него аналогично вероятность  (x2,1 ), в результате чего придём к
неравенству
(︁
)︁ (,1 + 1 −1)−(1 + 1 )
1
1
1 −  (x2,1 ) 6 (1 +  1 − 1) 1 −  + −1
.
̃︀  , для которых выполнено равенство
Определим аналогичным образом графы 

1
1
̃︀  ) =  ( , + )∖{x1,1 , x1,2 , . . . , x1,1 + 1 , . . . , x−1,1 , x−1,2 , . . . , x−1,1 + 1 },
 (

[︁
]︁
[︁
]︁
и вероятности x,1 , где 3 6  6
нено неравенство
 (,1 + 1 −1)
2(1 + 1 )
. При 1 6  6
 (,1 + 1 −1)
2(1 + 1 )
(︁
)︁ (,1 + 1 −1)−(−1)(1 + 1 )
1 + 1 −1
1 −  (x,1 ) 6 ( +  − 1) 1 − 
.
1
1
выпол-
(6)
[︁
]︁
1
1
1
+ 1 −1)
Пусть   — вероятность того, что в графе ( , + , ) найдется  (,
1
1
2( + )
индуцированных подграфов, изоморфных графу ℋ1 + 1 . Тогда, очевидно, в силу
(6) и (4) выполнены неравенства
[︂
1 −  6
 (,1 + 1 −1)
2(1 + 1 )
∑︁
=1
]︂
(1 −  (x,1 )) 6
24
Жуковский М. Е.
(︁
1
6 (1 +  1 − 1) 1 − 
[︂
1
+ −1
)︁ (,1 + 1 −1)−
(︂[︂
]︂
 (,1 + 1 −1)
−1
1
1
2( + )
(︁
∑︁
×
1−
1 + 1 −1
 (,1 + 1 −1)
2(1 + 1 )
)︁(1 + 1 )
]︂
)︂
−1 (1 + 1 )
×
6
=0
)︁ (,1 + 1 −1)/2
(︁
1 + 1 −1
1
1
)︁
(︁
1
−
1
−


(,
+
−1)/2
1
1
·
6 (1 +  1 − 1) 1 −  + −1
.
(︀
)︀1 + 1
1 − 1 − 1 + 1 −1
Найдём lim
(︁
→∞
(︁
1
1 − 
+ 1 −1
)︁ (,1 + 1 −1)/2
. Имеем в силу (4)
)︃
1
1
− (, 1 +  1 − 1) + −1
1−
∼ exp
=
2
(︃
(︃
)︃)︃
(︃
(︃
)︃)︃
1
1
1
1
1
1
− ( + −1)  + −1
− ( + −1)/2
=  exp
=  exp
.
2
2
1 + 1 −1
(︃
)︁ (,1 + 1 −1)/2
Последнее равенство имеет место в силу того, что при любом  > 0 выполнено
lim   = ∞. Следовательно, искомый предел равен 0.
 →∞
Пусть
1 +  1 − 1
=
(︀
)︀1 + 1 ,
1 − 1 − 1 + 1 −1
(︁
= 1−
1 + 1 −1
)︁ (,1 + 1 −1)/2
.
Тогда
1 −   6 ( − 2 ).

Следовательно,
→ 1 при  → ∞. Тогда почти наверное существует
]︁ 
[︁
1
1
 (, + −1)
1
1
индуцированных подграфов графа (dist
 , ) на  +  верши2(1 + 1 )
нах, которые (подграфы) удовлетворяют свойству 10 . Пусть (, ) — такой
подграф. Пусть, кроме того,  = (, ℰ),  = {v1 , . . . , v1 + 1 }, причём эти вершины перечислены в том порядке, в котором они шли в ходе построения, описанного выше. Тогда индуцированный подграф (ℋ, ) графа (, ), где ℋ =
({v1 , . . . , v1 }, ℰ|{v1 ,...,v1 } ), удовлетворяет условию теоремы 6.
(︀
)︀
Если же lim dist
 10 = 0, то достаточно рассмотреть граф ℋ1 + 1 ,
 ,
 →∞
не удовлетворяющий свойству 10 , и провести аналогичные рассуждения.
Осталось заметить, что при достаточно больших  в силу (4) выполнено неравенство
]︃
1
]︂ [︃
[︂
 21 +1 +4
 (, 1 +  1 − 1)
>
.
2(1 +  1 )
2(1 +  1 )
Теорема доказана.
Литература
1. Shwentick T. On Winning Ehrenfeucht Games and Monadic NP // Ann. Pure
Appl. Logic. — 1996. — Vol. 79, No 1. — Pp. 61–92.
2. Верещагин Н. К., Шень А. Языки и исчисления. — М.: МЦНМО, 2000.
Ослабленный закон «нуля или единицы» для случайных дистанционных . . .
25
3. Ehrenfeucht A. An Application of Games to the Completness Problem for Formalized Theories // Fund. Math. — 1960. — Vol. 49. — Pp. 121–149.
4. Bollobás B. Random Graphs. — 2 edition. — Cambridge University Press, 2001.
5. Алон Н., Спенсер Дж. Вероятностный метод. — М.: БИНОМ. Лаборатория
знаний, 2007.
6. Range of Degree and Realizability of Formulas in the Restricted Predicate Calculus / Ю. В. Глебский, Д. И. Коган, М. И. Легонький, В. А. Таланов //
Cybernetics. — 1972. — Vol. 5. — Pp. 142–154.
7. Fagin R. Probabilities in Finite Models // J. Symbolic Logic. — 1976. — Vol. 41. —
Pp. 50–58.
8. Shelah S., Spencer J. H. Zero-One Laws for Sparse Random Graphs // J.Amer.
Math. Soc. — 1988. — Vol. 1. — Pp. 97–115.
9. Райгородский А. М. Проблема Борсука и хроматические числа метрических
пространств // Успехи Матем. Наук. — 2001. — Т. 56, № 1. — С. 107–146.
10. Райгородский А. М. Линейно-алгебраический метод в комбинаторике. — М.:
МЦНМО, 2007.
11. Холл М. Комбинаторика. — М.: Мир, 1970.
UDC 519.175.4
The Weak Zero-One Law for the Random Distance Graphs
M. E. Zhukovskii
Department of Probability Theory
Moscow State University
Leninskie Gory, 1A, Moscow, Russia 119991
In this paper, the weak zero-one -law is defined. The results for the random distance
graphs similar to the statements for the zero-one law and random graphs are obtained.
Key words and phrases: zero-one law, distance graphs, Ehrenfeucht game.
Документ
Категория
Без категории
Просмотров
4
Размер файла
701 Кб
Теги
единицы, закон, случайных, нуля, дистанционное, ослабленным, графов
1/--страниц
Пожаловаться на содержимое документа