График Rado - Rado graph

График Rado, пронумерованный Аккерманн (1937) и Rado (1964).

в математический поле теория графов, то График Rado, Граф Эрдеша – Реньи, или же случайный граф это счетно бесконечный граф, который можно построить (с вероятность один ) путем независимого случайного выбора для каждой пары его вершин, соединять ли вершины ребром. Имена этого графа честь Ричард Радо, Пол Эрдёш, и Альфред Реньи, математики, изучавшие его в начале 1960-х годов; он появляется еще раньше в творчестве Вильгельм Аккерманн (1937 ). Граф Радо также можно построить неслучайно, симметризуя отношение принадлежности наследственно конечные множества, применяя Предикат BIT к двоичные представления из натуральные числа, или как бесконечное Граф Пэли который имеет ребра, соединяющие пары простые числа конгруэнтно 1 модулю 4, которые квадратичные вычеты по модулю друг друга.

Каждый конечный или счетно бесконечный граф является индуцированный подграф графа Радо и может быть найден как индуцированный подграф с помощью жадный алгоритм который строит подграф по одной вершине за раз. Граф Rado однозначно определяется среди счетных графов свойство расширения что гарантирует правильность этого алгоритма: независимо от того, какие вершины уже были выбраны для формирования части индуцированного подграфа, и независимо от того, какой образец смежности необходим для расширения подграфа еще на одну вершину, всегда будет существовать другая вершина с этим образец смежности, который может выбрать жадный алгоритм.

Граф Радо очень симметричен: любой изоморфизм его индуцированных подграфов может быть расширен до симметрии всего графа. логика первого порядка предложения, которые верны для графа Rado, также верны для почти все случайные конечные графы, и предложения, ложные для графа Радо, также неверны для почти всех конечных графов. В теория моделей, график Rado представляет собой пример насыщенная модель из ω-категоричный и полная теория.

История

Граф Rado был впервые построен Аккерманн (1937) двумя способами, с вершинами либо наследственно конечные множества или натуральные числа. (Строго говоря, Аккерман описал ориентированный граф, а граф Радо - это соответствующий неориентированный граф, заданный забыванием направлений на ребрах.) Эрдеш и Реньи (1963) построил граф Rado как случайный граф по счетному числу точек. Они доказали, что у него бесконечно много автоморфизмов, и их аргумент также показывает, что он уникален, хотя они не упоминали об этом явно. Ричард Радо (1964 ) переоткрыл граф Радо как универсальный граф, и дал явную конструкцию с множеством вершин натуральными числами. Конструкция Rado по сути эквивалентна одной из конструкций Аккермана.

Конструкции

Двоичные числа

Аккерманн (1937) и Rado (1964) построил граф Rado, используя Предикат BIT следующее. Они отождествили вершины графа с натуральные числа 0, 1, 2, ... Ребро соединяет вершины Икс и y в графе (где Икс < y) всякий раз, когда Иксй бит двоичный представление y отличен от нуля. Так, например, соседи вершины 0 состоят из всех вершин с нечетными номерами, потому что числа, у которых 0-й бит ненулевой, в точности являются нечетными числами. Вершина 1 имеет одного меньшего соседа, вершину 0, поскольку 1 нечетная, а вершина 0 соединена со всеми нечетными вершинами. Более крупные соседи вершины 1 - это все вершины с номерами, сравнимыми с 2 или 3 по модулю 4, потому что это в точности числа с ненулевым битом в индексе 1.^[1]

Случайный график

Возникает график Rado почти наверняка в Модель Эрдеша – Реньи случайного графа на счетном числе вершин. В частности, можно сформировать бесконечный граф, независимо и с вероятностью 1/2 для каждой пары вершин, соединять ли две вершины ребром. С вероятностью 1 полученный граф изоморфен графу Радо. Эта конструкция также работает, если фиксированная вероятность п не равно 0 или 1 используется вместо 1/2.^[2]

Этот результат, показанный Пол Эрдёш и Альфред Реньи (1963 ), оправдывает определенный артикль в общем альтернативном имени "то случайный граф »для графа Радо. Неоднократное рисование конечного графа из модели Эрдеша – Реньи, как правило, приводит к различным графам; однако, когда применяется к счетно бесконечному графу, модель почти всегда дает тот же бесконечный граф.^[3]

Для любого графа, сгенерированного таким образом случайным образом, дополнительный граф может быть получен одновременно, поменяв местами все варианты: включая ребро, когда первый граф не включал такое же ребро, и наоборот. Это построение дополнительного графа является примером того же процесса случайного и независимого выбора, включать ли каждое ребро, поэтому оно также (с вероятностью 1) генерирует граф Радо. Следовательно, граф Радо - это самодополняющий граф.^[4]

Прочие конструкции

В одной из оригинальных конструкций Аккермана 1937 года вершины графа Радо индексируются наследственно конечными множествами, и между двумя вершинами есть ребро именно тогда, когда одно из соответствующих конечных множеств является членом другого. на основе Парадокс Сколема, факт существования счетной модели для теории множеств первого порядка. Можно построить граф Rado из такой модели, создав вершину для каждого набора, с ребром, соединяющим каждую пару наборов, где один набор в паре является членом другого.^[5]

Граф Rado также может быть образован конструкцией, аналогичной построению для Графики Пэли, взяв за вершины графа все простые числа которые сравнимы с 1 по модулю 4, и соединяющие две вершины ребром, если одно из двух чисел является квадратичный вычет по модулю другого. К квадратичная взаимность и ограничение вершин на простые числа, конгруэнтные 1 по модулю 4, это симметричное отношение, поэтому он определяет неориентированный граф, который оказывается изоморфным графу Радо.^[6]

Другая конструкция графа Радо показывает, что это бесконечный циркулянтный график, с целыми числами в качестве вершин и с ребром между каждыми двумя целыми числами, расстояние между которыми ( абсолютная величина их различия) принадлежит определенному набору S. Чтобы построить граф Радо таким образом, S могут быть выбраны случайным образом или путем выбора индикаторная функция из S быть конкатенацией всех конечных двоичные последовательности.^[7]

График Rado также можно построить как блок граф пересечений бесконечного блочная конструкция в котором количество точек и размер каждого блока счетно бесконечный.^[8]

Характеристики

Расширение

Свойство расширения графа Радо: для любых двух непересекающихся конечных наборов вершин U и V, существует еще одна вершина Икс подключен ко всему в U, и ни к чему в V

Граф Радо удовлетворяет следующему свойству расширения: для любых двух непересекающихся конечных наборов вершин U и V, существует вершина Икс вне обоих множеств, который связан со всеми вершинами в U, но не имеет соседей в V.^[2]Например, с определением двоичного числа графа Радо, пусть

{ displaystyle x = 2 ^ {1+ max (U cup V)} + sum _ {u in U} 2 ^ {u}.}

Тогда ненулевые биты в двоичном представлении Икс заставить его быть рядом со всем в U. Тем не мение, Икс не имеет ненулевых битов в своем двоичном представлении, соответствующих вершинам в V, и Икс настолько велик, что Иксй бит каждого элемента V равно нулю. Таким образом, Икс не смежна ни с одной вершиной в V.^[9]

Согласно определению случайного графа графа Радо, каждая вершина вне объединения U и V имеет вероятность 1/2^{|U| + |V|} выполнения свойства продолжения независимо от других вершин. Поскольку существует бесконечно много вершин на выбор, каждая с одинаковой конечной вероятностью успеха, вероятность равна той, что существует вершина, которая удовлетворяет свойству расширения.^[2] С определением графа Пэли для любых множеств U и V, посредством Китайская теорема об остатках, числа, которые являются квадратичными вычетами по модулю каждого простого числа в U и невычетов по модулю каждого простого числа в V образуют периодическую последовательность, поэтому по Теорема Дирихле на простых числах в арифметических прогрессиях этот теоретико-числовой граф обладает свойством расширения.^[6]

Индуцированные подграфы

Свойство расширения можно использовать для построения изоморфных копий любого конечного или счетно бесконечного графа. грамм внутри графика Rado, как индуцированные подграфы. Для этого упорядочите вершины грамм, и добавить вершины в том же порядке к частичной копии грамм внутри графа Rado. На каждом шаге следующая вершина в грамм будет рядом с некоторым набором U вершин в грамм которые находятся в более раннем порядке вершин и не смежны с оставшимся множеством V более ранних вершин в грамм. Благодаря свойству расширения у графа Rado также будет вершина Икс которая смежна со всеми вершинами в частичной копии, которые соответствуют членам U, и несмежные со всеми вершинами в частичной копии, которые соответствуют членам V. Добавление Икс к частичной копии грамм производит частичную копию большего размера с еще одной вершиной.^[10]

Этот метод лежит в основе Доказательство по индукции, с 0-вершинный подграф в качестве базового случая, что каждое конечное или счетно бесконечный Граф - это индуцированный подграф графа Радо.^[10]

Уникальность

График Rado составляет до изоморфизм графов, единственный счетный граф со свойством расширения. Например, пусть грамм и ЧАС - два счетных графа со свойством расширения, пусть грамм_я и ЧАС_я быть изоморфными конечными индуцированными подграфами грамм и ЧАС соответственно, и пусть грамм_я и час_я быть первыми вершинами в перечислении вершин грамм и ЧАС соответственно, которые не принадлежат грамм_я и ЧАС_я. Тогда, дважды применяя свойство расширения, можно найти изоморфные индуцированные подграфы грамм_я + 1 и ЧАС_я + 1 которые включают грамм_я и час_я вместе со всеми вершинами предыдущих подграфов. Повторяя этот процесс, можно построить последовательность изоморфизмов между индуцированными подграфами, которая в конечном итоге включает каждую вершину в грамм и ЧАС. Таким образом, возвратно-поступательный метод, грамм и ЧАС должен быть изоморфен.^[11]Поскольку графы, построенные с помощью построения случайного графа, построения двоичного числа и построения графа Пэли, являются счетными графами со свойством расширения, этот аргумент показывает, что все они изоморфны друг другу.^[12]

Симметрия

Применение конструкции туда и обратно к любым двум изоморфным конечным подграфам графа Радо расширяет их изоморфизм до автоморфизм всего графа Rado. Тот факт, что любой изоморфизм конечных подграфов продолжается до автоморфизма всего графа, выражается в том, что граф Радо является сверходнородный. В частности, существует автоморфизм, переводящий любую упорядоченную пару смежных вершин в любую другую такую упорядоченную пару, так что граф Радо является симметричный граф.^[11]

В группа автоморфизмов графа Радо является простая группа, количество элементов которого равно мощность континуума. Каждый подгруппа этой группы, чья индекс меньше мощности континуума, может быть зажат между поточечным стабилизатором и стабилизатором конечного множества вершин.^[13]

Построение графа Радо как бесконечного циркулянтного графа показывает, что его группа симметрии включает автоморфизмы, порождающие транзитивный бесконечная циклическая группа. Набор разностей этой конструкции (набор расстояний в целых числах между соседними вершинами) можно ограничить, чтобы включить разность 1, не влияя на правильность этой конструкции, из чего следует, что граф Радо содержит бесконечную Гамильтонов путь симметрии которого являются подгруппой симметрий всего графа.^[14]

Устойчивость к конечным изменениям

Если график грамм формируется из графа Rado путем удаления любого конечного числа ребер или вершин или добавления конечного числа ребер, изменение не влияет на свойство расширения графа. Для любой пары наборов U и V все еще можно найти вершину в модифицированном графе, которая смежна со всем в U и не примыкает ко всему в V, добавив измененные части грамм к V и применение свойства расширения в немодифицированном графе Rado. Следовательно, любая конечная модификация этого типа приводит к графу, изоморфному графу Радо.^[15]

Раздел

Для любого разбиения вершин графа Радо на два множества А и B, или, в более общем смысле, для любого разбиения на конечное число подмножеств, по крайней мере, один из подграфов, индуцированных одним из множеств разбиений, изоморфен всему графу Радо. Кэмерон (2001) дает следующее короткое доказательство: если ни одна из частей не индуцирует подграф, изоморфный графу Радо, все они не обладают свойством расширения, и можно найти пары множеств U_я и V_я это не может быть расширено в пределах каждого подграфа. Но тогда объединение множеств U_я и объединение множеств V_я будет формировать набор, который не может быть расширен на весь граф, что противоречит свойству расширения графа Rado. Это свойство быть изоморфным одному из индуцированных подграфов любого разбиения поддерживается только тремя счетно бесконечными неориентированными графами: графом Радо, графом полный график, а пустой график.^[16] Бонато, Кэмерон и Делич (2000) и Diestel et al. (2007) исследовать бесконечное ориентированные графы с таким же свойством раздела; все они формируются путем выбора ориентации ребер полного графа или графа Радо.

Связанный результат касается разбиения ребер вместо разбиения вершин: для каждого разбиения ребер графа Радо на конечное число множеств существует подграф, изоморфный всему графу Радо, который использует не более двух цветов. Однако не обязательно может существовать изоморфный подграф, который использует только один цвет ребер.^[17]

Теория моделей и законы 0-1

Феджин (1976) использовал граф Радо, чтобы доказать закон нуля или единицы за первый заказ заявления в логика графиков. Когда логическое утверждение этого типа истинно или ложно для графика Rado, оно также истинно или ложно (соответственно) для почти все конечные графы.

Свойства первого порядка

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

{ Displaystyle forall u: существует v: u sim v}

где ${ displaystyle sim}$ символ указывает отношение смежности между двумя вершинами.^[18]Это предложение ${ displaystyle S}$ верно для одних графиков и ложно для других; график ${ displaystyle G}$ говорят модель ${ displaystyle S}$ , написано ${ displaystyle G models S}$ , если ${ displaystyle S}$ верно для вершин и отношения смежности ${ displaystyle G}$ .^[19]

Свойство расширения графа Rado может быть выражено набором предложений первого порядка. ${ displaystyle E_ {i, j}}$ , заявляя, что для каждого выбора ${ displaystyle i}$ вершины в наборе ${ displaystyle A}$ и ${ displaystyle j}$ вершины в наборе ${ displaystyle B}$ , все различны, существует вершина, смежная со всем в ${ displaystyle A}$ и не примыкает ко всему в ${ displaystyle B}$ .^[20] Например, ${ displaystyle E_ {1,1}}$ можно записать как

{ displaystyle forall a: forall b: a neq b rightarrow exists c: c neq a wedge c neq b wedge c sim a wedge lnot (c sim b).}

Полнота

Гайфман (1964) доказал, что предложения ${ displaystyle E_ {i, j}}$ , вместе с дополнительными предложениями, утверждающими, что отношение смежности симметричный и антирефлексивный (то есть, что граф, моделирующий эти предложения, неориентирован и не имеет петель), являются аксиомами полная теория. Это означает, что для каждого предложения первого порядка ${ displaystyle S}$ , ровно один из ${ displaystyle S}$ и его отрицание может быть доказано с помощью этих аксиом. Поскольку граф Радо моделирует аксиомы расширения, он моделирует все предложения в этой теории.^[21]

В логике теория, имеющая только одну модель (с точностью до изоморфизма) с заданной бесконечной мощность $λ$ называется $λ$ -категория. Тот факт, что граф Радо является единственным счетным графом со свойством расширения, означает, что он также является единственной счетной моделью для своей теории. Это свойство уникальности графа Радо можно выразить, сказав, что теория графа Радо ω-категоричный. Łoś и Vaught в 1954 г. доказал, что когда теория $λ$ –Категория (для некоторого бесконечного кардинала $λ$ ) и, кроме того, не имеет конечных моделей, то теория должна быть полной.^[22] Следовательно, теорема Гайфмана о полноте теории графа Радо следует из единственности графа Радо Тест Лось – Воота.^[23]

Конечные графы и вычислительная сложность

В качестве Феджин (1976) Доказано, что предложения первого порядка, выводимые из аксиом расширения и моделируемые графом Радо, являются в точности предложениями, истинными для почти все случайные конечные графы. Это означает, что если выбрать $п$ -вершинный граф равномерно случайным образом среди всех графов на $п$ помеченные вершины, то вероятность того, что такое предложение будет верным для выбранного графа, приближается к единице в пределе $п$ приближается к бесконечности. Симметрично предложения, которые не моделируются графом Радо, ложны почти для всех случайных конечных графов. Отсюда следует, что каждое предложение первого порядка либо почти всегда истина или почти всегда ложь для случайных конечных графов, и эти две возможности можно различить, определив, моделирует ли граф Радо предложение. Доказательство Феджина использует теорема компактности,^[24] Основываясь на этой эквивалентности, теория предложений, смоделированная графом Радо, была названа «теорией случайного графа» или «почти верной теорией графов».

Благодаря этому закону 0-1 можно проверить, моделируется ли какое-либо конкретное предложение первого порядка графом Радо за конечный промежуток времени, выбрав достаточно большое значение $п$ и подсчитывая количество $п$ -вершинные графы, моделирующие предложение. Однако здесь «достаточно большой» по крайней мере экспоненциально зависит от размера предложения. Например, аксиома расширения $E k,0$ подразумевает наличие $(k + 1)$ -вертекс клика, но клика такого размера существует с высокой вероятностью только в случайных графах экспоненциального размера в $k$ Маловероятно, что определение того, моделирует ли граф Rado данное предложение, может быть выполнено быстрее, чем экспоненциальное время, поскольку проблема заключается в следующем. PSPACE-полный.^[25]

Насыщенная модель

От теоретическая модель точки зрения, график Rado является примером насыщенная модель. Это всего лишь логическая формулировка того свойства, что граф Радо содержит все конечные графы как индуцированные подграфы.^[26]

В этом контексте тип представляет собой набор переменных вместе с набором ограничений на значения некоторых или всех предикатов, определенных этими переменными; Полный тип - это тип, который ограничивает все предикаты, определяемые его переменными. В теории графов переменные представляют вершины, а предикаты - это смежности между вершинами, поэтому полный тип определяет, присутствует ли ребро между каждой парой вершин, представленных заданными переменными, или нет. То есть полный тип определяет подграф, который индуцирует определенный набор переменных вершины.^[26]

Насыщенная модель - это модель, которая реализует все типы, которые имеют количество переменных, не более чем мощность модели. Граф Радо имеет индуцированные подграфы всех конечных или счетно бесконечных типов, поэтому он насыщен.^[26]

Связанные понятия

Хотя граф Радо универсален для индуцированных подграфов, он не универсален для изометрические вложения графов, где изометрическое вложение - это изоморфизм графов, сохраняющий расстояние. График Rado имеет диаметр два, поэтому любой граф большего диаметра не встраивается в него изометрически. Мох (1989, 1991 ) описал семейство универсальных графов для изометрического вложения, по одному для каждого возможного конечного диаметра графа; граф в его семье с диаметром два - это граф Радо.

В Графики Хенсона счетные графы (по одному для каждого положительного целого числа $я$ ), не содержащие $я$ -вертекс клика, и универсальны для $я$ -кликовые графы. Их можно построить как индуцированные подграфы графа Радо.^[14] Граф Радо, графы Хенсона и их дополнения, несвязные объединения счетно бесконечных клик и их дополнений, а также бесконечные несвязные объединения изоморфных конечных клик и их дополнений - единственно возможные счетно бесконечные однородные графы.^[27]

Свойство универсальности графа Радо можно распространить на графы с краской ребра; то есть графы, в которых ребрам присвоены разные цветовые классы, но без обычных окраска края требование, чтобы каждый цветовой класс образовывал соответствие. Для любого конечного или счетно бесконечного числа цветов χ существует единственный счетно-бесконечный χ-крашеный граф грамм_χ такой, что любой частичный изоморфизм конечного графа, раскрашенного χ-ребрами, можно продолжить до полного изоморфизма. В этих обозначениях график Rado просто грамм₁. Ферма (1985) исследует группы автоморфизмов этого более общего семейства графов.

Из соображений классической теории моделей построения насыщенной модели следует, что при гипотеза континуума CH существует универсальный граф с континуум много вершин. Конечно, при CH континуум равен ${ displaystyle aleph _ {1}}$ , то первый несчетный кардинал. Шела (1984, 1990 ) использует принуждение исследовать универсальные графы с ${ displaystyle aleph _ {1}}$ много вершин и показывает, что даже в отсутствие CH может существовать универсальный граф размера ${ displaystyle aleph _ {1}}$ . Он также исследует аналогичные вопросы для более высоких мощностей.

Примечания

^ Аккерманн (1937); Rado (1964).
^ ^а ^б ^c Видеть Кэмерон (1997), Факт 1 и его доказательство.
^ Эрдеш и Реньи (1963).
^ Кэмерон (1997), Предложение 5.
^ Кэмерон (1997), Теорема 2.
^ ^а ^б Кэмерон (1997, 2001 )
^ Кэмерон (1997), Раздел 1.2.
^ Хорсли, Пайк и Санаи (2011)
^ По сути, та же конструкция, описанная в теоретико-множественных терминах, а не с использованием двоичных чисел, дается как теорема 2 из Кэмерон (1997).
^ ^а ^б Кэмерон (1997), Предложение 6.
^ ^а ^б Кэмерон (2001).
^ Кэмерон (1997), Факт 2.
^ Кэмерон (1997), Раздел 1.8: Группа автоморфизмов.
^ ^а ^б Хенсон (1971).
^ Кэмерон (1997), Раздел 1.3: Неразрушимость.
^ Кэмерон (1990); Diestel et al. (2007).
^ Пузе и Зауэр (1996).
^ Спенсер (2001), Раздел 1.2, «Что такое теория первого порядка?», стр. 15–17.
^ См., Например, Гранджин (1983), п. 184.
^ Спенсер (2001), Раздел 1.3, «Операторы расширения и корневые графы», стр. 17–18.
^ Гайфман (1964); Маркер (2002), Теорема 2.4.2, с. 50.
^ Лось (1954); Воот (1954); Эндертон (1972), п. 147.
^ Маркер (2002), Теорема 2.2.6, с. 42.
^ Феджин (1976); Маркер (2002), Теорема 2.4.4, с. 51–52.
^ Гранджин (1983).
^ ^а ^б ^c Ласкар (2002).
^ Лахлан и Вудро (1980).