Erdős–Pósa-tétel

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(k) függvény, hogy minden k pozitív egész számra minden gráf vagy tartalmaz k csúcsdiszjunkt kört, vagy f(k) méretű körlefogó csúcshalmazt, ami a gráf minden köréből tartalmaz csúcsot. Továbbá, f(k) = O(k log k) 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 k számra létezik olyan (legkisebb) f(k) érték, amire igaz, hogy minden, k csúcsdiszjunkt kört nem tartalmazó gráf körei lefedhetők f(k) csúccsal. Ez Bollobás Béla publikálatlan eredményét általánosította, ami szerint f(2) = 3. (Erdős & Pósa 1965) az általános esetre a c₁k log k < f(k) < c₂k log k 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 k diszjunkt kör, ezek mégis véges sok, egyszerűen leírható osztályba sorolhatók. A k = 2 esetre (Lovász 1965) teljes leírást adott. (Voss 1969) bizonyította, hogy f(3) = 6 és 9 ≤ f(4) ≤ 12.

Erdős–Pósa-tulajdonság

Gráfok vagy hipergráfok F családja definíció szerint akkor rendelkezik az Erdős–Pósa-tulajdonsággal, ha létezik f: N → N függvény, mely esetében minden G (hiper-)gráfra és k egészre a következők egyike igaz:

• G tartalmaz k csúcsdiszjunkt részgráfot, melyek mindegyike izomorf egy F-beli gráffal; vagy
• G tartalmaz egy legfeljebb f(k) méretű C csúcshalmazt, melyre igaz, hogy G − C nem tartalmaz F-beli gráffal izomorf részgráfot.

A definíciót gyakran a következőképpen adják meg. Ha ν(G)-vel jelöljük G azon csúcsdiszjunkt részgráfjainak maximális számát, melyek izomorfak egy F-beli gráffal, és τ(G)-vel azon csúcsok minimális számát, melyek G-ből történő törlésével a maradék gráf nem tartalmaz F-beli gráffal izomorf részgráfot, akkor τ(G) ≤ f(ν(G)), valamely f: N → N függvényre, ami nem függ G-től.

Fordítás

• Ez a szócikk részben vagy egészben az Erdős–Pósa theorem című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• (1965) „On independent circuits contained in a graph”. Canad. Journ. Math 17, 347–352. o. DOI:10.4153/CJM-1965-035-8.  
• (1969) „Eigenschaften von Graphen, die keine k+1 knotenfremde Kreise enthalten”. Mathematische Nachrichten 40, 19–25. o. DOI:10.1002/mana.19690400104.  
• (1965) „On graphs not containing independent circuits”. Mat. Lapok 16, 289–299. o.