Hrabě Rado

Rado graf  je jediný (až do izomorfismu ) spočetný graf R takový, že pro jakýkoli konečný graf G a jeho vrchol v lze jakékoli vložení G −  v do R jako generovaného podgrafu rozšířit na vložení G do R . Výsledkem je, že Rado graf obsahuje všechny konečné a spočetně nekonečné grafy jako podgrafy. Hrabě Rado je znám také pod jmény náhodný hrabě a hrabě Erdős-Renyi .

Historie

Rado graf byl sestrojen Wilhelmem Ackermannem a několikrát znovu objeven, zejména Richardem Rado [1] , ale o symetrických vlastnostech tohoto grafu konstruovaného jiným způsobem uvažovali dříve Pal Erdős a Alfred Rényi [2] .

Podobný objekt v metrické geometrii , takzvaný Urysohnův prostor , byl znám mnohem dříve.

Konstrukce

Rado vzal jako vrcholy grafu nezáporná celá čísla . Hrana spojuje vrcholy x a y v ( x  <  y ) , pokud je x -tá číslice binární reprezentace y nenulová.

Například množina všech sousedů vrcholu 0 se skládá z lichých vrcholů, zatímco sousedy vrcholu 1 jsou vrchol 0 (jediný vrchol, jehož číslice v binární reprezentaci 1 je nenulová) a všechny vrcholy modulo 4, které jsou shodné. do 2 a 3.

Hledání izomorfních podgrafů

Rado graf splňuje následující podmínku rozšiřitelnosti: pro jakoukoli disjunktní množinu vrcholů U a V existuje vrchol x spojený se všemi vrcholy v U a žádný ve V . Například si můžete vzít

Potom nenulové bity v binární reprezentaci x sousedí se všemi vrcholy U. X však nemá žádné nenulové bity odpovídající vrcholům V a x je dostatečně velké, aby x -tý bit libovolného prvku V byl nulový. X tedy nemá žádné sousední vrcholy ve V .

Tuto myšlenku hledání vrcholů sousedících se všemi vrcholy jedné podmnožiny a žádného jiného nelze použít ke konstrukci izomorfní kopie libovolného konečného nebo nekonečného spočítatelného grafu G , přičemž se postupně přidává jeden vrchol za druhým. Nechť G i  je podgraf G generovaný jeho prvními vrcholy i a předpokládejme, že G i již bylo nalezeno jako indukovaný graf podmnožiny vrcholu S Rado grafu. Nechť v  je další vrchol v G a nechť U  je množina sousedů v v G i . Nechť V  je množina vrcholů, které nejsou sousedy v v grafu G i . Jestliže x  je vrchol Rado grafu sousedící se všemi vrcholy U a nesousedící se všemi vrcholy V , pak S  ∪ { x } generuje podgraf izomorfní k G i  + 1 .

Indukcí, počínaje prázdným grafem, dostaneme, že jakýkoli konečný nebo nekonečný spočetný graf je generován Rado grafem.

Jedinečnost

Rado graf, až do izomorfismu, je jediný spočetný graf, který má vlastnost rozšiřitelnosti. Nechť G a H  jsou dva grafy s touto vlastností. Nechť G i a H i  jsou dva izomorfní generované podgrafy v G a H , v tomto pořadí. Nechť g i a h i  jsou první vrcholy v pořadí číslování v grafech G a H , které nepatří do G i a H i . Potom dvojím použitím vlastnosti roztažitelnosti lze najít izomorfní generované podgrafy G i +  1 a Hi  + 1 , které zahrnují g i a h i společně se všemi vrcholy předchozích podgrafů. Opakováním tohoto procesu lze sestavit sekvenci izomorfismů mezi vygenerovanými podgrafy, které nakonec obsahují všechny vrcholy G a H . Podle metody tam a zpět musí být G a H izomorfní [3] .

Aplikací stejné konstrukce dvou izomorfních podgrafů Rado grafu lze ukázat, že Radův graf je ultrahomogenní  - jakýkoli izomorfismus mezi dvěma vygenerovanými podgrafy Rado grafu lze rozšířit na automorfismus celého Radova grafu [3] . Konkrétně se jedná o automorfismus, který vezme jakýkoli uspořádaný pár sousedů s jakýmkoli jiným takovým párem, takže Rado graf je symetrický graf .

Odolnost vůči konečným změnám

Pokud graf G získáme z Rado grafu odstraněním libovolného konečného počtu hran nebo vrcholů nebo přidáním konečného počtu hran, změny neovlivní vlastnost rozšiřitelnosti grafu - pro jakoukoli dvojici množin U a V je schopnost najít v upraveném grafu vrchol, který sousedí se všemi vrcholy z U a nesousedí s žádným vrcholem V , zůstává zachována. Jednoduše přidáme upravené části grafu G do V a aplikujeme vlastnost rozšiřitelnosti v neupraveném Rado grafu. Každá konečná změna tohoto druhu tedy vede ke grafu isomorfnímu s Rado grafem.

Vlastnost oddílu

Pro jakékoli rozdělení množiny vrcholů Rado grafu na dvě podmnožiny A a B nebo rozdělení na libovolný konečný počet podmnožin bude alespoň jeden z vygenerovaných podgrafů izomorfní k samotnému Rado grafu.

Cameron [3] podal následující krátký důkaz tohoto tvrzení: Pokud žádná z vygenerovaných částí není izomorfní s Rado grafem, všechny ztrácejí vlastnost roztažitelnosti, a proto lze v každém podgrafu najít dvojici množin U i a V i , které nejsou rozšiřitelné. Pak ale sjednocení množin U i a sjednocení V i tvoří dvě množiny, které nelze v úplném grafu rozšířit, což odporuje vlastnosti roztažitelnosti Rado grafu.

Pouze tři počitatelné nekonečné neorientované grafy mají vlastnost zůstat po rozdělení izomorfní k jednomu z vygenerovaných podgrafů — Rado graf, úplný graf a prázdný graf [4] [5] . Bonato a Cameron [6] a také Distel et al [5] studovali nekonečné orientované grafy se stejnou vlastností dělení. Ukázalo se, že všechny jsou získány volbou orientace oblouků v kompletním grafu nebo Rado grafu.

Podobný výsledek platí pro okrajové oblasti – pro jakékoli rozdělení hran Rado grafu do konečného počtu množin existuje podgraf izomorfní k celému Rado grafu s použitím nejvýše dvou barev. Graf využívající pouze jednu barvu hrany však nemusí existovat [7] .

Další sestavení

V Erdős-Rényiho modelu je možné sestavit nekonečný graf náhodným nezávislým výběrem s pravděpodobností 1/2 pro každou dvojici vrcholů, zda spojit dva vrcholy hranou nebo ne. S pravděpodobností 1 má výsledný graf vlastnost rozšiřitelnosti, a proto je izomorfní s Rado grafem.

Stejná konstrukce funguje, pokud místo 1/2 vezmeme jakoukoli pevnou pravděpodobnost p , která se nerovná 0 nebo 1. Tento výsledek, dokázaný Erdősem a Renyim v roce 1963 [2] [K 1] , ospravedlňuje použití určitého členu v alternativní název " náhodný graf » (náhodný graf) pro Rado graf - pro konečné grafy aplikace Erdős-Rényiho kreslicího modelu často vede k různým grafům, zatímco spočetný nekonečný graf téměř vždy vede ke stejnému grafu. Protože je možné získat stejný Rado graf po obrácení všech voleb, je Rado graf samodoplňkový .

Jak píše Cameron [3] , Radův graf lze získat pomocí metod podobných těm pro konstrukci Paleyových grafů . Vezměte jako vrcholy všechna prvočísla , která při dělení 4 nedávají zbytek 1, a spojte dva vrcholy hranou, pokud je jedno z čísel kvadratický zbytek modulo druhé (podle kvadratické reciprocity a vyloučení prvočísel, která dejte zbytek 1 při dělení 4 , tento vztah je symetrický , takže dostaneme neorientovaný graf). Nyní pro libovolné množiny U a V podle čínské věty o zbytku čísla, která jsou kvadraticky shodná modulová prvočísla z U a nejsou srovnatelná s prvočísly od V , tvoří periodickou posloupnost, takže podle Dirichletovy věty o prvočíslech v aritmetické posloupnosti tento teoretický graf -čísel má vlastnost rozšiřitelnosti.

Variace a zobecnění

Přestože je Radův graf univerzální pro indukované podgrafy, není univerzální pro vkládání izometrických grafů – Rado graf má průměr dva a žádný graf většího průměru do něj nelze izometricky vložit. Moss [8] [9] studoval univerzální grafy pro izometrické vkládání. Našel rodinu univerzálních grafů, jeden pro každý možný konečný průměr grafu. Graf z této rodiny s průměrem dva je Rado graf. Pro metrické prostory je přímým analogem Urysohnův prostor .

Univerzálnost Rado grafu lze rozšířit na čárové grafy. Tedy grafy, ve kterých hrany patří do různých tříd zbarvení, ale není zde žádný obvyklý požadavek na zbarvení hran , aby každá barva tvořila odpovídající . Pro jakýkoli konečný nebo spočetně nekonečný počet barev χ existuje jedinečný spočetně nekonečný graf G χ s obarvením hran v barvách χ tak, že jakýkoli částečný izomorfismus konečného grafu s vybarvením v barvách χ lze rozšířit na úplný izomorfismus. V tomto zápisu je Rado graf G 1 . Trouss [10] studoval automorfismus grup této obecnější rodiny grafů.

Z teoretického hlediska je Rado graf příkladem nasyceného modelu .

Shela [11] [12] studoval univerzální grafy s nespočetným počtem vrcholů.

Viz také

Komentáře

  1. ↑ Erdős a Renyi použili vlastnost rozšiřitelnosti takto získaného grafu, aby ukázali, že má mnoho automorfismů, ale nezvažovali další vlastnosti, které z rozšiřitelnosti vyplývají. Také si všimli, že vlastnost rozšiřitelnosti nadále existuje v některých sekvencích náhodného výběru, když různé hrany mají různé pravděpodobnosti, že budou zahrnuty.

Literatura

  1. ↑ Rado Richard. Univerzální grafy a univerzální funkce // Acta Arith .. - 1964. - T. 9 . — S. 331–340 .
  2. ↑ 1 2 Paul Erdős, Alfred Rényi. Asymetrické grafy // Acta Mathematica Academiae Scientiarum Hungaricae. - 1963. - T. 14 . — S. 295–315 . - doi : 10.1007/BF01895716 .
  3. ↑ 1 2 3 4 Peter J. Cameron. Evropský matematický kongres, sv. Já (Barcelona, ​​2000). - Basilej: Birkhäuser, 2001. - T. 201 . — S. 267–274 .
  4. ↑ Peter J. Cameron. Oligomorfní permutační grupy. - Cambridge: Cambridge University Press, 1990. - V. 152 . - S. viii + 160 . — ISBN 0-521-38836-8 .
  5. ↑ 1 2 Reinhard Diestel, Imre Leader, Alex Scott, Stéphan Thomassé. Rozdělení a orientace grafu Rado // Transactions of the American Mathematical Society. - 2007. - T. 359 , č.p. 5 . — S. 2395–2405 (elektronické) . - doi : 10.1090/S0002-9947-06-04086-4 .
  6. ↑ Anthony Bonato, Peter Cameron, Dejan Delic. Turnaje a objednávky s majetkem rozškatulkovat // Canadian Mathematical Bulletin. - 2000. - T. 43 , no. 4 . — S. 397–405 . - doi : 10.4153/CMB-2000-047-6 . Archivováno z originálu 12. června 2008.
  7. ↑ Maurice Pouzet, Norbert Sauer. Okrajové oddíly grafu Rado  // Combinatorica. - 1996. - T. 16 , no. 4 . — S. 505–520 . - doi : 10.1007/BF01271269 .
  8. ↑ Mech. Existence a nonexistence univerzálních grafů // Polska Akademia Nauk. Fundamenta Mathematicae. - 1989. - T. 133 , čís. 1 . — S. 25–37 .
  9. ↑ Mech. Teorie grafů, kombinatoria a aplikace. sv. 2 (Kalamazoo, MI, 1988). - New York: Wiley, 1991. - S. 923-937 .
  10. ↑ Příhradový nosník. Skupina počitatelného univerzálního grafu // Mathematical Proceedings of the Cambridge Philosophical Society. - 1985. - T. 98 , čís. 2 . — S. 213–245 . - doi : 10.1017/S0305004100063428 .
  11. ↑ Šela. Na univerzálních grafech bez instancí CH // Annals of Pure and Applied Logic. - 1984. - T. 26 , no. 1 . — s. 75–87 . - doi : 10.1016/0168-0072(84)90042-3 .
  12. ↑ Šela. Univerzální grafy bez instancí CH: revisited // Israel Journal of Mathematics. - 1990. - T. 70 , čís. 1 . — s. 69–81 . - doi : 10.1007/BF02807219 .