Rado graf

V matematice , a přesněji v teorii grafů , je Radův graf , nazývaný také Erdős - Rényiho graf nebo náhodný graf , počítatelným nekonečným grafem, který na počátku 60. let studovali Richard Rado , Paul Erdős a Alfréd Rényi a který se vyznačuje vlastností extenze , což znamená, že obsahuje (jako podgraf ) jakýkoli konečný nebo spočetný graf.

Existuje několik jeho konstrukcí; je to zejména ( téměř jistě ) náhodný graf získaný náhodným výběrem pro každou dvojici vrcholů bez ohledu na to, zda jsou spojeny nebo ne.

Historický

Graf Rado byl sestrojen Wilhelmem Ackermannem v roce 1937 z dědičně konečných množin  ( přesněji ) (přesněji popsal směrovaný graf, ze kterého je získán graf Rado odstraněním orientace). Ve své práci na náhodné grafy , Paul Erdős a Alfréd Rényi konstruována jako nekonečné náhodného grafu, a ukázal, že má nekonečný počet automorphisms argumentem, která by také umožnila prokázat jeho jedinečnost. Richard Rado jej znovuobjevil jako univerzální graf a dal deterministickou konstrukci v podstatě ekvivalentní konstrukci Ackermanna.

Stavby

Binární zápis

Ackermann a Rado dali explicitní konstrukci pomocí predikátu BIT  (en) . Identifikace vrcholy grafu a přírodních celých čísel 0, 1, 2, ..., hrana spojuje vrcholy x a y (s x  <  y ) v případě, a to pouze v případě, že bitová hodnost x o binární reprezentace z y je rovno 1 Například existuje spojnice mezi x = 2 a y = 4 = 100 2 , ale ne mezi x = 1 a y .

Náhodné grafy

Radův graf se objeví téměř jistě, když použijeme model náhodného grafu vyvinutý Erdősem a Rényem na spočetnou sadu vrcholů. Přesněji řečeno, nezávisle pro každou dvojici vrcholů s pravděpodobností p (0 < p <1), zda jsou tyto vrcholy spojeny hranou, je výsledný graf téměř jistě (tj. S pravděpodobností 1) izomorfní s grafem z Rado; Je to výsledek, který odůvodňuje článek definovaný ve výrazu „  v náhodném graf“, který se někdy označuje.

Graf izomorfní ke grafu doplňujícímu Rado graf lze získat (téměř jistě) stejnou konstrukcí výběrem hran s pravděpodobností 1– p , což ukazuje, že Rado graf je komplementární .

Ostatní stavby

Vlastnost extension charakterizuje Rado graf a umožňuje ukázat, že mnoho konstrukcí je pro něj izomorfních.

V Ackermannově konstrukci v roce 1937 jsou vrcholy grafu Rado dědičně konečné množiny (tj. Konečné množiny, jejichž prvky jsou samy dědičně konečné) a hrana spojuje dva vrcholy, když je jeden z nich součástí druhého.

Další konstrukce grafu Rado je analogická konstrukci grafů Paley . Vrcholy jsou prvočísla tvaru 4 n + 1 a hrana je spojuje, pokud je jedním z nich kvadratický zbytek modulo druhého (tento vztah je symetrický podle kvadratického zákona vzájemnosti ).

Mohou být také konstruovány jako průsečík grafu jednoho blokového systému  (en) nekonečno, kde každý blok je nekonečná (spočetná).

Vlastnosti

Vlastnost rozšíření

Radův graf splňuje následující vlastnost rozšíření : pro jakoukoli dvojici množin disjunktních konečných vrcholů U a V existuje vrchol x, který nepatří ani U ani V , a je spojen se všemi vrcholy U , ale žádný z těch V  ; tato vlastnost charakterizuje tento graf, jak je uvedeno níže .

Definice grafu binární reprezentací umožňuje konstruktivní demonstraci, pózováním

 :

x je větší než u všech stavebních prvků U a V , přiléhající na všechny prvky U , a protože U a V jsou disjunktní, x je přilehlé k jakékoli části V .

Konstrukce jako náhodný graf dává každému vrcholu, který není v U nebo V, pravděpodobnost p | U | (1- p ) | V | uspokojit vlastnost rozšíření, nezávisle na ostatních vrcholech; protože takových vrcholů je nekonečno, téměř jistě existuje jeden, který tuto vlastnost uspokojí.

Podgrafy

Pro každý konečný nebo nekonečný spočetnou grafu G , rozšíření vlastnost postavit sub-graf grafu Rado izomorfní s G . Důkaz se provádí indukcí na vrcholech G (předpokládá se, že jsou indexována celými čísly): za předpokladu, že pro první n vrcholy je vytvořen izomorfismus , přidáme nový vrchol výběrem z grafu Rado vrchol, který má přesně stejné odkazy s vrcholy již postavené odpovídající vrcholy v G . Z tohoto důvodu se někdy říká, že Radův graf je univerzální graf , ale ve skutečnosti je to slabší pojem než univerzální problém , definovaný teorií kategorií .

Jedinečnost

Radův graf je až do izomorfismu jediným počítatelným grafem, který má vlastnost rozšíření. Ve skutečnosti, pokud G a H jsou dva grafy, které mají tuto vlastnost, každý z těchto dvou je izomorfní s podgrafem druhého; při specifikaci konstrukce těchto podgrafů je možné získat indukcí izomorfismus mezi G a H metodou tam a zpět (analogicky k důkazu Cantor-Bernsteinovy ​​věty ).

Symetrie

Počínaje dvěma konečnými a izomorfními podgrafy Rado grafu umožňuje předchozí konstrukce rozšířit tento izomorfismus na automorfismus celého grafu; říkáme, že Rado graf je ultrahomogenní . Zejména existuje automorfismus, který posílá libovolné dvě hrany jedna na druhou, a Radův graf je tedy symetrický graf . Skupina automorfismů Rado grafu je jednoduchá skupina se silou kontinua .

Noty

Jakékoli konečné rozdělení vrcholů grafu Rado indukuje alespoň jeden podgraf izomorfní k celému grafu. Cameron 2001 o tom poskytuje krátký důkaz, získaný slepením podmnožin každého indukovaného podgrafu, který by nevěřil vlastnost rozšíření. Tuto vlastnost mají pouze tři spočítatelné neorientované grafy: Radoův graf, úplný graf a prázdný graf. Bonato, Cameron a Delić 2000 a Diestel et al. 2007 ukázaly, že pouze orientované grafy se stejnou vlastností jsou získány z těchto tří grafů výběrem vhodné orientace hran.

Pokud nás zajímají oddíly hran, podobný výsledek, ale slabší, ukazuje, že existuje podgraf izomorfní k celému Rado grafu výběrem hran mezi dvěma prvky oddílu, ale že není vždy možné vzít hrany v jednom prvku.

Vztah s teorií modelů

Ronald Fagin prokázal, že pokud výrok týkající se grafů (přesněji výrok rovnostářské teorie prvního řádu obsahující vztah sousednosti , který vyjadřuje, že hrana spojuje vrcholy a a b ), platí pro Radův graf, platí téměř pro všechny konečné grafy, to znamená, že podíl grafů s n vrcholy, pro které platí tvrzení, má sklon k 1, když n má sklon k nekonečnu.

Vlastnost rozšíření lze vyjádřit nekonečnou řadou příkazů prvního řádu , která ji prosazuje pro všechny sady vrcholů U a V, které mají prvky i a j . Například lze psát jako

Haim Gaifman  (in) demonstroval, že množina a tvrzení potvrzující, že vztah adjacence je symetrický a antireflexní, jsou axiomy úplné teorie , jejíž Rado graf je jedinečný spočetný model (tento poslední výsledek vyplývá z jedinečnosti grafů mít vlastnost rozšíření a umožňuje prokázat úplnost díky kritériu Łoś - Vaught ).

Zobecnění

Univerzální vlastnost Rado grafu nezobecňuje například na izometrické vložení, tj. Na izomorfismy zachovávající vzdálenost  : Rado graf má průměr dva, a proto se do něj nemůže izometricky ponořit žádný graf většího průměru. Moss sestrojil pro každou hodnotu n graf obsahující izometricky všechny konečné grafy průměru n , čímž získal úplný nekonečný graf pro n = 1 a graf Rado pro n = 2.

Saharon Shelah studoval existenci nespočetných univerzálních grafů a získal dostatečné podmínky existence na jejich kardinálovi .

Poznámky a odkazy

(fr) Tento článek je částečně nebo zcela převzat z článku Wikipedie v angličtině s názvem „  Rado graph  “ ( viz seznam autorů ) .

Poznámky

  1. V zásadě ekvivalentní konstrukce, ale uvedená v určitých termínech, představuje Větu 2 Camerona 1997 .

Reference

  1. Ackermann 1937  ; Rado 1964 .
  2. Viz Cameron 1997 , výsledek 1.
  3. Cameron 1997 , Proposition 5.
  4. Cameron 1997 , Věta 2.
  5. Cameron 1997 .
  6. Horsley, Pike a Sanaei 2011 .
  7. Cameron 1997 , Proposition 6.
  8. Delahaye 2018
  9. Cameron 2001 .
  10. Cameron 1997 , oddíl 1.8: skupina automorfismů.
  11. Cameron 1990  ; Diestel a kol. 2007 .
  12. POUZET a Sauer 1996 .
  13. Fagin 1976 .
  14. Spencer 2001 , oddíl 1.3, „Příkazy rozšíření a zakořeněné grafy“, s. 17-18 .
  15. Gaifman 1964 .
  16. Gaifman 1964  ; Marker 2002 , Theorem 2.4.2, str. 50.
  17. Marker 2002 , Theorem 2.2.6, str. 42.
  18. Moss 1989 .
  19. Shelah 1984 .

Bibliografie

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">