Частично упорядоченные множества и их графы сравнимости

Под графом будем понимать неориентированный граф без петель и параллельных ребер. Через $C(P)$ обозначим граф сравнимости частично упорядоченного (ч.у.) множества $P$, т. е. граф, состоящий из тех же элементов, что и $P$, в котором вершины $x$ и $y$ смежны тогда и только тогда, когда в $P$ либо $x<y$, либо $y<x$. Будем говорить, что граф $Q$ упорядочиваем, если $Q=C(P)$ для некоторого ч.у. множества $P$; любое $P$, для которого $C(P)=Q$, назовем упорядочением $Q$. $\sigma$-изоморфизмом ч.у. множества $P$ на ч.у. множество $P'$ назовем изоморфизм $C(P)$ на $C(P')$. В работе рассматриваются следующие вопросы. 1) Каковы необходимые и достаточные условия упорядочиваемости графа? 2) Как обозреть все упорядочения произвольного упорядочиваемого графа? 3) Каковы необходимые и достаточные условия $\sigma$-изоморфизма двух ч.у. множеств? 4) Каковы все ч.у. множества, каждый $\sigma$-изоморфизм которых есть изоморфизм или антиизоморфизм (дуальный изоморфизм)?
Основными результатами работы являются теоремы 2–4, решающие соответственно вопросы 2)–4). Попутно доказывается теорема 1, дающая ответ на вопрос 1), который был решен ранее Гилмором и Хофманом (РЖМ, 1966, 1А421). Доказательство теоремы 1 отличается от доказательства упомянутых авторов и основано на иных идеях. Вообще доказательства теорем 1–4 тесно связаны друг с другом и проводятся единым методом, в основе которого лежит рассмотрение стабильных подграфов. Идеи подобных рассмотрений восходят к работе РЖМ, 1964, 7А292 (см. также РЖМ, 1965, 9А286; 1967, 4А225; 1966, 12А320; заметим, что в цитированных работах свойство, аналогичное стабильности, называлось однородностью). Подграф $S$ графа $Q$ назовем стабильным, если любая вершина из $Q\setminus S$, смежная с некоторой вершиной из $S$, смежна и с каждой вершиной из $S$. При помощи стабильных подграфов определяется понятие так называемого канонического упорядочения упорядочиваемого графа.
Теорема 2. Любое упорядочение упорядочиваемого графа является каноническим.
Следствие теоремы 2 описывает графы, допускающие лишь конечное число упорядочений, и дает формулу для подсчета числа всех упорядочений произвольного такого графа. Другим следствием теоремы 2 является теорема 3.
Теорема 4. Для того чтобы каждый $\sigma$-изоморфизм ч.у. множества $P$ был изоморфизмом или антиизоморфизмом, необходимо и достаточно, чтобы самое большее одна из связных компонент $P$ была неодноэлементна, причем эта компонента не содержала бы неодноэлементных отличных от нее связных подмножеств, являющихся стабильными подграфами в $C(P)$.
В заключение приводятся решения вопросов, аналогичных указанным выше, для квазиупорядоченных множеств.