Teorema Robertson-Seymour

Această intrare pe tema matematicii este doar o schiță . Contribuiți la îmbunătățirea acestuia în conformitate cu convențiile Wikipedia . Urmați sfaturile de proiectare de referință .

În teoria graficelor, teorema Robertson-Seymour constituie o largă generalizare a teoremei lui Kuratowski considerată ca o afirmație că ${\displaystyle {\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">K.</span></span>}}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">5</span></span>}}}${\ displaystyle \, K_ {5}} Și ${\displaystyle {\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">K.</span></span>}}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">3</span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">,</span></span>\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">3</span></span>}}}${\ displaystyle \, K_ {3,3}} sunt „minori interziși” pentru graficele plane.

Afirmație

Să luăm în considerare orice număr natural g și suprafețe din genul g . Există un set de grafice P (g) (set de minori interzise pentru g ) astfel încât fiecare grafic care poate fi scufundat într-o suprafață a genului g nu are niciun element de P (g) printre minori.

Bibliografie

MR Fellows (1987): The Robertson-Seymour Theorems: A Survey of Applications , Contemp. Matematica. 89, pp.1-18

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică