Теорема Шнайдерса - Schnyders theorem

В теория графов, Теорема Шнайдера это характеристика планарные графы с точки зрения размер заказа от их случаи заболеваемости. Он назван в честь Уолтера Шнайдера, который опубликовал свое доказательство в 1989.

Заболеваемость посет $п (грамм)$ из неориентированный граф $грамм$ с вершина набор $V$ и край набор $E$ это частично заказанный набор из высота 2, который имеет $V \cup E$ как его элементы. В этом частичном порядке существует отношение порядка $Икс < у$ когда $Икс$ это вершина, $у$ это край, и $Икс$ это одна из двух конечных точек $у$ .

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

Расширения

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

В более общем плане для абстрактные симплициальные комплексы, порядковая размерность расположения граней комплекса не превосходит $1 + d$ , куда $d$ минимальный размер Евклидово пространство в котором комплекс имеет геометрическую реализацию (Ossona de Mendez1999, 2002 ).

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

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

Если график можно цветной с четырьмя цветами, то его посет инцидентности имеет размерность порядка не более четырех (Шнайдер 1989 ).

Частота возникновения полный график на п вершины имеют размерность порядка ${ Displaystyle Theta ( журнал журнал п)}$ (Спенсер 1971 ).

Теорема Шнайдерса - Schnyders theorem

Расширения

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

Рекомендации