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 .
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] .
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] .