Теорема Шнайдера

Теорема Шнайдера — це опис планарного графа в термінах порядкової розмірності^[en] його частково упорядкованої множини інцидентності вершин^[en]. Теорему названо ім'ям Вальтера Шнайдера, який опублікував її доведення 1989 року.

Частково впорядкована множина інцидентних вершин ${\displaystyle P(G)}$ неорієнтованого графа ${\displaystyle G}$ з множиною вершин ${\displaystyle V}$ і множиною ребер ${\displaystyle E}$ — це частково впорядкована множина висоти 2, яка має ${\displaystyle V\cup E}$ як елементи. У цій частково впорядкованій множині є відношення порядку ${\displaystyle x<y}$ якщо ${\displaystyle x}$ є вершиною, ${\displaystyle y}$ є ребром і ${\displaystyle x}$ є одним із кінців ${\displaystyle y}$.

Порядкова розмірність частково впорядкованої множини — це найменша кількість повних порядків, перетин яких дає дану частково впорядковану множину. Таку множину порядків називають реалізатором частково впорядкованої множини. Теорема Шнайдера стверджує, що граф ${\displaystyle G}$ є планарним тоді й лише тоді, коли порядкова розмірність ${\displaystyle P(G)}$ не перевищує трьох.

Розширення

Теорему узагальнили Брайтвел і Троттер^[1][2] для отримання точної оцінки розмірності частково впорядкованих множин висоти три, утворених аналогічно з вершин ребер і граней опуклого многогранника, або, загальніше, вкладеного планарного графа. В обох випадках порядкова розмірність частково впорядкованої множини не перевищує чотирьох. Однак результат не можна узагальнити на багатовимірні опуклі многогранники, тому що існують чотиривимірні многогранники, решітки граней^[en] яких мають необмежену порядкову розмірність.

Для абстрактних симпліційних комплексів порядкова розмірність частково впорядкованої множини граней комплексу не перевищує 1 + d, де d — найменша розмірність евклідового простору, в якому комплекс має геометричну реалізацію^[3][4].

Інші графи

Як зауважив Шнайдер, частково впорядкована множина інцидентності вершин графа ${\displaystyle G}$ має порядкову розмірність два тоді й лише тоді, коли граф є шляхом або підграфом шляху. Щоб частково впорядкована множина інцидентності вершин мала порядкову розмірність два, необхідно, щоб реалізатор складався з двох повних порядків, які (обмежені вершинами графа) обернені один до одного. Будь-які інші два порядки давали б перетин, який включає відношення порядку між двома вершинами, що неприпустимо для частково впорядкованої множини інцидентності вершин. Для цих двох порядків на вершинах ребро між двома сусідніми вершинами можна включити в порядок, розмістивши його безпосередньо за останнім з двох кінцевих вершин ребра^{[прояснити]}, але інші ребра включити не можна.

Якщо граф можна розфарбувати в чотири кольори, то його частково впорядкована множина інцидентності вершин має порядкову розмірність, що не перевищує 4 (Schnyder, 1989) .

Частково впорядкована множина інцидентності вершин повного графа з n вершинами має порядкову розмірність ${\displaystyle \Theta (\log \log n)}$^[5].