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

Теорема Шнайдера — это описание планарных графов в терминах Шаблон:Не переведено 5 его Шаблон:Не переведено 5. Теорема носит имя Вальтера Шнайдера, опубликовавшего её доказательство в 1989 году.

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

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

Расширения

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

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

Другие графы

Как заметил Шнайдер, частично упорядоченное множество инцидентности вершин графа G имеет порядковую размерность два тогда и только тогда, когда граф является путём или подграфом пути. Чтобы частично упорядоченное множество инцидентности вершин имело порядковую размерность два, необходимо, чтобы реализатор состоял из двух полных порядков, которые (ограниченные на вершины графа) обратны друг другу. Любые другие два порядка давали бы пересечение, которое включает отношение порядка между двумя вершинами, что недопустимо для частично упорядоченного множества инцидентности вершин. Для этих двух порядков на вершинах ребро между двумя соседними вершинами может быть включено в порядок путём размещения его непосредственно за последним из двух конечных вершин дуги, но никакие другие рёбра включить нельзя.

Если граф можно раскрасить в четыре цвета, то его частично упорядоченное множество инцидентности вершин имеет порядковую размерность, не превосходящую четырёх Шаблон:Harv.

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

Литература

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