Sumners hypotese

Uløste problemer i matematik : Indeholder nogen vertex-turnering et rettet vertex-træ som en undergraf ?

(2n-2)

n

David Sumner (en grafteoretiker ved University of South Carolina ) formodede i 1971 , at turneringer er universelle grafer for polytrees (directed trees). Mere præcist siger Sumners formodning (eller Sumners universelle turneringsformodning ) at enhver orientering af ethvert vertextræ er en undergraf af enhver toppunktsturnering [1] . Hypotesen forbliver ubevist. Kuhn, Mycroft og Ostus [2] taler om formodningen som "et af de bedst kendte turneringsproblemer." $n$ $(2n-2)$

Eksempler

Lad et orienteret træ være en stjerne , hvor alle kanter er orienteret fra midten til bladene. Så er det umuligt at indlejre sig i en turnering dannet ud fra hjørnerne af en regulær -gon ved at rette alle kanter med uret rundt om polygonen. For denne turnering er enhver indgang halv grad og enhver udgang halv grad , mens den centrale top har en større udgang halv grad, . [3] . Således, hvis Sumners formodning er korrekt, giver det den bedst mulige størrelse af en universel graf for rettede træer. $P$ $K_{1,n-1}$ $P$ $(2n-3)$ $n-2$ $P$ $n-1$

Men i enhver turnering med peaks er den gennemsnitlige halvgrad for udgang , og den maksimale halvgrad for udgang er et heltal, der er større end eller lig med gennemsnitsværdien. Der er således et toppunkt med udgang semi-grad , som kan bruges som midtpunkt for kopien . $2n-2$ $n-{\frac {3}{2))$ $\left\lceil n-{\frac {3}{2}}\right\rceil =n-1$ $P$

Delvise resultater

Følgende delresultater er kendte.

Hypotesen er sand for alle tilstrækkeligt store værdier [4] . $n$
Der er en funktion med asymptotisk vækstrate med den egenskab, at ethvert rettet vertex-træ kan indlejres i en undergraf i enhver vertex-turnering. Også og mere eksplicit . [5] $f(n)$ $f(n)=2n+o(n)$ $n$ $f(n)$ $f(n)\leq 3n-3$
Der er en funktion sådan, at vertex-turneringer er universelle for rettede træer med blade [6] [7] [8] . $g(k)$ $n+g(k)$ $k$
Der er en funktion sådan, at ethvert rettet træ med toppunkter med maksimal grad ikke større end , danner en undergraf i enhver turnering med toppunkter. Hvis er en fast konstant, er hastigheden af asymptotisk vækst [ 2] . $h(n,\Delta )$ $n$ $\Delta$ $h(n,\Delta )$ $\Delta$ $h(n,\Delta )$ $n+o(n)$
Enhver "næsten almindelig" turnering med toppunkter indeholder ethvert rettet træ med toppunkter [9] . $2n-2$ $n$
Enhver rettet larve med hjørner og diameter på ikke over fire kan indlejres som en undergraf i enhver turnering med hjørner [9] . $n$ $(2n-2)$
Enhver turnering med knudepunkter indeholder som en undergraf enhver rettet rodgraf med knudepunkter [10] . $(2n-2)$ $n$

Relaterede hypoteser

Rosenfeld [11] formodede, at enhver dirigeret sti med knudepunkter (for ) kan indlejres som en undergraf i enhver turnering med knudepunkter [9] . Efter delvise resultater opnået af Thomason [12 ] beviste Ave og Tomassi [7] formodningen . $n$ $n\geqslant 8$ $n$

Ave og Tomassi [13] fremførte til gengæld Sumners styrkede formodning om, at enhver turnering med hjørner som en undergraf indeholder ethvert rettet træ med højst blade. $n+k-1$ $k$

Burr [14] formodede, at hvis en graf kræver mere end én farve for at farve grafen , så indeholder enhver orientering af grafen enhver orientering af vertextræet. Fordi komplette grafer kræver en anden farve for hvert toppunkt, følger Sumners formodning umiddelbart af Burrs formodning [15] . Som Burr viste, er orienteringer af grafer, hvis kromatiske tal vokser kvadratisk fra , universelle for rettede træer. $G$ $2n-2$ $G$ $G$ $n$ $n$

Noter

↑ ( Kühn, Mycroft, Osthus 2011a ). Det tidligste publicerede citat er fra Daniela Kühn et al. af Reid og Wormald (( Reid, Wormald 1983 ), ( Wormald 1983 )). Wormald citerer hypotesen som værende blevet hørt i en privat samtale med Sumner.
↑ 1 2 Kühn, Mycroft, Osthus, 2011a .
↑ Dette eksempel er taget fra en artikel af Kühn, Mycroft og Osthus (( Kühn, Mycroft, Osthus 2011a )).
↑ Kühn, Mycroft, Osthus, 2011b .
↑ Kühn, Mycroft, Osthus, 2011a ; El Sahili, 2004 . Svagere og tidligere grænser for funktionen kan findes i Chung, 1981 , Wormald, 1983 , Häggkvist, Thomason, 1991 , Havet, Thomassé, 2000b , Havet, 2002 . $f(n)$
↑ Häggkvist, Thomason, 1991 .
↑ 1 2 Havet, Thomasse, 2000a .
↑ Havet, 2002 .
↑ 1 2 3 Reid, Wormald, 1983 .
↑ Havet, Thomasse, 2000b .
↑ Rosenfeld, 1972 .
↑ Thomason, 1986 .
↑ I Aves artikel (( Havet 2002 )), men Ave tilskriver det i denne artikel Tomassi.
↑ Burr, 1980 .
↑ Dette er en redigeret version af Burrs formodning fra Wormalds papir (( Wormald 1983 )).

Litteratur