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

Теорема Шнайдера — це опис планарного графа в термінах порядкової розмірності^[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].

Примітки

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

Література

• Brightwell G., Trotter W. T. The order dimension of convex polytopes // SIAM Journal on Discrete Mathematics. — 1993. — Т. 6, вип. 2. — С. 230–245. — DOI:10.1137/0406018.
• Brightwell G., Trotter W. T. The order dimension of planar maps // SIAM Journal on Discrete Mathematics. — 1997. — Т. 10, вип. 4. — С. 515–528. — DOI:10.1137/S0895480192238561.
• Ossona de Mendez P. Geometric realization of simplicial complexes // Proc. Int. Symp. Graph Drawing (GD 1999) / Kratochvil J. — Springer-Verlag, 1999. — Т. 1731. — С. 323–332. — (Lecture Notes in Computer Science) — DOI:10.1007/3-540-46648-7_33.
• Ossona de Mendez P. Realization of posets // Journal of Graph Algorithms and Applications. — 2002. — Т. 6, вип. 1. — С. 149–153.
• Schnyder W. Planar graphs and poset dimension // Order^[en]. — 1989. — Т. 5. — С. 323–343. — DOI:10.1007/BF00353652.
• Spencer J. Minimal scrambling sets of simple orders // Acta Mathematica Academiae Scientiarum Hungaricae. — 1971. — Т. 22. — С. 349–353. — DOI:10.1007/bf01896428.