Радо график

Бесконечный граф, содержащий все счетные графы

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

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

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

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

История

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

Конструкции

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

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

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

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

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

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

Другие конструкции

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

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

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

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

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

Расширение

Свойство расширения графа Радо: для каждых двух непересекающихся конечных множеств вершин и существует еще одна вершина, соединенная со всем в и ни с чем в ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle x}$ ${\displaystyle U}$ ${\displaystyle V}$

Граф Радо удовлетворяет следующему свойству расширения: для любых двух непересекающихся конечных множеств вершин и существует вершина вне обоих множеств, которая соединена со всеми вершинами в , но не имеет соседей в . ^[2] Например, с определением графа Радо в виде двоичных чисел, пусть Тогда ненулевые биты в двоичном представлении заставляют его быть смежным со всем в . Однако не имеет ненулевых битов в своем двоичном представлении, соответствующих вершинам в , и настолько велик, что -й бит каждого элемента равен нулю. Таким образом, не смежно ни с одной вершиной в . ^[10] ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle x}$ ${\displaystyle U}$ ${\displaystyle V}$ $${\displaystyle x=2^{1+\max(U\cup V)}+\sum _{u\in U}2^{u}.}$$ ${\displaystyle x}$ ${\displaystyle U}$ ${\displaystyle x}$ ${\displaystyle V}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle V}$ ${\displaystyle x}$ ${\displaystyle V}$

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

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

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

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

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

Граф Радо является, с точностью до изоморфизма графов , единственным счетным графом со свойством расширения. Например, пусть и будут двумя счетными графами со свойством расширения, пусть и будут изоморфными конечными индуцированными подграфами и соответственно, и пусть и будут первыми вершинами в перечислении вершин и соответственно, которые не принадлежат и . Затем, применяя свойство расширения дважды, можно найти изоморфные индуцированные подграфы и , которые включают и вместе со всеми вершинами предыдущих подграфов. Повторяя этот процесс, можно построить последовательность изоморфизмов между индуцированными подграфами, которая в конечном итоге включает каждую вершину в и . Таким образом, методом возврата и вперед и должны быть изоморфны. ^[12] Поскольку графы, построенные с помощью построения случайного графа, построения двоичного числа и построения графа Пейли, являются счетными графами со свойством расширения, этот аргумент показывает, что все они изоморфны друг другу. ^[13] ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G_{i}}$ ${\displaystyle H_{i}}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle g_{i}}$ ${\displaystyle h_{i}}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G_{i}}$ ${\displaystyle H_{i}}$ ${\displaystyle G_{i+1}}$ ${\displaystyle H_{i+1}}$ ${\displaystyle g_{i}}$ ${\displaystyle h_{i}}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$

Группа симметрии

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

Группа автоморфизмов графа Радо является простой группой , число элементов которой равно мощности континуума . Каждая подгруппа этой группы, индекс которой меньше мощности континуума, содержит поточечный стабилизатор конечного множества вершин и, кроме того, содержится внутри поточечного стабилизатора того же множества. ^[14] Утверждение о поточечных стабилизаторах называется свойством малого индекса, ^[14] и для его доказательства требуется показать, что для каждого конечного графа существует конечный граф, содержащий в качестве индуцированного подграфа такой, что каждый изоморфизм между индуцированными подграфами из продолжается до автоморфизма из . ^[15] Это называется свойством расширения для частичных автоморфизмов и с тех пор было обобщено на другие структуры, чтобы показать свойство малого индекса и другие свойства. ^[16] ${\displaystyle X}$ ${\displaystyle Z}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle Z}$

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

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

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

Разделы

Для любого разбиения вершин графа Радо на два множества и , или, в более общем случае, для любого разбиения на конечное число подмножеств, по крайней мере один из подграфов, индуцированных одним из множеств разбиения, изоморфен всему графу Радо. Кэмерон (2001) дает следующее короткое доказательство: если ни одна из частей не индуцирует подграф, изоморфный графу Радо, все они не обладают свойством расширения, и можно найти пары множеств и , которые не могут быть расширены внутри каждого подграфа. Но тогда объединение множеств и объединение множеств образовали бы множество, которое не могло бы быть расширено во всем графе, что противоречит свойству расширения графа Радо. Это свойство быть изоморфным одному из индуцированных подграфов любого разбиения сохраняется только у трех счетно бесконечных неориентированных графов: графа Радо, полного графа и пустого графа . ^[19] Бонато, Кэмерон и Делич (2000) и Дистель и др. (2007) исследуют бесконечные ориентированные графы с одинаковым свойством разбиения; все они образованы путем выбора ориентаций для ребер полного графа или графа Радо. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle U_{i}}$ ${\displaystyle V_{i}}$ ${\displaystyle U_{i}}$ ${\displaystyle V_{i}}$

Связанный результат касается разбиений ребер вместо разбиений вершин: для каждого разбиения ребер графа Радо на конечное число множеств существует подграф, изоморфный всему графу Радо, который использует не более двух цветов. Однако не обязательно может существовать изоморфный подграф, который использует только один цвет ребер. ^[20] В более общем смысле, для каждого конечного графа существует число (называемое большой степенью Рамсея в графе Радо) такое, что для каждого разбиения копий в графе Радо на конечное число множеств существует индуцированный подграф, изоморфный всему графу Радо, который использует не более двух цветов. ^{[21] [22]} ${\displaystyle A}$ ${\displaystyle d_{A}}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle d_{A}}$

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

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

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

Язык графов первого порядка — это набор правильно построенных предложений в математической логике, образованных из переменных, представляющих вершины графов, универсальных и экзистенциальных квантификаторов , логических связок и предикатов для равенства и смежности вершин. Например, условие, что граф не имеет изолированных вершин, может быть выражено предложением , где символ указывает на отношение смежности между двумя вершинами. ^[23] Это предложение истинно для некоторых графов и ложно для других; говорят, что граф моделирует , записанное , если истинно для вершин и отношения смежности . ^[24] $${\displaystyle \forall u:\exists v:u\sim v}$$ ${\displaystyle \sim }$ ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle G\models S}$ ${\displaystyle S}$ ${\displaystyle G}$

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

В логике теория, которая имеет только одну модель (с точностью до изоморфизма) с заданной бесконечной мощностью, называется -категоричной . Тот факт, что граф Радо является единственным счетным графом со свойством расширения, подразумевает, что он также является единственной счетной моделью для своей теории. Это свойство уникальности графа Радо можно выразить, сказав, что теория графа Радо является ω-категоричной . Лос и Воут доказали в 1954 году, что когда теория является -категоричной (для некоторого бесконечного кардинала ) и, кроме того, не имеет конечных моделей, то теория должна быть полной. ^[27] Следовательно, теорема Гайфмана о том, что теория графа Радо является полной, следует из уникальности графа Радо по тесту Лоса–Воута . ^[28] ${\displaystyle \lambda }$ ${\displaystyle \lambda }$ ${\displaystyle \lambda }$ ${\displaystyle \lambda }$

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

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

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

Другие модельно-теоретические свойства

Граф Радо является ультраоднородным и, таким образом, является пределом Фраисса своего класса конечных подструктур, т.е. класса конечных графов. ^[31] Учитывая, что он также находится в конечном реляционном языке, ультраоднородность эквивалентна его теории, имеющей исключение кванторов и являющейся ω-категоричной. ^[32] Поскольку граф Радо является, таким образом, счетной моделью счетной ω-категоричной теории, он является как простым , так и насыщенным . ^{[33] [34]}

Теория графа Радо является прототипическим примером теории со свойством независимости и простой теории, которая не является стабильной . ^[35]

Связанные концепции

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

Графы Хенсона — это счетные графы (по одному для каждого положительного целого числа ), которые не содержат клику вершин и являются универсальными для графов без клик. Они могут быть построены как индуцированные подграфы графа Радо. ^[17] Граф Радо, графы Хенсона и их дополнения, несвязные объединения счетно бесконечных клик и их дополнений, а также бесконечные несвязные объединения изоморфных конечных клик и их дополнений являются единственными возможными счетно бесконечными однородными графами . ^[36] ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i}$

Свойство универсальности графа Радо может быть распространено на графы с рёбрами, то есть графы, в которых рёбрам присвоены различные цветовые классы, но без обычного требования к раскраске рёбер, чтобы каждый цветовой класс образовывал соответствие . Для любого конечного или счётно бесконечного числа цветов существует уникальный счётно бесконечный -рёберно -раскрашенный граф такой, что каждый частичный изоморфизм -рёберно-раскрашенного конечного графа может быть расширен до полного изоморфизма. С этой нотацией граф Радо — это просто . Трасс (1985) исследует группы автоморфизмов этого более общего семейства графов. ${\displaystyle \chi }$ ${\displaystyle \chi }$ ${\displaystyle G_{\chi }}$ ${\displaystyle \chi }$ ${\displaystyle G_{1}}$

В то время как граф Радо является счетным универсальным для класса всех графов, не все классы графов имеют счетный универсальный граф. Например, не существует счетного графа, исключающего 4-цикл как подграф, который содержит все другие такие счетные графы как (не обязательно индуцированные) подграфы. ^[37]

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

Примечания

1. Акерман (1937); Радо (1964).
2. См. Кэмерон (1997), Факт 1 и его доказательство.
3. Эрдёш и Реньи (1963).
4. Кэмерон (1997), Предложение 5.
5. Кэмерон (1997), Теорема 2.
6. Кэмерон (1997, 2001)
7. Кэмерон (1997), Раздел 1.2.
8. Хорсли, Пайк и Санаи (2011)
9. Ходжес (1997), стр. 350.
10. По сути та же конструкция, описанная в терминах теории множеств, а не с использованием двоичных чисел, приведена в Теореме 2 Кэмерона (1997).
11. Cameron (1997), Предложение 6.
12. Кэмерон (2001).
13. Кэмерон (1997), Факт 2.
14. Cameron (1997), Раздел 1.8: Группа автоморфизмов.
15. Грушовский (1992)
16. Макферсон (2011), разделы 5.2 и 5.3.
17. Хенсон (1971).
18. Кэмерон (1997), Раздел 1.3: Неразрушимость.
19. Кэмерон (1990); Дистель и др. (2007).
20. Пузе и Зауэр (1996).
21. Зауэр (2006)
22. Добринен (2021)
23. Спенсер (2001), Раздел 1.2, «Что такое теория первого порядка?», стр. 15–17.
24. См., например, Гранжан (1983), с. 184.
25. Спенсер (2001), Раздел 1.3, «Операторы расширения и корневые графы», стр. 17–18.
26. Гайфман (1964); Маркер (2002), Теорема 2.4.2, стр. 50.
27. Лось (1954); Воот (1954); Эндертон (1972), с. 147.
28. Маркер (2002), Теорема 2.2.6, стр. 42.
29. Фейгин (1976); Маркер (2002), Теорема 2.4.4, стр. 51–52.
30. Гранжан (1983).
31. Макферсон (2011), Теорема 2.1.3, Пример 2.2.1.
32. Макферсон (2011), Следствие 3.1.3, Предложение 3.1.6.
33. Ротмалер (2000), Теорема 13.3.1, Теорема 13.2.1.
34. МакНалти (2016), стр.71 и стр.75.
35. Болдуин (2018)
36. Лаклан и Вудро (1980).
37. Черлин (2011), Факт 1.3

Ссылки

• Акерманн, Вильгельм (1937), «Die Widerspruchsfreiheit der allgemeinen Mengenlehre», Mathematische Annalen , 114 (1): 305–315, doi : 10.1007/BF01594179, S2CID  120576556
• Бонато, Энтони; Кэмерон, Питер ; Делич, Деян (2000), «Турниры и порядки со свойством «пигхола»», Канадский математический вестник , 43 (4): 397–405, doi : 10.4153/CMB-2000-047-6 , MR  1793941.
• Болдуин, Джон Т. (2018), Теория моделей и философия математической практики: формализация без фундаментализма , Cambridge University Press, doi : 10.1017/9781316987216, ISBN 978-1-107-18921-8, MR  3793636, S2CID  126311148.
• Кэмерон, Питер Дж. (1990), Олигоморфные группы перестановок , Серия лекций Лондонского математического общества, т. 152, Кембридж: Cambridge University Press, ISBN 0-521-38836-8, МР  1066691.
• Кэмерон, Питер Дж. (1997), «Случайный граф», Математика Пола Эрдёша, II , Алгоритмы и комбинаторика , т. 14, Берлин: Springer, стр. 333–351, arXiv : 1301.7544 , Bibcode : 2013arXiv1301.7544C, MR  1425227.
• Кэмерон, Питер Дж. (2001), «Случайный граф снова» (PDF) , Европейский математический конгресс , т. I (Барселона, 2000) , Progr. Math., т. 201, Базель: Birkhäuser, стр. 267–274, doi :10.1007/978-3-0348-8268-2_15, MR  1905324.
• Черлин, Грегори (2011), «Запрещенные подструктуры и комбинаторные дихотомии: WQO и универсальность», Дискретная математика , 311 (15): 1543–1584, doi :10.1016/j.disc.2011.03.014, MR  2800977.
• Дистель, Рейнхард; Лидер, Имре ; Скотт, Алекс; Томассе, Стефан (2007), «Разбиения и ориентации графа Радо», Труды Американского математического общества , 359 (5): 2395–2405, doi : 10.1090/S0002-9947-06-04086-4 , MR  2276626.
• Добринен, Наташа (2021), «Теория однородных структур Рамсея: современные тенденции и открытые проблемы», arXiv : 2110.00655v1 [math.LO].
• Эндертон, Герберт Б. (1972), Математическое введение в логику , Academic Press, Нью-Йорк-Лондон, MR  0337470.
• Эрдеш, П .; Реньи, А. (1963), «Асимметричные графы», Acta Mathematica Academiae Scientiarum Hungaricae , 14 (3–4): 295–315, doi : 10.1007/BF01895716 , MR  0156334.
• Fagin, Ronald (1976), "Вероятности конечных моделей" (PDF) , The Journal of Symbolic Logic , 41 (1): 50–58, doi :10.1017/s0022481200051756, JSTOR  2272945, MR  0476480, S2CID  2563318, заархивировано из оригинала (PDF) 2016-03-04 , извлечено 2014-09-05.
• Гайфман, Хаим (1964), «О мерах в исчислениях первого порядка», Israel Journal of Mathematics , 2 : 1–18, doi : 10.1007/BF02759729 , MR  0175755.
• Гранжан, Этьен (1983), «Сложность теории первого порядка почти всех конечных структур», Информация и управление , 57 (2–3): 180–204, doi : 10.1016/S0019-9958(83)80043-6 , MR  0742707.
• Хенсон, К. Уорд (1971), «Семейство счетных однородных графов», Pacific Journal of Mathematics , 38 : 69–83, doi : 10.2140/pjm.1971.38.69 , MR  0304242.
• Ходжес, Уилфрид (1997), Теория более короткой модели , Cambridge University Press, ISBN 0-521-58713-1, OCLC  468298248
• Хорсли, Дэниел; Пайк, Дэвид А.; Санаи, Асие (2011), «Экзистенциальное замыкание графов пересечения блоков бесконечных конструкций, имеющих бесконечный размер блока», Журнал комбинаторных конструкций , 19 (4): 317–327, doi :10.1002/jcd.20283, MR  2838911, S2CID  120707836.
• Хрушовски, Эхуд (1992), «Расширение частичных изоморфизмов графов», Combinatorica , 12 (4): 411–416, doi :10.1007/BF01305233, MR  1194731, S2CID  19939702.
• Лаклан, AH; Вудро, Роберт Э. (1980), «Счетные ультраоднородные неориентированные графы», Труды Американского математического общества , 262 (1): 51–94, doi : 10.2307/1999974 , JSTOR  1999974, MR  0583847.
• Лос, Й. (1954), «О категоричности в мощности элементарных дедуктивных систем и некоторых связанных с этим проблемах», Colloquium Math. , 3 : 58–62, doi : 10.4064/cm-3-1-58-62 , MR  0061561.
• Макферсон, Дугалд (2011), «Обзор однородных структур», Дискретная математика , 311 (15): 1599–1634, doi : 10.1016/j.disc.2011.01.024 , MR  2800979.
• Маркер, Дэвид (2002), Теория моделей , Graduate Texts in Mathematics, т. 217, Springer-Verlag, Нью-Йорк, ISBN 0-387-98760-6, г-н  1924282.
• МакНалти, Джордж Ф. (2016), Elementary Model Theory (PDF) , стр. 71–75 , получено 5 апреля 2023 г..
• Мосс, Лоуренс С. (1989), «Существование и несуществование универсальных графов», Польская академия наук. Fundamenta Mathematicae , 133 (1): 25–37, doi : 10.4064/fm-133-1-25-37 , MR  1059159.
• Мосс, Лоуренс С. (1991), «Универсальные графы фиксированного конечного диаметра», Теория графов, комбинаторика и приложения. Т. 2 (Каламазу, Мичиган, 1988) , Wiley-Intersci. Publ., Нью-Йорк: Wiley, стр. 923–937, MR  1170834.
• Пузе, Морис; Зауэр, Норберт (1996), «Разбиения рёбер графа Радо», Combinatorica , 16 (4): 505–520, doi :10.1007/BF01271269, MR  1433638, S2CID  206793062.
• Радо, Ричард (1964), «Универсальные графы и универсальные функции» (PDF) , Acta Arith. , 9 (4): 331–340, doi :10.4064/aa-9-4-331-340.
• Ротмалер, Филипп (2000), Введение в теорию моделей , Алгебра, логика и приложения, т. 15, Gordon and Breach Science Publishers, ISBN 90-5699-287-2, МР  1800596.
• Зауэр, Норберт (2006), «Раскраска подграфов графа Радо», Combinatorica , 26 (2): 231–253, doi :10.1007/s00493-006-0015-0, MR  2223636, S2CID  19251747.
• Шелах, Сахарон (1984), «Об универсальных графах без примеров CH», Annals of Pure and Applied Logic , 26 (1): 75–87, doi : 10.1016/0168-0072(84)90042-3 , MR  0739914.
• Шелах, Сахарон (1990), «Универсальные графы без экземпляров CH: пересмотр», Israel Journal of Mathematics , 70 (1): 69–81, doi : 10.1007/BF02807219 , MR  1057268.
• Спенсер, Джоэл (2001), Странная логика случайных графов , Алгоритмы и комбинаторика, т. 22, Springer-Verlag, Берлин, doi :10.1007/978-3-662-04538-1, ISBN 3-540-41654-4, MR  1847951, S2CID  118026950.
• Truss, JK (1985), «Группа счетного универсального графа», Математические труды Кембриджского философского общества , 98 (2): 213–245, Bibcode : 1985MPCPS..98..213T, doi : 10.1017/S0305004100063428, MR  0795890, S2CID  122772888.
• Воот, Роберт Л. (1954), «Применение теоремы Лёвенгейма-Сколема-Тарского к проблемам полноты и разрешимости», Indagationes Mathematicae , 16 : 467–472, doi :10.1016/S1385-7258(54)50058-2, MR  0063993.