Erdős-Hajnals hypotese

Uløste problemer i matematik : Er det rigtigt, at grafer med en fast forbudt induceret undergraf nødvendigvis har store kliker eller store uafhængige sæt?

Erdős-Hajnal formodningen siger, at familier af grafer defineret af forbudte inducerede undergrafer har enten store kliker eller store uafhængige sæt . Mere præcist, for en vilkårlig urettet graf , lad være en familie af grafer, der ikke indeholder som en genereret undergraf . Så er der ifølge hypotesen en konstant sådan, at grafer med toppunkter i enten har en klike eller et uafhængigt sæt størrelse .

Et tilsvarende udsagn af den oprindelige formodning: for enhver graf indeholder grafer, der ikke indeholder vilkårligt store perfekte genererede undergrafer .

Grafer uden store kliker eller uafhængige sæt

Til sammenligning, for tilfældige grafer i Erdős-Rényi-modellen med kantsandsynlighed 1/2, er både den største klike og den største uafhængige mængde meget mindre - deres størrelse er proportional med logaritmen af ​​, og vokser ikke polynomielt. Ramseys teorem beviser, at ingen graf har både størrelsen af ​​den største klike og størrelsen af ​​den største uafhængige mængde mindre end logaritmisk [1] [2] . Ramsey-sætningen indebærer også et særligt tilfælde af Erdős-Hajnal-hypotesen, når selve grafen er en klike eller et uafhængigt sæt [1] .

Delvise resultater

Formodningen tilhører Pal Erdős og András Hajnal , som beviste det for tilfældet, hvornår er en kograf . De viste også for en vilkårlig graf , at størrelsen af ​​den største klike eller uafhængige sæt vokser superlogaritmisk. Mere præcist, for enhver graf er der en konstant sådan, at ikke -vertex- grafer har kliker eller uafhængige sæt, der indeholder mindst toppunkter [1] . Graferne , for hvilke formodningen er sand, inkluderer også en sti [1] [3] med fire hjørner, et tyrehoved [1] [4] med fem spidser og enhver graf, der kan opnås fra disse grafer og kografer ved hjælp af en modulær nedbrydning [1] [2] . Fra 2021 er hypotesen dog ikke blevet fuldt bevist og forbliver et åbent problem [5] .

En tidligere formulering af formodningen, også på grund af Erdős og Hajnal, vedrører det særlige tilfælde, hvor grafen er en 5-vertex grafcyklus [3] . Ifølge fortrykket fra 2021 er formodningen sand i dette tilfælde [5] . Ikke-indeholdende grafer inkluderer perfekte grafer , som nødvendigvis har enten en klike eller et uafhængigt sæt med en størrelse, der er proportional med kvadratroden af ​​deres antal hjørner. Omvendt er enhver klike eller uafhængigt sæt i sig selv en perfekt graf. Af denne grund er en bekvem og symmetrisk formulering af Erdős-Hajnal-formodningen påstanden om, at for enhver graf , indeholder ikke-indeholdende grafer nødvendigvis en genereret perfekt subgraf af polynomisk størrelse [1] [6] .

Noter

  1. ↑ 1 2 3 4 5 6 7 Erdős, Hajnal, 1989 , s. 37-52.
  2. ↑ 1 2 Alon, Pach, Solymosi, 2001 , s. 155-170.
  3. ↑ 1 2 Gyárfás, 1997 , s. 93-98.
  4. ↑ Chudnovsky, Safra, 2008 , s. 1301-1310.
  5. ↑ 12 Steve Nadis . Nyt bevis afslører, at grafer uden femkanter er fundamentalt anderledes . Quanta (26. april 2021). Hentet 26. april 2021. Arkiveret fra originalen 26. april 2021.
  6. ↑ Chudnovsky, 2014 , s. 178-179.

Litteratur

Links