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

Частково впорядкована множина інцидентних вершин неорієнтованого графа з множиною вершин і множиною ребер  — це частково впорядкована множина висоти 2, яка має як елементи. У цій частково впорядкованій множині є відношення порядку якщо є вершиною, є ребром і є одним із кінців .

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

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

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

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

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

Частково впорядкована множина інцидентності вершин повного графа з n вершинами має порядкову розмірність .

Примітки

Література