WikiDer > Заболеваемость посет

Incidence poset

В математике заболеваемость посет или же порядок заболеваемости это тип частично заказанный набор что представляет собой отношение инцидентности между вершинами и ребрами неориентированный граф. Частота возникновения графа грамм имеет элемент для каждой вершины или ребра в грамм; в этом наборе существует отношение порядка Икс ≤ у если и только если либо Икс = у или же Икс это вершина, у это край, и Икс конечная точка у.

Пример

Например, зигзагообразный позет или же изгородь с нечетным числом элементов, с чередующимися отношениями порядка а < б > c < d... это случайность граф путей.

Характеристики

Каждое ЧУМ инцидентности непустого графа имеет высота два. Его ширина равна количеству ребер плюс количество ациклических связных компонентов.

Позиции заболеваемости были особенно изучены в отношении их размер заказа, и его отношение к свойствам нижележащего графа. Множество инцидентности связного графа грамм имеет размерность порядка не более двух тогда и только тогда, когда грамм является графом путей и имеет размерность порядка не более трех тогда и только тогда, когда грамм самое большее плоское (Теорема Шнайдера).[1] Однако графы, чьи множества инцидентности имеют размерность порядка 4, могут быть плотный[2] и может иметь неограниченный хроматическое число.[3] Каждый полный график на п вершин, и, следовательно, каждый граф на п вершины, имеет ЧУМ инцидентности с размерностью порядка О(журнал журналап).[4] Если poset инцидентности имеет высокую размерность, то он должен содержать копии множеств инцидентности всех маленьких деревьев либо в виде подзаконных порядков, либо как двойников под порядков.[5]

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

  1. ^ Шнайдер, В. (1989), "Планарные графы и размерность посета", Заказ, 5 (4): 323–343, Дои:10.1007 / BF00353652.
  2. ^ Агнарссон, Гейр; Фельснер, Стефан; Троттер, Уильям Т. (1999), "Максимальное количество ребер в графе ограниченной размерности, с приложениями к теории колец", Дискретная математика, 201 (1–3): 5–19, Дои:10.1016 / S0012-365X (98) 00309-4, МИСТЕР 1687854.
  3. ^ Троттер, Уильям Т .; Ван, Жуйдун (2014), «Постановки заболеваемости и графики покрытия», Заказ, 31 (2): 279–287, arXiv:1308.2471, Дои:10.1007 / s11083-013-9301-9.
  4. ^ Хоштен, Серкан; Моррис, Уолтер Д., младший (1999), "Порядковая размерность полного графа", Дискретная математика, 201 (1–3): 133–139, Дои:10.1016 / S0012-365X (98) 00315-X, МИСТЕР 1687882.
  5. ^ Brightwell, Graham R .; Троттер, Уильям Т. (1994), "Посеты деревьев в положениях большого размера", Заказ, 11 (2): 159–167, Дои:10.1007 / BF01108600, МИСТЕР 1302404.