Burr–Erdős gissning

Inom matematiken var Burr -Erdős-förmodan ett problem angående Ramsey-antalet glesa grafer . Gissningarna är uppkallade efter Stefan Burr och Paul Erdős , och är en av många gissningar som är uppkallade efter Erdős ; det står att Ramsey-antalet grafer i en gles familj av grafer bör växa linjärt i antalet hörn i grafen.

Gissningen bevisades av Choongbum Lee. Så det är nu ett teorem.

Definitioner

Om G är en oriktad graf , så är degenerationen av G det minsta antalet p så att varje subgraf av G innehåller en vertex av grad p eller mindre. En graf med degeneration p kallas p -degenererad. På motsvarande sätt är en p -degenererad graf en graf som kan reduceras till den tomma grafen genom att upprepade gånger ta bort en vertex av grad p eller mindre.

Det följer av Ramseys teorem att det för varje graf G finns ett minsta heltal Ramsey -talet för G , så att varje komplett graf på åtminstone hörn vars kanter är färgade röda eller blå innehåller en monokromatisk kopia av G . Till exempel är Ramsey-talet för en triangel 6: oavsett hur kanterna på en komplett graf på sex hörn är färgade röda eller blå, finns det alltid antingen en röd triangel eller en blå triangel.

Gissningen

1973 gjorde Stefan Burr och Paul Erdős följande gissningar:

För varje heltal p finns det en konstant cp - så att varje p -degenererad graf G på n hörn har Ramsey tal som mest c p n .

Det vill säga, om en n -vertexgraf G är p -degenererad, så borde en monokromatisk kopia av G finnas i varje tvåkantsfärgad komplett graf på c p n hörn.

Kända resultat

Innan den fullständiga gissningen bevisades, avgjordes den först i några speciella fall. Det bevisades för grafer med begränsade grader av Chvátal et al. (1983) ; deras bevis ledde till ett mycket högt värde på c p , och förbättringar av denna konstant gjordes av Eaton (1998) och Graham, Rödl & Rucínski (2000) . Mer generellt är gissningarna känd för att vara sanna för p -arrangerbara grafer, vilket inkluderar grafer med begränsad maximal grad, plana grafer och grafer som inte innehåller en underavdelning av K p . Det är också känt för uppdelade grafer, grafer där inga två närliggande hörn har en grad som är större än två.

För godtyckliga grafer är Ramsey-talet känt för att begränsas av en funktion som endast växer något superlinjärt. Specifikt Fox & Sudakov (2009) att det finns en konstant cp så , att för varje p -degenererad n -vertexgraf G

Anteckningar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Burr–Erdős_conjecture&oldid=1126226912 "