Граф Радо

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
Граф Радо

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

История

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

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

Построение

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

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

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

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

[math]\displaystyle{ x=2^{1+\max(U\cup V)} + \sum_{u\in U} 2^u. }[/math]

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

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

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

Единственность

Граф Радо, с точностью до изоморфизма, является единственным счётным графом, обладающим свойством расширяемости. Пусть G и H — два графа с таким свойством. Пусть Gi и Hi — два изоморфных порождённых подграфа в G и H соответственно. Пусть gi и hi — первые вершины в порядке нумерации в графах G и H соответственно, не принадлежащие Gi и Hi. Тогда, применяя свойство расширяемости дважды, можно найти изоморфные порождённые подграфы Gi + 1 и Hi + 1, включающие gi и hi вместе со всеми вершинами предыдущих подграфов. Повторяя этот процесс, можно построить последовательность изоморфизмов между порожденными подграфами, которые содержат, в конечном счёте, все вершины G и H. Таким образом, следуя методу туда-сюда[англ.], G и H должны быть изоморфны[3].

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

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

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

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

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

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

Свойство оставаться изоморфным к одному из порождённых подграфов после деления имеют только три счётных бесконечных ненаправленных графа — граф Радо, полный граф и пустой граф[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χ с раскраской рёбер в χ цветов, такой, что любой частичный изоморфизм конечного графа с раскраской в χ цветов может быть расширен до полного изоморфизма. В этих обозначениях граф Радо — это G1. Трасс[10] исследовал автоморфизм групп этого более общего семейства графов.

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

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

См. также

Комментарии

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

Литература

  1. ↑ Rado Richard. Universal graphs and universal functions // Acta Arith.. — 1964. — Т. 9. — С. 331–340.
  2. ↑ 2,0 2,1 Paul Erdős, Alfréd Rényi. Asymmetric graphs // Acta Mathematica Academiae Scientiarum Hungaricae. — 1963. — Т. 14. — С. 295–315. — doi:10.1007/BF01895716.
  3. ↑ 3,0 3,1 3,2 3,3 Peter J. Cameron. European Congress of Mathematics, Vol. I (Barcelona, 2000). — Basel: Birkhäuser, 2001. — Т. 201. — С. 267–274.
  4. ↑ Peter J.Cameron. Oligomorphic permutation groups. — Cambridge: Cambridge University Press, 1990. — Т. 152. — С. viii+160. — ISBN 0-521-38836-8.
  5. ↑ 5,0 5,1 Reinhard Diestel, Imre Leader, Alex Scott, Stéphan Thomassé. Partitions and orientations of the Rado graph // Transactions of the American Mathematical Society. — 2007. — Т. 359, вып. 5. — С. 2395–2405 (electronic). — doi:10.1090/S0002-9947-06-04086-4.
  6. ↑ Anthony Bonato, Peter Cameron, Dejan Delić. Tournaments and orders with the pigeonhole property // Canadian Mathematical Bulletin. — 2000. — Т. 43, вып. 4. — С. 397–405. — doi:10.4153/CMB-2000-047-6. Архивировано 12 июня 2008 года.
  7. ↑ Maurice Pouzet, Norbert Sauer. Edge partitions of the Rado graph // Combinatorica. — 1996. — Т. 16, вып. 4. — С. 505–520. — doi:10.1007/BF01271269.
  8. ↑ Moss. Existence and nonexistence of universal graphs // Polska Akademia Nauk. Fundamenta Mathematicae. — 1989. — Т. 133, вып. 1. — С. 25–37.
  9. ↑ Moss. Graph theory, combinatorics, and applications. Vol. 2 (Kalamazoo, MI, 1988). — New York: Wiley, 1991. — С. 923–937.
  10. ↑ Truss. The group of the countable universal graph // Mathematical Proceedings of the Cambridge Philosophical Society. — 1985. — Т. 98, вып. 2. — С. 213–245. — doi:10.1017/S0305004100063428.
  11. ↑ Shelah. On universal graphs without instances of CH // Annals of Pure and Applied Logic. — 1984. — Т. 26, вып. 1. — С. 75–87. — doi:10.1016/0168-0072(84)90042-3.
  12. ↑ Shelah. Universal graphs without instances of CH: revisited // Israel Journal of Mathematics. — 1990. — Т. 70, вып. 1. — С. 69–81. — doi:10.1007/BF02807219.
  • 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.
Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Граф_Радо&oldid=13513352