Граф Радо

Граф Радо

Граф Радо — единственный (с точностью до изоморфизма) счётный граф R, такой, что для любого конечного графа G и его вершины v любое вложение G − v в R в качестве порождённого подграфа может быть расширено до вложения G в R. Как результат граф Радо содержит все конечные и счётные бесконечные графы в качестве подграфов. Граф Радо известен также под именами случайный граф и граф Эрдёша — Реньи.

История

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

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

Построение

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

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

Нахождение изоморфных подграфов

Граф Радо удовлетворяет следующему условию расширяемости: для любых непересекающихся наборов вершин 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.

Эту идею нахождения вершин, смежных со всеми вершинами одного подмножества и ни одной вершиной другого можно использовать для построения изоморфной копии любого конечного или бесконечного счётного графа 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 должны быть изоморфны.

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

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

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

Свойство разбиений

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

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

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

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

Другие построения

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

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

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

Вариации и обобщения

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

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

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

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

См. также

• Графон — модель случайного графа, обобщение модели Эрдеша — Реньи.
• Пространство Урысона
• Случайный граф

Литература

• 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.