Graafiteoriassa Erdős – Pose-lause ( Pal Erdős ja Lajos Pose ) väittää, että on olemassa funktio f ( k ) siten, että minkä tahansa luonnollisen luvun k kohdalla mikä tahansa graafi sisältää joko k kärjellä erotettua sykliä tai se on sykli, joka leikkaa f ( k ) -pisteiden joukon , joka leikkaa minkä tahansa syklin. Lisäksi f ( k ) = O( k log k ) O Big - merkinnällä . Tämän lauseen valossa syklien sanotaan olevan Erdős–Pose-ominaisuus .
Lause sanoo, että mille tahansa äärelliselle luvulle k on olemassa jokin (minimi)arvo f ( k ) , jolle missä tahansa graafissa, jossa ei ole k vertexirrotettua sykliä, kaikki syklit voidaan kattaa f ( k ) pisteillä. Tämä yleistää Bolobashin julkaisemattoman tuloksen , jonka mukaan f (2) = 3 . Erdős ja Poza [1] saivat rajat c 1 k log k < f ( k ) < c 2 k log k yleisessä tapauksessa. Tämä tulos viittaa siihen, että vaikka on äärettömän monta kuvaajaa ilman k irrotettua sykliä, ne kuuluvat äärelliseen määrään yksinkertaisesti kuvattavia luokkia. Tapaukselle k = 2 Lovasz [2] antoi täydellisen kuvauksen. Voss [3] osoitti, että f (3) = 6 ja 9 ≤ f (4) ≤ 12 .
Graafisten tai hypergraafien perheellä F määritelmän mukaan on Erdős–Pose-ominaisuus, jos on olemassa funktio f : N → N siten, että jollekin (hyper)kuvaajalle G ja mille tahansa kokonaisluvulle k yksi seuraavista on tosi:
Määritelmä muotoillaan usein seuraavasti. Jos merkitsemme ν ( G ) niiden G :n disjunktoitujen aligraafien pisteiden maksimimäärää, jotka ovat isomorfisia F :n graafien kanssa ja τ ( G ) niiden kärkien enimmäismäärää, joiden poistaminen G :stä jättää graafin ilman graafeja, jotka ovat isomorfisia F :n graafien kanssa. , silloin ν ( G ) ≤ f ( τ ( G )) , jollekin funktiolle f : N → N riippumaton G :stä .