Сепароид

В математике сепароид — это бинарное отношение между непересекающимися множествами , которое устойчиво как идеал в каноническом порядке, индуцированном включением . Многие математические объекты, которые кажутся совершенно разными, находят общее обобщение в рамках сепароидов; например, графы , конфигурации выпуклых множеств , ориентированные матроиды и многогранники . Любая счетная категория является индуцированной подкатегорией сепароидов, если они наделены гомоморфизмами. ^[1] (а именно отображения, сохраняющие так называемые минимальные разбиения Радона ).

В этой общей схеме некоторые результаты и инварианты разных категорий оказываются частными случаями одного и того же аспекта; например, псевдоахроматическое число из теории графов и теорема Тверберга из комбинаторной выпуклости — это просто две грани одного и того же аспекта, а именно полной раскраски сепароидов.

Аксиомы

Сепароид ^[2] это набор $S$ наделенный бинарным отношением $\mid \ \subseteq 2^{S}\times 2^{S}$ на своем наборе степеней , который удовлетворяет следующим простым свойствам для $A,B\subseteq S$ :

A\mid B\Leftrightarrow B\mid A,

A\mid B\Rightarrow A\cap B=\varnothing ,

A\mid B{\hbox{ and }}A'\subset A\Rightarrow A'\mid B.

Родственная пара $A\mid B$ называется разделением , и мы часто говорим, что A отделено от B. Достаточно знать максимальные расстояния, чтобы восстановить сепароид.

Отображение $\varphi \colon S\to T$ является морфизмом сепароидов, если прообразы разделений являются разделениями; то есть для $A,B\subseteq T$

A\mid B\Rightarrow \varphi ^{-1}(A)\mid \varphi ^{-1}(B).

Примеры

Примеры сепароидов можно найти практически во всех разделах математики . ^[3]^[4]^[5] Здесь мы перечислим лишь некоторые из них.

1. Учитывая граф G=(V,E), мы можем определить сепароид в его вершинах , сказав, что два (непересекающихся) подмножества V, скажем A и B, разделены, если нет ребер, идущих из одного в другое. ; то есть,

A\mid B\Leftrightarrow \forall a\in A{\hbox{ and }}b\in B\colon ab\not \in E.

2. Дан ориентированный матроид. ^[5] M = ( E , T ), заданный через его топы T , мы можем определить сепароид на E , сказав, что два подмножества разделены, если они содержатся в противоположных знаках топа. Другими словами, вершины ориентированного матроида — это максимальные разделения сепароида. В этот пример входят, конечно же, все ориентированные графы .

3. Учитывая семейство объектов в евклидовом пространстве , мы можем определить в нем сепароид, сказав, что два подмножества разделены, если существует гиперплоскость , разделяющая их ; т. е. оставив их в двух противоположных его сторонах.

4. Учитывая топологическое пространство , мы можем определить сепароид, говоря, что два подмножества разделены, если существуют два непересекающихся открытых множества , которые их содержат (по одному для каждого из них).

Основная лемма

Каждый сепароид можно представить семейством выпуклых множеств в некотором евклидовом пространстве и их разделением гиперплоскостями.

Ссылки

^ Штраус, Рикардо (1 марта 2007 г.). «Гомоморфизмы сепароидов». Электронные заметки по дискретной математике . 28 : 461–468. дои : 10.1016/j.endm.2007.01.064 . Збл 1291.05036 .
^ Штраус, Рикардо (2005). «Сепароиды и проблема типа Тверберга». Геомбинаторика . 15 (2): 79–92. Збл 1090.52005 .
^ Ароча, Хорхе Луис; Брачо, Хавьер; Монтехано, Луис; Оливерос, Дебора ; Штраус, Рикардо (2002). «Сепароиды, их категории и теорема типа Хадвигера для трансверсалей» . Дискретная и вычислительная геометрия . 27 (3): 377–385. дои : 10.1007/s00454-001-0075-2 .
^ Нешетрил, Ярослав ; Штраус, Рикардо (2006). «Универсальность сепароидов» (PDF) . Архивум Математикум (Брно) . 42 (1): 85–101.
^ Jump up to: ^а ^б Монтеллано-Баллестерос, Хуан Хосе; Штраус, Рикардо (июль 2006 г.). «Характеристика косхемных графов однородно ориентированных матроидов» . Журнал комбинаторной теории . Серия Б. 96 (4): 445–454. дои : 10.1016/j.jctb.2005.09.008 . Збл 1109.52016 .

Дальнейшее чтение

Штраус, Рикардо (1998). «Сепароиды». Ситус, Серия B, №5 . Национальный автономный университет Мексики.
Монтеллано-Баллестерос, Хуан Хосе; Пор, Аттила; Штраус, Рикардо (2006). «Теоремы типа Тверберга для сепароидов» . Дискретная и вычислительная геометрия . 35 (3): 513–523. дои : 10.1007/s00454-005-1229-4 .
Брачо, Хавьер; Штраус, Рикардо (2006). «Два геометрических представления сепароидов» . Периодика Математика Венгерка . 53 (1–2): 115–120. дои : 10.1007/s10998-006-0025-0 .
Штраус, Рикардо (2008). «Теоремы Эрдеша-Секереша типа «счастливый конец» для сепароидов» . Европейский журнал комбинаторики . 29 (4): 1076–1085. дои : 10.1016/j.ejc.2007.11.011 .

[1] Штраус, Рикардо (1 марта 2007 г.). «Гомоморфизмы сепароидов». Электронные заметки по дискретной математике . 28 : 461–468. дои : 10.1016/j.endm.2007.01.064 . Збл 1291.05036 .

[2] Штраус, Рикардо (2005). «Сепароиды и проблема типа Тверберга». Геомбинаторика . 15 (2): 79–92. Збл 1090.52005 .

[3] Ароча, Хорхе Луис; Брачо, Хавьер; Монтехано, Луис; Оливерос, Дебора ; Штраус, Рикардо (2002). «Сепароиды, их категории и теорема типа Хадвигера для трансверсалей» . Дискретная и вычислительная геометрия . 27 (3): 377–385. дои : 10.1007/s00454-001-0075-2 .

[4] Нешетрил, Ярослав ; Штраус, Рикардо (2006). «Универсальность сепароидов» (PDF) . Архивум Математикум (Брно) . 42 (1): 85–101.

[M-BS-5] Jump up to: ^а ^б Монтеллано-Баллестерос, Хуан Хосе; Штраус, Рикардо (июль 2006 г.). «Характеристика косхемных графов однородно ориентированных матроидов» . Журнал комбинаторной теории . Серия Б. 96 (4): 445–454. дои : 10.1016/j.jctb.2005.09.008 . Збл 1109.52016 .

[1]

[2]

[3]

[4]

[5]