Граф Радо

Граф Радо

Граф Радо — єдиний (з точністю до ізоморфізму) зліченний граф R, такий, що для будь-якого скінченного графу G і його вершини v будь-яке вкладення G − v в R як породженого підграфу можна розширити до вкладення G в R. Як наслідок, граф Радо містить усі скінченні і зліченні нескінченні графи як підграфи. Граф Радо відомий також під назвами випадковий граф і граф Ердеша — Реньї.

Історія

Граф Радо, побудований Вільгельмом Акерманом^[ru], перевідкрито кілька разів. Цей граф розглядав Річард Радо^[en][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. Таким чином, дотримуючись методу туди-сюди^[en] , G і H мають бути ізоморфними[3].

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

Стійкість до скінченних змін

Якщо граф G отримано з графу Радо видаленням будь-якого скінченного числа ребер або вершин або додаванням скінченного числа ребер, зміни не впливають на властивість розширюваності графу — для будь-якої пари множин U і V можливість знайти вершину в модифікованому графі, суміжну всім вершинам з U і не суміжну будь-якій вершині з V, залишається. Просто додамо змінені частини графу G у V і застосуємо властивість розширюваності в немодифікованому графі Радо. Таким чином, будь-яка скінченна зміна такого виду приводить до графу, ізоморфного графу Радо.

Властивість розбиттів

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

Кемерон^[en][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 [Архівовано 26 квітня 2021 у Wayback Machine.])[8][9] досліджував універсальні графи щодо ізометричного вкладення. Він знайшов сімейство універсальних графів, по одному для кожного можливого скінченного діаметра графів. Граф із цього сімейства з діаметром 2 є графом Радо. Для метричних просторів, прямим аналогом є простір Урисона.

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

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

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

Див. також

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

Коментарі

1. Ердеш і Реньї використовували властивість розширюваності графу, отриманого таким способом, для того, щоб показати, що він має багато автоморфізмів, але інших властивостей, що випливають з розширюваності, вони не розглядали. Вони також помітили, що властивість розширюваності продовжує існувати в деяких послідовностях випадкового вибору, коли різні ребра мають різну ймовірність бути включеними.

Примітки

1. Rado Richard. Universal graphs and universal functions // Acta Arith.. — 1964. — Т. 9 (25 грудня). — С. 331–340. Архівовано з джерела 26 квітня 2021. Процитовано 26 квітня 2021.
2. Paul Erdős, Alfréd Rényi. Asymmetric graphs // Acta Mathematica Academiae Scientiarum Hungaricae. — 1963. — Т. 14 (25 грудня). — С. 295–315. — DOI:10.1007/BF01895716.
3. Peter J. Cameron. European Congress of Mathematics, Vol. I (Barcelona, 2000). — Basel : Birkhäuser, 2001. — Т. 201 (25 грудня). — С. 267–274.
4. Peter J.Cameron. Oligomorphic permutation groups. — Cambridge : Cambridge University Press, 1990. — Т. 152 (25 грудня). — С. viii+160. — ISBN 0-521-38836-8.
5. 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 (25 грудня). — С. 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 (25 грудня). — С. 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 (25 грудня). — С. 505–520. — DOI:10.1007/BF01271269.
8. Moss. Existence and nonexistence of universal graphs // Polska Akademia Nauk. Fundamenta Mathematicae. — 1989. — Т. 133, вип. 1 (25 грудня). — С. 25–37.
9. Moss. Graph theory, combinatorics, and applications. Vol. 2 (Kalamazoo, MI, 1988). — New York : Wiley, 1991. — 25 грудня. — С. 923–937.
10. Truss. The group of the countable universal graph // Mathematical Proceedings of the Cambridge Philosophical Society. — 1985. — Т. 98, вип. 2 (25 грудня). — С. 213–245. — DOI:10.1017/S0305004100063428.
11. Shelah. On universal graphs without instances of CH // Annals of Pure and Applied Logic. — 1984. — Т. 26, вип. 1 (25 грудня). — С. 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 (25 грудня). — С. 69–81. — DOI:10.1007/BF02807219.

Література

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