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

Теорема Шнайдера — це опис планарного графа в термінах Шаблон:Не перекладено його Шаблон:Не перекладено. Теорему названо ім'ям Вальтера Шнайдера, який опублікував її доведення 1989 року.

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

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

Розширення

Теорему узагальнили Брайтвел і ТроттерШаблон:SfnШаблон:Sfn для отримання точної оцінки розмірності частково впорядкованих множин висоти три, утворених аналогічно з вершин ребер і граней опуклого многогранника, або, загальніше, вкладеного планарного графа. В обох випадках порядкова розмірність частково впорядкованої множини не перевищує чотирьох. Однак результат не можна узагальнити на багатовимірні опуклі многогранники, тому що існують чотиривимірні многогранники, Шаблон:Не перекладено яких мають необмежену порядкову розмірність.

Для абстрактних симпліційних комплексів порядкова розмірність частково впорядкованої множини граней комплексу не перевищує Шаблон:Math, де Шаблон:Mvar — найменша розмірність евклідового простору, в якому комплекс має геометричну реалізаціюШаблон:SfnШаблон:Sfn.

Інші графи

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

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

Частково впорядкована множина інцидентності вершин повного графа з n вершинами має порядкову розмірність $\mathrm{\Theta }(\log \log n)$Шаблон:Sfn.

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття