Schneider tétele

A Schneider-tétel a síkgráfok leírása a részlegesen rendezett csúcsbeesési halmaz ordinális dimenziója . A tétel Walter Schneider nevéhez fűződik, aki 1989-ben publikálta a bizonyítását.

A V csúcshalmazzal és E élhalmazzal rendelkező irányítatlan G gráf beeső csúcsainak készlete egy 2- es magasságú , elemei. Ennek a póznak vannak sorrendi relációi , ha x egy csúcs, y egy él, és x az y egyik vége .

Egy részlegesen rendezett halmaz ordinális dimenziója azon teljes rendelések legkisebb száma, amelyek metszéspontja egy adott részben rendezett halmazt ad. Az ilyen parancskészletet részlegesen rendezett halmazmegvalósítónak nevezzük. Schneider tétele kimondja, hogy egy G gráf akkor és csak akkor sík, ha az ordinális dimenzió nem haladja meg a hármat.

Kiterjesztések

A tételt Brightwell és Trotter általánosította [1] [2] , hogy éles becslést kapjon a konvex poliéder éleinek és lapjainak csúcsaiból hasonló módon kialakított három magasságú pózok méretére , vagy általánosabban, beágyazott síkgráf. A részben megrendelt készlet sorszáma mindkét esetben nem haladja meg a négyet. Az eredmény azonban nem általánosítható többdimenziós konvex poliéderekre , mivel vannak olyan négydimenziós poliéderek, amelyek laprácsainak korlátlan ordinális dimenziója van.

Absztrakt egyszerűsített komplexek esetén a komplex részlegesen rendezett laphalmazának ordinális mérete nem haladja meg az 1 + d értéket , ahol d az euklideszi tér minimális mérete , amelyben a komplex geometriai realizációval rendelkezik [3] [ 4] .

Egyéb grafikonok

Ahogy Schneider megjegyezte, a G gráf POI-jának akkor és csak akkor van második sorrendje, ha a gráf egy útvonal útvonala vagy részgráfja. Ahhoz, hogy egy részlegesen rendezett csúcsincidencia halmaz kettős ordinális dimenzióval rendelkezzen, szükséges, hogy az implementátor két teljes sorrendből álljon, amelyek (a gráf csúcsaira korlátozva) inverzek egymással. Bármely másik két sorrend olyan metszéspontot adna, amely két csúcs közötti sorrendi relációt tartalmaz, ami nem megengedett egy részlegesen rendezett csúcs előfordulási halmaz esetén. Ennél a két csúcsrendnél a két szomszédos csúcs közötti él beszámítható a sorrendbe, ha azt közvetlenül az ív két végpontja közül az utolsó mögé helyezzük, de más él nem szerepelhet.

Ha egy gráf négy színnel színezhető , akkor a csúcspont előfordulási poszete legfeljebb négy ordinális dimenzióval rendelkezik ( Schnyder 1989 ).

Egy n csúcsú teljes gráf csúcsainak részlegesen rendezett előfordulási halmaza ordinális dimenzióval rendelkezik [5] .

Jegyzetek

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

Irodalom