Universell graf - Universal graph

I matematik är en universell graf en oändlig graf som innehåller alla ändliga (eller högst räknade ) diagram som en inducerad subgraf . En universell graf av denna typ konstruerades först av Richard Rado och kallas nu Rado -grafen eller slumpmässig graf. Senare arbete har fokuserat på universella diagram för en graf familj F : det vill säga en oändlig kurva som tillhör F som innehåller alla ändliga grafer i F . Till exempel är Henson -graferna universella i denna mening för de i -klickfria graferna.

En universal graf för en familj F av grafer kan också hänvisa till en medlem av en sekvens av ändliga grafer som innehåller alla grafer i F ; till exempel är varje ändligt träd en subgraf av en tillräckligt stor hyperkubgraf så att en hyperkub kan sägas vara en universell graf för träd. Det är dock inte den minsta sådan graf: det är känt att det finns en universell graf för n -vertex -träd, med endast n  hörn och O ( n  log  n ) kanter, och att detta är optimalt. En konstruktion baserad på den plana avgränsningssatsen kan användas för att visa att n -vertex plana grafer har universella grafer med O ( n ^3/2 ) kanter och att begränsade plana grafer har universella grafer med O ( n  log  n ) kanter . Det är också möjligt att konstruera universella grafer för plana grafer som har n ^{1+ o (1)} hörn. Sumners gissning säger att turneringar är universella för polytrees , i den meningen att varje turnering med 2 n  - 2 hörn innehåller varje polytree med n hörn som en subgraf.

En familj F av grafer har en universell graf med polynomstorlek, som innehåller varje n -vertexgraf som en inducerad subgraf , om och bara om den har ett adjacensmärkningsschema där hörn kan märkas med O (log  n ) -bit bitsträngar att en algoritm kan avgöra om två hörn ligger intill varandra genom att undersöka deras etiketter. För om det finns ett universellt diagram av denna typ kan hörnen för valfri graf i F märkas med identiteten hos motsvarande hörn i det universella diagrammet, och omvänt om det finns ett märkningsschema kan en universell graf konstrueras med en toppunkt för varje möjlig etikett.

I äldre matematisk terminologi användes ibland uttrycket "universalgraf" för att beteckna ett komplett diagram .

Begreppet universell graf har anpassats och använts för att lösa genomsnittliga utbetalningsspel.

Referenser

externa länkar

• Panarborialformeln , "Theorem of the Day" angående universella grafer för träd