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

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

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

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

Расширения

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

В более общем смысле, для абстрактных симплициальных комплексов порядковая размерность частичного набора граней комплекса не превышает 1 + d , где d — минимальная размерность евклидова пространства , в котором комплекс имеет геометрическую реализацию (Оссона де Мендес 1999 , 2002 ).

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

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

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

Частное множество инцидентности полного графа на n вершинах имеет порядковую размерность $\Theta (\log \log n)$ ( Спенсер 1971 ).

Ссылки

• Брайтуэлл, Г.; Троттер, В.Т. (1993), «Порядковая размерность выпуклых многогранников», SIAM Journal on Discrete Mathematics , 6 (2): 230–245, doi : 10.1137/0406018 , MR   1215230 .
• Брайтуэлл, Г.; Троттер, В.Т. (1997), «Порядковая размерность плоских карт», SIAM Journal on Discrete Mathematics , 10 (4): 515–528, CiteSeerX   10.1.1.127.1016 , doi : 10.1137/S0895480192238561 , MR   1477654 .
• Оссона де Мендес, П. (1999), «Геометрическая реализация симплициальных комплексов», в Краточвиле, Дж. (ред.), Proc. Межд. Симп. Рисование графиков (GD 1999) , Конспекты лекций по информатике, том. 1731, Springer-Verlag, стр. 323–332, номер документа : 10.1007/3-540-46648-7_33 , MR   1856785 .
• Оссона де Мендес, П. (2002), «Реализация частично упорядоченных наборов» (PDF) , Журнал графовых алгоритмов и приложений , 6 (1): 149–153, doi : 10.7155/jgaa.00048 , MR   1898206 .
• Шнайдер, В. (1989), «Плоские графы и размерность частичного множества», Order , 5 (4): 323–343, doi : 10.1007/BF00353652 , MR   1010382 , S2CID   122785359 .
• Спенсер, Дж. (1971), «Минимальные наборы скремблирования простых порядков», Математический журнал Венгерской академии наук , 22 (3–4): 349–353, doi : 10.1007/bf01896428 , MR   0292722 , S2CID   123142998 .