Полиматроид

В математике полиматроид — это многогранник , связанный с субмодулярной функцией . Это понятие было введено Джеком Эдмондсом в 1970 году. ^[1] Его также называют мультимножественным аналогом матроида .

Определение

Позволять $E$ быть конечным множеством и $f:2^{E}\rightarrow \mathbb {R} _{+}$ неубывающая субмодулярная функция , то есть для каждого $A\subseteq B\subseteq E$ у нас есть $f(A)\leq f(B)$ , и для каждого $A,B\subseteq E$ у нас есть $f(A)+f(B)\geq f(A\cup B)+f(A\cap B)$ . Определим полиматроид, ассоциированный с $f$ быть следующим многогранником :

$P_{f}={\Big \{}{\textbf {x}}\in \mathbb {R} _{+}^{E}~{\Big |}~\sum _{e\in U}{\textbf {x}}(e)\leq f(U),\forall U\subseteq E{\Big \}}$ .

Когда мы разрешаем запись ${\textbf {x}}$ чтобы быть отрицательным, мы обозначаем этот многогранник через $EP_{f}$ и назовем его расширенным полиматроидом, связанным с $f$ . ^[2]

Эквивалентное определение

Позволять $E$ быть конечным множеством . Если ${\textbf {u}},{\textbf {v}}\in \mathbb {R} ^{E}$ то мы обозначим через $|{\textbf {u}}|$ сумма записей ${\textbf {u}}$ , и напиши ${\textbf {u}}\leq {\textbf {v}}$ в любое время ${\textbf {v}}(i)-{\textbf {u}}(i)\geq 0$ для каждого $i\in E$ (обратите внимание, что это приказ дает $\mathbb {R} _{+}^{E}$ ). Полиматроид на земле $E$ является непустым компактным подмножеством $P$ в $\mathbb {R} _{+}^{E}$ , набор независимых векторов, таких что:

У нас есть это, если ${\textbf {v}}\in P$ , затем ${\textbf {u}}\in P$ для каждого ${\textbf {u}}\leq {\textbf {v}}$ :
Если ${\textbf {u}},{\textbf {v}}\in P$ с $|{\textbf {v}}|>|{\textbf {u}}|$ , то существует вектор ${\textbf {w}}\in P$ такой, что ${\textbf {u}}<{\textbf {w}}\leq (\max\{{\textbf {u}}(1),{\textbf {v}}(1)\},\dots ,\max\{{\textbf {u}}({|E|}),{\textbf {v}}({|E|})\})$ .

Это определение эквивалентно описанному ранее, ^[3] где $f$ это функция, определяемая $f(A)=\max {\Big \{}\sum _{i\in A}{\textbf {v}}(i)~{\Big |}~{\textbf {v}}\in P{\Big \}}$ для каждого $A\subset E$ .

Отношение к матроидам

Каждому матроиду $M$ на земле установлен $E$ мы можем связать набор $V_{M}=\{{\textbf {w}}_{F}~|~F\in {\mathcal {I}}\}$ , где ${\mathcal {I}}$ представляет собой множество независимых множеств $M$ и мы обозначаем через ${\textbf {w}}_{F}$ характеристический вектор $F\subset E$ : для каждого $i\in E$

${\textbf {w}}_{F}(i)={\begin{cases}1,&i\in F;\\0,&i\not \in F.\end{cases}}$

Взяв выпуклую оболочку $V_{M}$ мы получаем полиматроид. Это связано с ранговой функцией $M$ . Условия второго определения отражают аксиомы независимых множеств матроида.

Связь с обобщенными пермутаэдрами

Поскольку обобщенные пермутаэдры могут быть построены из субмодулярных функций, а каждый обобщенный пермутаэдр имеет связанную с ним субмодулярную функцию, мы получаем, что должно существовать соответствие между обобщенными пермутаэдрами и полиматроидами. Фактически каждый полиматроид представляет собой обобщенный пермутаэдр, который был преобразован так, чтобы иметь вершину в начале координат. Этот результат предполагает, что комбинаторная информация полиматроидов совпадает с обобщенными пермутаэдрами.

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

$P_{f}$ непусто тогда и только тогда, когда $f\geq 0$ и это $EP_{f}$ непусто тогда и только тогда, когда $f(\emptyset )\geq 0$ .

Учитывая любой расширенный полиматроид $EP$ существует уникальная субмодульная функция $f$ такой, что $f(\emptyset )=0$ и $EP_{f}=EP$ .

Контраполиматроиды

Для супермодуля f аналогично можно определить контраполиматроид

{\Big \{}w\in \mathbb {R} _{+}^{E}~{\Big |}~\forall S\subseteq E,\sum _{e\in S}w(e)\geq f(S){\Big \}}

Это аналогично обобщает доминанту многогранника остовного множества матроидов.

Дискретные полиматроиды

Когда мы фокусируемся только на точках решетки наших полиматроидов, мы получаем так называемые дискретные полиматроиды . Формально говоря, определение дискретного полиматроида точно такое же, как и для полиматроидов, за исключением того, где будут жить векторы, а не где будут жить векторы. $\mathbb {R} _{+}^{E}$ они будут жить в $\mathbb {Z} _{+}^{E}$ . Этот комбинаторный объект представляет большой интерес из-за его связи с мономиальными идеалами .

Ссылки

Сноски

^ Эдмондс, Джек. Субмодулярные функции, матроиды и некоторые многогранники . 1970. Комбинаторные структуры и их приложения (Proc. Calgary Internat. Conf., Калгари, Альта, 1969), стр. 69–87 Гордон и Брич, Нью-Йорк. МИСТЕР 0270945
^ Шрийвер, Александр (2003), Комбинаторная оптимизация , Springer , §44, с. 767, ISBN 3-540-44389-4
^ Дж.Херцог, Т.Хиби. Мономиальные идеалы . 2011. Тексты для выпускников по математике 260, стр. 237–263 Springer-Verlag, Лондон.

Дополнительное чтение

Ли, Джон (2004), Первый курс комбинаторной оптимизации , Cambridge University Press , ISBN 0-521-01012-8
Фудзисигэ, Сатору (2005), Субмодульные функции и оптимизация , Elsevier , ISBN 0-444-52086-4
Нарайанан, Х. (1997), Субмодулярные функции и электрические сети , ISBN 0-444-82523-1

[edmonds-1] Эдмондс, Джек. Субмодулярные функции, матроиды и некоторые многогранники . 1970. Комбинаторные структуры и их приложения (Proc. Calgary Internat. Conf., Калгари, Альта, 1969), стр. 69–87 Гордон и Брич, Нью-Йорк. МИСТЕР 0270945

[schrijver-2] Шрийвер, Александр (2003), Комбинаторная оптимизация , Springer , §44, с. 767, ISBN 3-540-44389-4

[Herzog-3] Дж.Херцог, Т.Хиби. Мономиальные идеалы . 2011. Тексты для выпускников по математике 260, стр. 237–263 Springer-Verlag, Лондон.

[1]

[2]

[3]