График Радо

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

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

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

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

История

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

Конструкции

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

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

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

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

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

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

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

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

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

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

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

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

Расширение

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

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

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

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

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

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

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

Граф Радо — с точностью до изоморфизма графа единственный счетный граф со свойством расширения . Например, пусть $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$ и $H$ должно быть изоморфно. Поскольку графы, построенные с помощью конструкции случайного графа, конструкции двоичного числа и конструкции графа Пэли, являются счетными графами со свойством расширения, этот аргумент показывает, что все они изоморфны друг другу.

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

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

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

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

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

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

Перегородки

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

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

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

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

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

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

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

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

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

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

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

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

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

Теория графа Радо является прототипическим примером теории со свойством независимости и простой теории , которая не является устойчивой .

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

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

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

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

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

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

Ссылки

• Акерманн, Вильгельм (1937), «Непротиворечивость общей теории множеств», Mathematical Annals , 114 (1): 305–315, doi : 10.1007/BF01594179 , S2CID   120576556
• Бонато, Энтони; Кэмерон, Питер ; Делич, Деян (2000), «Турниры и заказы со свойством ячейки», Canadian Mathematical Bulletin , 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 , МР   3793636 , S2CID   126311148 .
• Кэмерон, Питер Дж. (1990), Олигоморфные группы перестановок , Серия лекций Лондонского математического общества, том. 152, Кембридж: Издательство Кембриджского университета, ISBN  0-521-38836-8 , МР   1066691 .
• Кэмерон, Питер Дж. (1997), «Случайный граф», Математика Пола Эрдёша, II , Алгоритмы и комбинаторика , том. 14, Берлин: Springer, стр. 333–351, arXiv : 1301.7544 , Bibcode : 2013arXiv1301.7544C , MR   1425227 .
• Кэмерон, Питер Дж. (2001), «Возвращение к случайному графу» (PDF) , Европейский математический конгресс , Vol. I (Барселона, 2000) , Progr. Матем., вып. 201, Базель: Биркхойзер, стр. 267–274, номер документа : 10.1007/978-3-0348-8268-2_15 , MR   1905324 .
• Черлин, Грегори (2011), «Запрещенные подструктуры и комбинаторные дихотомии: WQO и универсальность», Discrete Mathematics , 311 (15): 1543–1584, doi : 10.1016/j.disc.2011.03.014 , MR   2800977 .
• Дистель, Рейнхард; Лидер, Имре ; Скотт, Алекс; Томассе, Стефан (2007), «Разбиения и ориентации графа Радо», Transactions of the American Mathematical Society , 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), «Асимметричные графы», Математический журнал Венгерской академии наук , 14 (3–4): 295–315, doi : 10.1007/BF01895716 , MR   0156334 .
• Феджин, Рональд (1976), «Вероятности в конечных моделях» (PDF) , Журнал символической логики , 41 (1): 50–58, doi : 10.1017/s0022481200051756 , JSTOR   2272945 , MR   0476480 , S2CID   2563318 .
• Гайфман, Хаим (1964), «О мерах в исчислениях первого порядка», Израильский математический журнал , 2 : 1–18, doi : 10.1007/BF02759729 , MR   0175755 .
• Гранжан, Этьен (1983), «Сложность теории первого порядка почти всех конечных структур», Information and Control , 57 (2–3): 180–204, doi : 10.1016/S0019-9958(83)80043-6 , МР   0742707 .
• Хенсон, К. Уорд (1971), «Семейство счетных однородных графов», Pacific Journal of Mathematics , 38 : 69–83, doi : 10.2140/pjm.1971.38.69 , MR   0304242 .
• Ходжес, Уилфрид (1997), Более короткая теория моделей , издательство Кембриджского университета, ISBN  0-521-58713-1 , OCLC   468298248
• Хорсли, Дэниел; Пайк, Дэвид А.; Санаи, Асие (2011), «Экзистенциальное замыкание графов пересечения блоков бесконечных конструкций, имеющих бесконечный размер блока», Journal of Combinatorial Designs , 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 .
• Лахлан, АХ; Вудро, Роберт Э. (1980), «Счетные ультраоднородные неориентированные графы», Transactions of the American Mathematical Society , 262 (1): 51–94, doi : 10.2307/1999974 , JSTOR   1999974 , MR   0583847 .
• Лось, Дж. (1954), «О категоричности по степени элементарных дедуктивных систем и некоторых связанных с этим проблемах», Colloquium Math. , 3 : 58–62, doi : 10,4064/см-3-1-58-62 , MR   0061561 .
• Макферсон, Дугалд (2011), «Обзор однородных структур», Discrete Mathematics , 311 (15): 1599–1634, doi : 10.1016/j.disc.2011.01.024 , MR   2800979 .
• Маркер, Дэвид (2002), Теория моделей , Тексты для выпускников по математике, том. 217, Спрингер-Верлаг, Нью-Йорк, ISBN  0-387-98760-6 , МР   1924282 .
• МакНалти, Джордж Ф. (2016), Элементарная теория моделей (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, 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, Шпрингер-Верлаг, Берлин, номер номера : 10.1007/978-3-662-04538-1 , ISBN  3-540-41654-4 , MR   1847951 , S2CID   118026950 .
• Трасс, Дж. К. (1985), «Группа счетного универсального графа», Mathematical Proceedings of the Cambridge Philosophical Society , 98 (2): 213–245, Бибкод : 1985MPCPS..98..213T , doi : 10.1017/S0305004100063428 , МР   0795890 , S2CID   122772888 .
• Воот, Роберт Л. (1954), «Применение теоремы Левенхайма-Скулема-Тарского к проблемам полноты и разрешимости», Indagationes Mathematicae , 16 : 467–472, doi : 10.1016/S1385-7258(54)50058-2 , МР   0063993 .