Teorema lui Schneider

Teorema lui Schneider este o descriere a graficelor plane în termenii dimensiunii ordinale setului său de incidență a vârfurilor parțial ordonat . Teorema este numită după Walter Schneider, care și-a publicat demonstrația în 1989.

Pozetul de vârfuri incidente ale unui graf nedirecționat G cu mulțimea de vârfuri V și mulțimea de muchii E este o poziție de înălțime 2 care are ca elemente. Acest poset are relații de ordine dacă x este un vârf, y este o muchie și x este unul dintre capetele lui y .

Dimensiunea ordinală a unei mulțimi parțial ordonate este cel mai mic număr de ordine complete a căror intersecție dă o mulțime parțial ordonată dată. Un astfel de set de ordine se numește implementator de set parțial ordonat. Teorema lui Schneider afirmă că un grafic G este plan dacă și numai dacă dimensiunea ordinală nu depășește trei.

Extensii

Teorema a fost generalizată de Brightwell și Trotter [1] [2] pentru a obține o estimare clară a dimensiunii posetelor de înălțime trei, formate în mod similar din vârfurile muchiilor și fețelor unui poliedru convex sau, mai general, un grafic planar încorporat. În ambele cazuri, dimensiunea ordinală a unei mulțimi parțial ordonate nu depășește patru. Totuși, rezultatul nu poate fi generalizat la poliedre convexe multidimensionale , deoarece există poliedre cu patru dimensiuni ale căror rețele fețe au o dimensiune ordinală nemărginită.

Pentru complexe abstracte simpliale , dimensiunea ordinală a mulțimii parțial ordonate de fețe ale complexului nu depășește 1 + d , unde d este dimensiunea minimă a spațiului euclidian în care complexul are o realizare geometrică [3] [ 4] .

Alte grafice

După cum a observat Schneider, punctul de interes al unui grafic G are dimensiunea de ordin doi dacă și numai dacă graficul este o cale sau un subgraf al unei căi. Pentru ca un set de incidență a nodurilor parțial ordonat să aibă dimensiunea ordinală doi, este necesar ca implementatorul să fie format din două ordine complete care (restricționate la vârfurile graficului) sunt inverse unul față de celălalt. Orice alte două ordine ar da o intersecție care include o relație de ordine între două vârfuri, care nu este permisă pentru un set de incidență a vârfurilor parțial ordonat. Pentru aceste două ordine de vârfuri, o muchie între două vârfuri adiacente poate fi inclusă în ordine prin plasarea ei direct în spatele ultimului dintre cele două vârfuri de capăt ale arcului, dar nu pot fi incluse alte muchii.

Dacă un grafic poate fi colorat cu patru culori, atunci poziția sa de incidență a vârfurilor are dimensiunea ordinală de cel mult patru ( Schnyder 1989 ).

Mulțimea de incidență parțial ordonată a vârfurilor unui graf complet cu n vârfuri are dimensiunea ordinală [5] .

Note

  1. ↑ Brightwell, Trotter, 1993 .
  2. ↑ Brightwell, Trotter, 1997 .
  3. ↑ Ossona de Mendez, 1999 .
  4. ↑ Ossona de Mendez, 2002 .
  5. ↑ Spencer, 1971 .

Literatură