Граф Радо — единственный (с точностью до изоморфизма ) счётный граф 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 . Например, можно взять

${\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 должны быть изоморфны .

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

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

Если граф 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 : .