Граф Радо
Граф Радо — єдиний (з точністю до ізоморфізму) зліченний граф 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. Наприклад, можна взяти
Тоді ненульові біти в двійковому поданні 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. Таким чином, дотримуючись методу туди-сюди[en] , G і H мають бути ізоморфними[3].
Застосовуючи таку ж побудову двох ізоморфних підграфів графу Радо, можна показати, що граф Радо ультраоднорідний — будь-який ізоморфізм між двома породженими підграфами графу Радо розширюваний до автоморфізму всього графу Радо[3]. Зокрема, існує автоморфізм, що переводить будь-яку впорядковану пару суміжних у будь-яку іншу таку пару, так що граф Радо є симетричним графом.
Стійкість до скінченних змін[ред. | ред. код]
Якщо граф G отримано з графу Радо видаленням будь-якого скінченного числа ребер або вершин або додаванням скінченного числа ребер, зміни не впливають на властивість розширюваності графу — для будь-якої пари множин U і V можливість знайти вершину в модифікованому графі, суміжну всім вершинам з U і не суміжну будь-якій вершині з V, залишається. Просто додамо змінені частини графу G у V і застосуємо властивість розширюваності в немодифікованому графі Радо. Таким чином, будь-яка скінченна зміна такого виду приводить до графу, ізоморфного графу Радо.
Властивість розбиттів[ред. | ред. код]
Для будь-якого розбиття множини вершин графу Радо на дві підмножини A і B, або поділу на будь-яке скінченне число підмножин, щонайменше один з породжених підграфів буде ізоморфним самому графу Радо.
Кемерон[en][3] навів таке коротке доведення цього твердження: якщо жодна з породжених частин не ізоморфна графу Радо, вони всі втрачають властивість розширюваності, а отже, в кожному підграфі можна знайти пару множин Ui і Vi, що не піддаються розширенню. Але тоді об'єднання множин Ui і об'єднання Vi утворюють дві множини, які не можна розширити в повному графі, що суперечить властивості розширюваності графу Радо.
Властивість залишатися ізоморфним до одного з породжених підграфів після поділу мають тільки три зліченних нескінченних ненапрямлених графи — граф Радо, повний граф і порожній граф[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χ з розфарбуванням ребер у χ кольорів, такий, що будь-який частковий ізоморфізм скінченного графу з розфарбуванням у χ кольорів можна розширити до повного ізоморфізму. У цих позначеннях граф Радо — це G1. Трасс (John K. Truss)[10] досліджував автоморфізм груп цього загальнішого сімейства графів.
З теоретичної точки зору граф Радо є прикладом насиченої моделі[en].
Шелах[11][12] досліджував універсальні графи з незліченною кількістю вершин.
Див. також[ред. | ред. код]
Коментарі[ред. | ред. код]
- ↑ Ердеш і Реньї використовували властивість розширюваності графу, отриманого таким способом, для того, щоб показати, що він має багато автоморфізмів, але інших властивостей, що випливають з розширюваності, вони не розглядали. Вони також помітили, що властивість розширюваності продовжує існувати в деяких послідовностях випадкового вибору, коли різні ребра мають різну ймовірність бути включеними.
Примітки[ред. | ред. код]
- ↑ Rado Richard. Universal graphs and universal functions // Acta Arith.. — 1964. — Т. 9 (21 квітня). — С. 331–340. Архівовано з джерела 26 квітня 2021. Процитовано 26 квітня 2021.
- ↑ а б Paul Erdős, Alfréd Rényi. Asymmetric graphs // Acta Mathematica Academiae Scientiarum Hungaricae. — 1963. — Т. 14 (21 квітня). — С. 295–315. — DOI:.
- ↑ а б в г Peter J. Cameron. European Congress of Mathematics, Vol. I (Barcelona, 2000). — Basel : Birkhäuser, 2001. — Т. 201 (21 квітня). — С. 267–274.
- ↑ Peter J.Cameron. Oligomorphic permutation groups. — Cambridge : Cambridge University Press, 1990. — Т. 152 (21 квітня). — С. viii+160. — ISBN 0-521-38836-8.
- ↑ 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 (21 квітня). — С. 2395–2405 (electronic). — DOI:.
- ↑ Anthony Bonato, Peter Cameron, Dejan Delić. Tournaments and orders with the pigeonhole property // Canadian Mathematical Bulletin. — 2000. — Т. 43, вип. 4 (21 квітня). — С. 397–405. — DOI:. Архівовано з джерела 12 червня 2008.
- ↑ Maurice Pouzet, Norbert Sauer. Edge partitions of the Rado graph // Combinatorica. — 1996. — Т. 16, вип. 4 (21 квітня). — С. 505–520. — DOI:.
- ↑ Moss. Existence and nonexistence of universal graphs // Polska Akademia Nauk. Fundamenta Mathematicae. — 1989. — Т. 133, вип. 1 (21 квітня). — С. 25–37.
- ↑ Moss. Graph theory, combinatorics, and applications. Vol. 2 (Kalamazoo, MI, 1988). — New York : Wiley, 1991. — 21 квітня. — С. 923–937.
- ↑ Truss. The group of the countable universal graph // Mathematical Proceedings of the Cambridge Philosophical Society. — 1985. — Т. 98, вип. 2 (21 квітня). — С. 213–245. — DOI:.
- ↑ Shelah. On universal graphs without instances of CH // Annals of Pure and Applied Logic. — 1984. — Т. 26, вип. 1 (21 квітня). — С. 75–87. — DOI:.
- ↑ Shelah. Universal graphs without instances of CH: revisited // Israel Journal of Mathematics. — 1990. — Т. 70, вип. 1 (21 квітня). — С. 69–81. — DOI:.