A matematika, azon belül a gráfelmélet területén az Erdős Pálról és Pósa Lajosról elnevezett Erdős–Pósa-tétel kimondja, hogy létezik egy függvény, hogy minden pozitív egész számra minden gráf vagy tartalmaz csúcsdiszjunkt kört, vagy méretű körlefogó csúcshalmazt, ami a gráf minden köréből tartalmaz csúcsot. Továbbá, az O jelölés szerint. A tétel miatt szokás azt mondani körökre, hogy „rendelkeznek az Erdős–Pósa-tulajdonsággal”.
A tétel állítása szerint bármely véges számra létezik olyan (legkisebb) érték, amire igaz, hogy minden, csúcsdiszjunkt kört nem tartalmazó gráf körei lefedhetők csúccsal. Ez Bollobás Béla publikálatlan eredményét általánosította, ami szerint . az általános esetre a korlátokat bizonyították. Az eredményből következik, hogy bár végtelen sok különböző gráf van, amiben nincsen diszjunkt kör, ezek mégis véges sok, egyszerűen leírható osztályba sorolhatók. A esetre teljes leírást adott. bizonyította, hogy és .
Erdős–Pósa-tulajdonság Gráfok vagy hipergráfok családja definíció szerint akkor rendelkezik az Erdős–Pósa-tulajdonsággal, ha létezik függvény, mely esetében minden (hiper-)gráfra és egészre a következők egyike igaz:
tartalmaz csúcsdiszjunkt részgráfot, melyek mindegyike izomorf egy -beli gráffal; vagy tartalmaz egy legfeljebb méretű csúcshalmazt, melyre igaz, hogy nem tartalmaz -beli gráffal izomorf részgráfot.
A definíciót gyakran a következőképpen adják meg. Ha -vel jelöljük azon csúcsdiszjunkt részgráfjainak maximális számát, melyek izomorfak egy -beli gráffal, és -vel azon csúcsok minimális számát, melyek -ből történő törlésével a maradék gráf nem tartalmaz -beli gráffal izomorf részgráfot, akkor , valamely függvényre, ami nem függ -től.
Fordítás
Jegyzetek
Kategória:Gráfelméleti tételek Kategória:Erdős Pál