В математике частично упорядоченное множество инцидентности или порядок инцидентности — это тип частично упорядоченного множества , представляющего отношение инцидентности между вершинами и ребрами неориентированного графа . ЧУМ графа G имеет элемент для каждой вершины или ребра в G ; в этом ЧУМ существует отношение порядка x ≤ y тогда и только тогда, когда либо x = y , либо x является вершиной, y является ребром, а x является конечной точкой y .
Например, зигзагообразный посет или забор с нечетным числом элементов, с чередующимися отношениями порядка a < b > c < d ... является инцидентным посетом графа путей .
Каждый инцидентный посет непустого графа имеет высоту два. Его ширина равна числу ребер плюс число ациклических связных компонент.
Инцидентные частично упорядоченные множества были особенно изучены в отношении их размерности порядка и ее связи со свойствами базового графа. Инцидентный частично упорядоченный множество связного графа G имеет размерность порядка не более двух тогда и только тогда, когда G является графом путей, и имеет размерность порядка не более трех тогда и только тогда, когда G не более чем планарный ( теорема Шнайдера ). [1] Однако графы, чьи инцидентные частично упорядоченные множества имеют размерность порядка 4, могут быть плотными [2] и могут иметь неограниченное хроматическое число . [3] Каждый полный граф на n вершинах, и, по расширению, каждый граф на n вершинах, имеет инцидентный частично упорядоченный множество с размерностью порядка O (log log n ). [4] Если инцидентный частично упорядоченный множество имеет высокую размерность, то он должен содержать копии инцидентных частично упорядоченных множеств всех малых деревьев либо как подпорядки, либо как двойственные подпорядки. [5]