График Rado

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

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

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

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

История [ править ]

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

Конструкции [ править ]

Двоичные числа [ править ]

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

Случайный график [ править ]

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

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

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

Другие конструкции [ править ]

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

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

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

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

Свойства [ править ]

Расширение [ править ]

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

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

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

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

Индуцированные подграфы [ править ]

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

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

Уникальность [ править ]

Граф Радо, с точностью до изоморфизма графов , является единственным счетным графом со свойством расширения. Например, пусть G и H - два счетных графа со свойством расширения, пусть G _i и H _i - изоморфные конечные индуцированные подграфы G и H соответственно, и пусть g _i и h _i - первые вершины в перечислении вершин группы G и H соответственно, не принадлежащие G _i и H _i. Затем, дважды применяя свойство расширения, можно найти изоморфные индуцированные подграфы G _{i  + 1} и H _{i  + 1,} которые включают g _i и h _i вместе со всеми вершинами предыдущих подграфов. Повторяя этот процесс, можно построить последовательность изоморфизмов между индуцированными подграфами , что в конечном итоге включает в себя каждую вершину в G и H . Таким образом, с помощью метода назад и вперед , G и Н должны быть изоморфны. ^[11]Поскольку графы, построенные путем построения случайного графа, построения двоичного числа и построения графа Пэли, являются счетными графами со свойством расширения, этот аргумент показывает, что все они изоморфны друг другу. ^[12]

Симметрия [ править ]

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

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

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

Устойчивость к конечным изменениям [ править ]

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

Раздел [ править ]

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

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

Теория моделей и законы 0-1 [ править ]

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

Свойства первого порядка [ править ]

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

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

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

Свойство расширения графа Rado может быть выражено набором предложений первого порядка , утверждающих, что для каждого выбора вершин в наборе и вершин в наборе , все различные, существует вершина, смежная со всем и не смежная со всем. в . ^[20] Например, можно записать как${\ displaystyle E_ {i, j}}$${\ displaystyle i}$${\ displaystyle A}$${\ displaystyle j}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$${\ 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) доказал, что предложения вместе с дополнительными предложениями, утверждающими, что отношение смежности является симметричным и антирефлексивным (то есть, что граф, моделирующий эти предложения, неориентирован и не имеет петель), являются аксиомами полной теории . Это означает, что для каждого предложения первого порядка с помощью этих аксиом может быть доказано ровно одно из и его отрицание. Поскольку граф Rado моделирует аксиомы расширения, он моделирует все предложения этой теории. ^[21]${\displaystyle E_{i,j}}$${\displaystyle S}$${\displaystyle S}$

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

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

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

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

Насыщенная модель [ править ]

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

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

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

Понятия, связанные с данным [ править ]

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

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

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

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

Заметки [ править ]

Ссылки [ править ]