Граф Радо

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

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

Схожий результат істинний для розбиття ребер — для будь-якого розбиття ребер графу Радо на скінченне число множин, існує підграф, ізоморфний усьому графу Радо, що використовує максимум два кольори. Однак графу, що використовує тільки один колір ребер, може й не існувати[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χ з розфарбуванням ребер у χ кольорів, такий, що будь-який частковий ізоморфізм скінченного графу з розфарбуванням у χ кольорів можна розширити до повного ізоморфізму. У цих позначеннях граф Радо — це G1. Трасс (John K. Truss)[10] досліджував автоморфізм груп цього загальнішого сімейства графів.

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

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

Див. також

Коментарі

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

Примітки

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

Література

  • 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.