Введение

Измерение порядка инцидентностей в планарных графах
В теории графов теорема Шнайдера является характеризацией планарных графов с точки зрения измерения порядка их инцидентных частично упорядоченных множеств. Она названа в честь Вальтера Шнайдера, который опубликовал её доказательство в 1989 году. Инцидентное частично упорядоченное множество P(G) неориентированного графа G с множеством вершин V и множеством ребер E – это частично упорядоченное множество высоты 2, элементами которого являются V ∪ E. В этом частичном порядке существует отношение порядка x < y, когда x – вершина, y – ребро, и x является одной из двух конечных точек y. Измерение порядка частично упорядоченного множества – это наименьшее число полных порядков, пересечение которых является данным частичным порядком; такое множество порядков называется реализатором частичного порядка. Теорема Шнайдера утверждает, что граф G является планарным тогда и только тогда, когда измерение порядка P(G) не превышает трех.

Расширения

Эта теорема была обобщена до точной границы для размерности частично упорядоченных множеств высоты три, образованных аналогичным образом из вершин, ребер и граней выпуклого многогранника или, в более общем случае, из планарного графа, заданного на плоскости: в обоих случаях размерность порядка множества не превышает четырех. Однако этот результат нельзя обобщить на выпуклые политопы более высокой размерности, поскольку существуют четырехмерные политопы, чьи решетки граней имеют неограниченную размерность порядка. Более общим образом, для абстрактных симплициальных комплексов размерность порядка лицевого позита комплекса не превышает 1 + d, где d – минимальная размерность евклидова пространства, в котором комплекс имеет геометрическую реализацию.

Другие графики

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