Граф Радо

Граф Радо был построен Вильгельмом Аккерманом и переоткрыт несколько раз. Этот граф рассматривался Ричардом Радо[1], но свойства симметрий этого графа построенного другим способом, рассматривались ранее Палом Эрдёшем и Альфредом Реньи[2].

Аналогичный объект в метрической геометрии, так называемое пространство Урысона, был известен существенно раньше.

Радо брал неотрицательные целые числа в качестве вершин графа. Ребро соединяет вершины x и y при (x < y), если x-ая цифра двоичного представления числа y не равна нулю.

Например, множество всех соседей вершины 0 состоят из нечётных вершин, в то время как соседи вершины 1 — это вершина 0 (единственная вершина, чья цифра в двоичном представлении числа 1 ненулевая) и все вершины, сравнимые с 2 и 3 по модулю 4.

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

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

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

Эту идею нахождения вершин, смежных со всеми вершинами одного подмножества и ни одной вершиной другого можно использовать для построения изоморфной копии любого конечного или бесконечного счётного графа G, последовательно добавляя одну вершину за другой. Пусть G_i — подграф G, порождённый его первыми i вершинами и предположим, что G_i уже найден как индуцированный граф подмножества вершин S графа Радо. Пусть v — следующая вершина в графе G и пусть U — набор соседей вершины v в G_i. Пусть V — набор вершин, не являющихся соседями вершины v в графе G_i. Если x — вершина графа Радо, смежная всем вершинам U и не смежна всем вершинам V, то S ∪ {x} порождает подграф, изоморфный G_i + 1.

По индукции, начиная с пустого графа, получим, что любой конечный или бесконечный счётный граф порождается графом Радо.

Граф Радо, с точностью до изоморфизма, является единственным счётным графом, обладающим свойством расширяемости. Пусть 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 должны быть изоморфны[3].

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

Если граф G получен из графа Радо путём удаления любого конечного числа рёбер или вершин или путём добавления конечного числа рёбер, изменения не влияют на свойство расширяемости графа — для любой пары множеств U и V возможность найти вершину в модифицированном графе, которая смежна всем вершинам из U и не смежна любой вершине из V, остаётся. Просто добавим изменённые части графа G в V и применим свойство расширяемости в немодифицированном графе Радо. Таким образом, любое конечное изменение такого вида приводит к графу, изоморфному графу Радо.

Для любого разбиения множества вершин графа Радо на два подмоножества A и B, или деления на любое конечное число подмножеств, по меньшей мере один из порождённых подграфов будет изоморфен самому графу Радо.

Камерон[3] привёл следующее короткое доказательство этого утверждения: Если ни одна из порождённых частей не изоморфна графу Радо, они все теряют свойство расширяемости, а следовательно, в каждом подграфе можно найти пару множеств U_i и V_i, не поддающихся расширению. Но тогда объединение множеств U_i и объединение V_i образуют два множества, которые нельзя расширить в полном графе, что противоречит свойству расширяемости графа Радо.

Свойство оставаться изоморфным к одному из порождённых подграфов после деления имеют только три счётных бесконечных ненаправленных графа — граф Радо, полный граф и пустой граф[4][5]. Бонато и Камерон[6], а также Дистель и др.[5] исследовали бесконечные ориентированные графы с этим же свойством деления. Оказалось, что все они получаются выбором ориентации дуг в полном графе или графе Радо.

Похожий результат верен для разбиений рёбер — для любого разбиения рёбер графа Радо на конечное число множеств, существует подграф, изоморфный всему графу Радо, использующий максимум два цвета. Однако графа, использующего только один цвет рёбер, может и не существовать[7].

Можно сформировать бесконечный граф в модели Эрдёша — Реньи путём случайного независимого выбора с вероятностью 1/2 для каждой пары вершин, соединять ли две вершины ребром или нет. С вероятностью 1 полученный граф обладает свойством расширяемости, а потому изоморфен графу Радо.

То же построение работает, если взять вместо 1/2 любую фиксированную вероятность p, не равную 0 или 1. Этот результат, доказанный Эрдёшем и Реньи в 1963[2][K 1], оправдывает использование определённого артикля в альтернативном названии «the random graph» (случайный граф) для графа Радо — для конечных графов применение модели рисования Эрдёша — Реньи часто приводит к различным графам, в то время как счётный бесконечный граф почти всегда получается один и тот же. Поскольку можно получить тот же граф Радо после изменения всех выборов на обратные, граф Радо самодополнителен.

Как пишет Камерон[3], граф Радо можно получить при использовании методов, похожих на методы построения графов Пэли. Возьмём в качестве вершин все простые числа, не дающие 1 в остатке от деления на 4, и соединим две вершины ребром, если одно из чисел является квадратичным вычетом по модулю другого (согласно квадратичной взаимности и исключению простых чисел, дающих остаток 1 при делении на 4, это отношение симметрично, так что получим ненаправленный граф). Теперь, для любых множеств U и V, по китайской теореме об остатках, числа, квадратично сравнимые по простому модулю из U и не сравнимые с простыми числами из V, образуют периодическую последовательность, так что согласно теореме Дирихле о простых числах в арифметической прогрессии этот теоретико-числовой граф имеет свойство расширяемости.

Хотя граф Радо универсален для порождённых подграфов, он не универсален для изометрического вложения графов — граф Радо имеет диаметр два, и любой граф большего диаметра не может быть вложен изометрически в него. Мосс[8][9] исследовал универсальные графы для изометрического вложения. Он нашёл семейство универсальных графов, по одному для каждого возможного конечного диаметра графов. Граф из этого семейства с диаметром два является графом Радо. Для метрических пространств, прямым аналогом является пространство Урысона.

Свойство универсальности графа Радо можно расширить для рёберно-раскрашенных графов. То есть графов, в которых рёбра принадлежат различным классам раскраски, но нет обычного требования рёберной раскраски, по которому каждый цвет формирует паросочетание. Для любого конечного или счётного бесконечного числа цветов χ существует единственный счётно-бесконечный граф G_χ с раскраской рёбер в χ цветов, такой, что любой частичный изоморфизм конечного графа с раскраской в χ цветов может быть расширен до полного изоморфизма. В этих обозначениях граф Радо — это G₁. Трусс[10] исследовал автоморфизм групп этого более общего семейства графов.

С теоретической точки зрения граф Радо является примером насыщенной модели.

Шела[11][12] исследовал универсальные графы с несчётным числом вершин.

• Пространство Урысона
• Случайный граф

• Peter J. Cameron. The mathematics of Paul Erdős, II. — Berlin: Springer, 1997. — Т. 14. — С. 333–351.
• Peter Cameron. The random graph. — 2013. — arXiv:1301.7544.