| Математические заметки |
|
|
|
|
|
Краткие сообщения О пучке паросочетаний графа и LP-ориентациях многогранника паросочетаний А. И. Болотников Московский государственный университет им. М. В. Ломоносова
Англоязычная версия:
Mathematical Notes, 2023, Volume 114, Issue 2, Pages DOI: https://doi.org/10.1134/S0001434623070283 
Реферативные базы данных:
 1. ВведениеКаждой конфигурации гиперплоскостей можно сопоставить частично упорядоченное множество пересечений ее гиперплоскостей. Результаты о связи частично упорядоченных множеств пересечений гиперплоскостей с алгебрами Орлика–Соломона [1], [2] имеют приложения в алгебре, комбинаторике и топологии. Одной из комбинаторных задач, связанных с конфигурациями гиперплоскостей, является задача подсчета числа регионов конфигурации. По частично упорядоченному множеству конфигурации можно построить характеристический многочлен конфигурации. Число регионов конфигурации далее можно выразить с помощью характеристического многочлена конфигурации [3]. Обобщением задачи о числе регионов конфигурации является задача о нахождении числа $k$-мерных клеток разбиения проективного пространства гиперплоскостями [4]–[6]. Подсчет числа регионов конфигурации гиперплоскостей с помощью его характеристического многочлена применим в некоторых задачах комбинаторики. Например, с помощью специальной конфигурации гиперплоскостей и связанных с ней математических конструкций в работах [7]–[9] были найдены асимптотические оценки числа пороговых функций и числа вырожденных $\{\pm 1\}$-матриц. В работе [10] связь хроматического многочлена графа и числа его ациклических ориентаций была выражена в терминах пучков гиперплоскостей. Оказалось, что построенный по множеству ребер графа пучок, названный графическим, имеет характеристический многочлен, равный хроматическому многочлену исходного графа, а число его регионов равно числу ациклических ориентаций исходного графа. В работе [11] задача о максимальном паросочетании для произвольного графа была представлена как задача линейного программирования. В рамках этого представления был построен многогранник паросочетаний, вершины которого соответствуют паросочетаниям исходного графа. С линейным программированием также тесно связано понятие LP-ориентаций [12]. В работе [13] было дано определение специального пучка гиперплоскостей – пучка паросочетаний, были доказаны его основные свойства, а также свойства его характеристического многочлена. В данной работе описывается связь между пучком паросочетаний и многогранником паросочетаний. Строится взаимно-однозначное соответствие между регионами пучка паросочетаний и LP-ориентациями многогранника паросочетаний. Благодаря такому соответствию число LP-ориентаций многогранника паросочетаний можно найти с помощью характеристического многочлена пучка паросочетаний. 2. Основные определенияОпределение 1. Конфигурация гиперплоскостей – конечное множество гиперплоскостей в некотором векторном пространстве $V$. В данной работе в качестве $V$ используется евклидово пространство $\mathbb{R}^n$. Определение 2. Если все гиперплоскости конфигурации проходят через одну точку, то такая конфигурация называется пучком. Определение 3. Регион конфигурации – связная компонента дополнения к объединению гиперплоскостей конфигурации. Определение 4. Пучок паросочетаний графа определим следующим образом. Пусть $G(V,E)$, $|E|=n$ – граф без петель и кратных ребер, $N\colon E\to \{1,2,\dots,n\}$ - некоторая нумерация ребер в графе $G$. Рассмотрим в пространстве $\mathbb{R}^n$ следующие гиперплоскости: для любой последовательности ребер $(r_1,r_2,r_3,\dots,r_n)$, образующей простой незамкнутый путь произвольной длины или простой цикл четной длины в графе $G$, берем гиперплоскость $x_1-x_2+x_3-\cdots+(-1)^{n+1}x_n=0$. Все такие гиперплоскости образуют некоторый пучок. Данный пучок назовем пучком паросочетаний графа и обозначим $MA(G,N)$. Определение 5 [6]. Пусть $G(V,E)$, $|E|=n$, – граф без петель и кратных ребер. Многогранник паросочетаний – выпуклый многогранник в $\mathbb{R}^n$, который задается системой неравенств, состоящей из всех неравенств следующих трех видов: Каждому паросочетанию графа $G(V,E)$, $|E|=n$, может быть взаимно однозначно сопоставлена вершина $n$-мерного булева куба следующим образом. Пусть $M$ – паросочетание в графе $G$. Тогда ему сопоставляется вершина булева куба $(x_1,x_2,x_3,\dots,x_n)$, где $x_i=1$, если ребро $e_i$ принадлежит $M$, и $x_i=0$ в противоположном случае. Таким образом, построено взаимно-однозначное соответствие между множеством паросочетаний графа $G$ и некоторым подмножеством $D$ вершин булева куба. Теорема 1 [6]. Подмножество $D$ является множеством вершин многогранника паросочетаний. Пусть $P$ – многогранник в $\mathbb{R}^n$, а $\phi\colon \mathbb{R}^n \to \mathbb{R}$ – линейная функция, которая на любых вершинах $P$, соединенных ребром, принимает различные значения. Тогда $\phi$ индуцирует на одномерном остове $P$ ориентацию ребер следующим образом. Ребро $(v_i,v_j)$, соединяющее вершины $v_i$ и $v_j$, ориентируется от $v_i$ к $v_j$, если $\phi(v_i) < \phi(v_j)$. Индуцированная таким образом ориентация называется LP-ориентацией. 3. Основной результатПусть $G(V,E)$, $|E|=n$, – граф без петель и кратных ребер, $P(G)$ – многогранник паросочетаний $G$. Пусть $L(P(G))$ – множество LP-ориентаций многогранника $P(G)$. Определим отображение $F\colon L(P(G)) \to 2^{\mathbb{R}^{n}}$ следующим образом. Для любой LP-ориентации $O$
$$
\begin{equation*}
\begin{aligned} \, F(O)&=\bigl\{(\alpha_1,\alpha_2,\dots,\alpha_n) \in \mathbb{R}^n \mid f(x_1,x_2,\dots,x_n) \\ &\qquad=\alpha_{1}x_1+\alpha_{2}x_2+\cdots+ \alpha_{n}x_n \text{ индуцирует }O\bigr\}. \end{aligned}
\end{equation*}
\notag
$$
Пусть $RG(MA(G))=\{R_1,R_2,\dots,R_n\}$ – множество регионов пучка паросочетаний графа $G$. Доказательство. Пусть $\Pi(v)$ – паросочетание, соответствующее вершине $v$ многогранника паросочетаний. Многогранник паросочетаний обладает следующим свойством [14; теорема 25.3]: вершины $v_1$ и $v_2$ многогранника $P(G)$ соединены ребром тогда и только тогда, когда $\Pi(v_1)\triangle\Pi(V_2)$ является простым незамкнутым путем либо простым циклом четной длины. Пусть $O$ – LP-ориентация $P(G)$, точки $a=(a_1,\dots,a_n)$ и $b=(b_1,\dots,b_n)$ являются элементами $F(O)$. Предположим, что $a$ и $b$ лежат в разных регионах $MA(G)$. Тогда существует простой незамкнутый путь или простой цикл четной длины $(e_{i_1},e_{i_2},\dots,e_{i_k})$, $e_{i_j} \in E$, такой, что точки $a$ и $b$ лежат по разные стороны от гиперплоскости Пусть для определенности
$$
\begin{equation*}
a_{i_1}-a_{i_2}+a_{i_3}+\cdots+(-1)^{k+1}a_{i_k} > 0, \qquad b_{i_1}-b_{i_2}+b_{i_3}+\cdots+(-1)^{k+1}b_{i_k} < 0.
\end{equation*}
\notag
$$
По построению множества ребер $\{e_{i_1},e_{i_3},e_{i_5},\dots\}$ и $\{e_{i_2},e_{i_4},e_{i_6},\dots\}$ являются паросочетаниями, а соответствующие им вершины $P(G)$ соединены ребром $t$ многогранника $P(G)$. Функции $f_a(x)=a_1 x_1+a_2 x_2+\cdots+a_n x_n$ и $f_b(x)=b_1 x_1+b_2 x_2+\cdots+b_n x_n$ это ребро ориентируют по-разному, а значит, $a$ и $b$ не могут одновременно принадлежать $F(O)$. Предположим теперь, что $a$ лежит на границе региона $R$, т.е. на некоторой гиперплоскости $x_{i_1}-x_{i_2}+x_{i_3}+\dots+(-1)^{k+1}x_{i_k}=0$. Тогда функция $f_a$ принимает одинаковые значения на вершинах $P(G)$, соответствующих паросочетаниям $\{e_{i_1},e_{i_3},e_{i_5},\dots\}$ и $\{e_{i_2},e_{i_4},e_{i_6},\dots\}$, и соединенных ребром. Следовательно, $f_a$ не может индуцировать LP-ориентацию, а значит, $a$ не может лежать в $F(O)$. Таким образом, если $O$ – произвольный элемент $L(P(G))$, то $F(O)$ целиком лежит внутри некоторого региона $R_i$. Пусть $a \in F(O)$, $b\in R_i$, $b$ не лежит в $F(O)$. Так как $b$ не лежит ни на одной из гиперплоскостей $MA(G)$, $f_b$ принимает различные значения на вершинах любого ребра многогранника $P(G)$, а значит, $f_b$ индуцирует LP-ориентацию $\widehat O$. Предположим, что ребро $t$ по-разному ориентировано в $O$ и в $\widehat O$. Пусть $v_1$ и $v_2$ – вершины $t$, $\Pi(v_1)=\{e_{j_1},e_{j_3},\dots\}$, $\Pi(v_2)=\{e_{j_2},e_{j_4},\dots\}$. Тогда $H\colon x_{j_1}-x_{j_2}+x_{j_3}-\cdots=0$ – гиперплоскость пучка $MA(G)$, причем $a$ и $b$ лежат по разные стороны от $H$, что противоречит тому, что $a$ и $b$ лежат в одном регионе $R_i$. Следовательно, $O=\widehat O$, $F(O)=R_i$ и $F\colon L(P(G))\to RG(MA(G))$ инъективно. Пусть $R$ – некоторый регион $MA(G)$, $b \in R$. Так как $b$ не лежит ни на одной из гиперплоскостей $MA(G)$, $f_b$ принимает различные значения на вершинах любого ребра многогранника $P(G)$, а значит, $f_b$ индуцирует некоторую LP-ориентацию $\overline{O}$. Тогда по доказанному выше $F(\overline{O})=R$. Следовательно, $F$ сюръективно. Таким образом, $F$ – биекция. Автор благодарит А. А. Ирматова за постановку задачи и обсуждение полученных результатов. 
Цитирование в формате AMSBIB
\RBibitem{Bol23} |
|
||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|