Twierdzenie Schnydera

W teorii grafów twierdzenie Schnydera jest charakterystyką grafów planarnych pod względem wymiaru rzędu ich pozycji występowania . Został nazwany na cześć Waltera Schnydera, który opublikował dowód w 1989 roku .

Poset padania P ( G ) grafu nieskierowanego G ze zbiorem wierzchołków V i zbiorem krawędzi E jest częściowo uporządkowanym zbiorem wysokości 2, którego elementami są V ∪ E. W tym częściowym porządku istnieje relacja porządku x < y , gdy x jest wierzchołkiem, y jest krawędzią, a x jest jednym z dwóch punktów końcowych y .

Wymiar porządku częściowego porządku to najmniejsza liczba całkowitych porządków, których przecięciem jest dany porządek częściowy; taki zbiór porządków nazywany jest realizatorem porządku cząstkowego. Twierdzenie Schnydera stwierdza, że ​​graf G jest planarny wtedy i tylko wtedy, gdy wymiar rzędu P ( G ) wynosi co najwyżej trzy.

Rozszerzenia

Twierdzenie to zostało uogólnione przez Brightwella i Trottera ( 1993 , 1997 ) do ścisłego ograniczenia wymiaru wysokości trzech częściowo uporządkowanych zbiorów utworzonych analogicznie z wierzchołków, krawędzi i ścian wielościanu wypukłego lub, bardziej ogólnie, z osadzonej płaszczyzny wykres: w obu przypadkach wymiar porządku posetu wynosi co najwyżej cztery. Jednak wyniku tego nie można uogólnić na wielowymiarowe wypukłe polytopy , ponieważ istnieją czterowymiarowe polytopy, których sieci twarzy mają wymiar nieograniczonego rzędu.

Jeszcze bardziej ogólnie, dla abstrakcyjnych kompleksów symplicjalnych , wymiar porządku zbioru ścian kompleksu wynosi co najwyżej 1 + d , gdzie d jest minimalnym wymiarem przestrzeni euklidesowej, w której kompleks ma realizację geometryczną (Ossona de Mendez 1999 , 2002 ).

Inne wykresy

Jak zauważa Schnyder, poset padania grafu G ma wymiar rzędu dwa wtedy i tylko wtedy, gdy graf jest ścieżką lub podgrafem ścieżki. Gdy bowiem poset incydencji ma wymiar rzędu dwa, jego jedyny możliwy realizator składa się z dwóch całkowitych rzędów, które (w przypadku ograniczenia do wierzchołków grafu) są wzajemnie odwrotne. Jakiekolwiek inne dwa rzędy miałyby przecięcie, które obejmuje relację porządku między dwoma wierzchołkami, co nie jest dozwolone w przypadku pozycji występowania. W przypadku tych dwóch rzędów wierzchołków krawędź między kolejnymi wierzchołkami może zostać uwzględniona w porządku, umieszczając ją bezpośrednio po późniejszym z dwóch punktów końcowych krawędzi, ale nie można uwzględnić żadnych innych krawędzi.

Jeśli graf można pokolorować czterema kolorami, to jego zestaw częstości ma wymiar rzędu co najwyżej czterech ( Schnyder 1989 ).

Zbiór częstości pełnego wykresu na n wierzchołkach ma wymiar porządku ${\ Displaystyle \ Theta (\ log \ log n)}$ ( Spencer 1971 ).

•   Brightwell, G.; Trotter, WT (1993), „Wymiar rzędu wypukłych polytopów”, SIAM Journal on Discrete Mathematics , 6 (2): 230–245, doi : 10,1137/0406018 , MR 1215230 .
•    Brightwell, G.; Trotter, WT (1997), „Wymiar porządku map planarnych”, SIAM Journal on Discrete Mathematics , 10 (4): 515–528, CiteSeerX 10.1.1.127.1016 , doi : 10.1137/S0895480192238561 , MR 1477654 .
•   Ossona de Mendez, P. (1999), „Geometryczna realizacja uproszczonych kompleksów”, w: Kratochvil, J. (red.), Proc. Int. Symp. Rysowanie wykresów (GD 1999) , Notatki z wykładów z informatyki, tom. 1731, Springer-Verlag, s. 323–332, doi : 10.1007/3-540-46648-7_33 , MR 1856785 .
•   Ossona de Mendez, P. (2002), „Realizacja posetów” (PDF) , Journal of Graph Algorithms and Applications , 6 (1): 149–153, doi : 10,7155/jgaa.00048 , MR 1898206 .
•    Schnyder, W. (1989), „Wykresy planarne i wymiar posetowy”, Order , 5 (4): 323–343, doi : 10.1007 / BF00353652 , MR 1010382 , S2CID 122785359 .
•    Spencer, J. (1971), „Minimalne zestawy szyfrujące prostych zamówień”, Acta Mathematica Academiae Scientiarum Hungaricae , 22 (3–4): 349–353, doi : 10.1007/bf01896428 , MR 0292722 , S2CID 123142998 .