Граф Радо

Граф Радо, побудований Вільгельмом Акерманом, перевідкрито кілька разів. Цей граф розглядав Річард Радо[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], а також Дістель та інші досліджували нескінченні орієнтовані графи з цією властивістю поділу. Виявилося, що всі вони отримуються вибором орієнтації дуг у повному графі або графі Радо.

Схожий результат істинний для розбиття ребер — для будь-якого розбиття ребер графу Радо на скінченне число множин, існує підграф, ізоморфний усьому графу Радо, що використовує максимум два кольори. Однак графу, що використовує тільки один колір ребер, може й не існувати[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, утворюють періодичну послідовність, так що згідно зтеоремою Діріхле про прості числа в арифметичній прогресії цей теоретико-числовий граф має властивість розширюваності.

Хоча граф Радо універсальний для породжених підграфів, він не універсальний для ізометричного вкладення графів — граф Радо має діаметр 2, і будь-який граф більшого діаметра не можна вкласти ізометрично в нього. Мосс (Lawrence S. Moss)[8][9] досліджував універсальні графи щодо ізометричного вкладення. Він знайшов сімейство універсальних графів, по одному для кожного можливого скінченного діаметра графів. Граф із цього сімейства з діаметром 2 є графом Радо. Для метричних просторів, прямим аналогом є простір Урисона.

Властивість універсальності графу Радо можна розширити для реберно-розфарбованих графів. Тобто графів, у яких ребра належать різним класам розфарбування, але немає звичайної вимоги реберного розфарбування, за якою кожен колір формує парування. Для будь-якого скінченного або зліченного нескінченного числа кольорів χ існує єдиний зліченно нескінченний граф G_χ з розфарбуванням ребер у χ кольорів, такий, що будь-який частковий ізоморфізм скінченного графу з розфарбуванням у χ кольорів можна розширити до повного ізоморфізму. У цих позначеннях граф Радо — це G₁. Трасс (John K. Truss)[10] досліджував автоморфізм груп цього загальнішого сімейства графів.

З теоретичної точки зору граф Радо є прикладом насиченої моделі.

Шелах[11][12] досліджував універсальні графи з незліченною кількістю вершин.

• Урисонів простір
• Випадковий граф

• Peter J. Cameron. The mathematics of Paul Erdős, II. — Berlin : Springer, 1997. — Т. 14 (7 лютого). — С. 333–351.
• Peter Cameron. The random graph. — 2013. — 7 лютого. — arXiv:1301.7544. Процитовано 2013-06-13.