В теории графов теорема Шнайдера является характеристикой планарных графов в терминах размерности порядка их инцидентных множеств . Она названа в честь Уолтера Шнайдера, который опубликовал ее доказательство в 1989 году.
Инцидентный посет P ( G ) неориентированного графа G с множеством вершин V и множеством ребер E — это частично упорядоченное множество высоты 2 , элементами которого являются V ∪ E. В этом частичном порядке существует отношение порядка x < y , когда x — вершина, y — ребро, а x — одна из двух конечных точек y .
Размерность порядка частичного порядка — это наименьшее число полных порядков, пересечение которых является заданным частичным порядком; такой набор порядков называется реализатором частичного порядка. Теорема Шнайдера утверждает, что граф G является планарным тогда и только тогда, когда размерность порядка P ( G ) не превышает трех.
Эта теорема была обобщена Брайтвеллом и Троттером (1993, 1997) до жесткой границы размерности частично упорядоченных множеств высоты три, образованных аналогично из вершин, ребер и граней выпуклого многогранника или, в более общем случае, вложенного планарного графа: в обоих случаях размерность порядка частично упорядоченного множества не превышает четырех. Однако этот результат не может быть обобщен на многомерные выпуклые многогранники , поскольку существуют четырехмерные многогранники, решетки граней которых имеют неограниченную размерность порядка.
Еще более обобщенно, для абстрактных симплициальных комплексов размерность порядка частично упорядоченного множества граней комплекса не превышает 1 + d , где d — минимальная размерность евклидова пространства , в котором комплекс имеет геометрическую реализацию (Ossona de Mendez 1999, 2002).
Как замечает Шнайдер, инцидентный ЧУМ графа G имеет размерность порядка два тогда и только тогда, когда граф является путем или подграфом пути. Ибо, когда инцидентный ЧУМ имеет размерность порядка два, его единственный возможный реализатор состоит из двух полных порядков, которые (при ограничении вершинами графа) являются обратными друг другу. Любые другие два порядка имели бы пересечение, которое включает отношение порядка между двумя вершинами, что не допускается для инцидентных ЧУМ. Для этих двух порядков на вершинах ребро между последовательными вершинами может быть включено в упорядочение, помещая его сразу после более поздней из двух конечных точек ребра, но никакие другие ребра не могут быть включены.
Если граф можно раскрасить четырьмя цветами, то его порядковый номер инцидентности имеет размерность не более четырех (Schnyder 1989).
Инцидентное частично упорядоченное множество полного графа с n вершинами имеет размерность порядка (Спенсер, 1971).
