Olarak grafik teorisi , Erdös ve Posa teoremi adını, Paul Erdös ve Lajos Posa (en) , bir grafik bir minimum boyuta ayrık döngüsü bir toplama en büyük boyutu ile ilgilidir köşelerin kesme döngüsü ( geri besleme tepe grubu ).
Erdős – Pósa teoremi - Bir f : N → N fonksiyonu vardır, öyle ki herhangi bir G grafiği ve herhangi bir pozitif k tamsayısı için aşağıdaki ifadelerden biri doğrudur:
Ayrıca, f ( k ) = O ( k log k ) .
Bu teorem, f (2) = 3 olan Béla Bollobás'ın yayınlanmamış bir sonucunu genelleştirir . Lovász , 2 ayrık döngü içermeyen grafiklerin tam bir tanımını verdi. Voss, f (3) = 6 ve 9 ≤ f (4) ≤ 12 olduğunu kanıtladı . Bir genel k için , Erdős ve Pósa, yukarıdaki teoremin ifadesini sağlayan herhangi bir f fonksiyonunun , f ( k ) = Ω ( k log k ) olacak şekilde olduğunu gösterdi . Voss ayrıca f ( k ) = (2 + o (1)) k log k üst sınırını ve alt sınır f ( k ) ≥ elde etti.18 k günlüğü k .
Teoremle benzerlik kurarak, herhangi bir G grafiği ve herhangi bir pozitif tamsayı k için bir f : N → N işlevi varsa, bir F grafik ailesinin Erdős – Pósa özelliğine sahip olduğunu söyleriz , aşağıdaki ifadelerden biri doğrudur:
Yukarıdaki tanımdaki (daha küçük) f işlevi , F ailesinin Erdős-Pósa özelliği için uçbirim olarak adlandırılır . Bu terminolojiyle, Erdős – Pósa teoremi şu şekilde yeniden formüle edilir: tüm döngülerin F ailesi , f ( k ) = Θ ( k log k ) ile bağlı Erdős ve Pósa özelliğine sahiptir . Bir H grafiği verildiğinde , H'yi minör olarak içeren tüm grafiklerin sınıfını F ( H ) ile belirtin . Izgara dışlama teoreminin bir sonucu olarak , Robertson ve Seymour , Erdős ve Pósa teoreminin önemli bir genellemesini gösterdi:
Teorem - F ( H ) Erdős – Pósa özelliğine sahiptir ancak ve ancak H bir düzlemsel grafik ise .
Daha sonra, bağlı mukabil gösterilmiştir olan f ( k ) = Θ ( k ) ise , H , bir bir orman ve olduğunu f ( k ) = Θ ( k günlük k ) herhangi bir diğeri için düzlemsel H grafik. H'nin bir üçgen olduğu özel durum , Erdős ve Pósa teoremine eşdeğerdir.
Erdős – Pósa teoremini Kőnig'in teoreminin kuzeni olarak görebiliriz ; bu, yukarıda açıklanan formalizmde ifade edildiğinde, iki parçalı grafiklerde F ( K 2 ) 'nin f ( k ) = k ile bağlı Erdős-Pósa özelliğine sahip olduğu anlamına gelir. . Aynısı , bir grafikteki maksimum sayıda ayrık nesne (bu durumda yollar) ile tüm bu nesneleri (bir ayırıcı) yok etmek için kaldırılacak minimum köşe sayısıyla ilişkilendiren Menger teoremi için de geçerlidir .