Separoid - Separoid

V matematiky , je separoid je binární relace mezi disjunktních množin , který je stabilní za ideální v kanonickém pořadí vyvolané začlenění . Mnoho matematických objektů, které se zdají být zcela odlišné, nachází společné zobecnění v rámci separoidů; např. grafy , konfigurace konvexních množin , orientovaných matroidů a polytopů . Jakákoli spočítatelná kategorie je indukovanou podkategorií separoidů, pokud jsou vybaveny homomorfismy (tj. Mapováním , které zachovává takzvané minimální oddíly radonu ).

V tomto obecném rámci se některé výsledky a invarianty různých kategorií ukázaly jako zvláštní případy stejného aspektu; např. pseudoachromatické číslo z teorie grafů a Tverbergova věta z kombinatorické konvexnosti jsou jednoduše dvě tváře stejného aspektu, konkrétně úplné zabarvení separoidů.

Axiomy

Separoid je sada obdařen binární relace na jeho elektrického souboru , který splňuje tyto jednoduché vlastnosti pro : ${\ displaystyle S}$${\ Displaystyle \ mid \ \ subseteq 2^{S} \ times 2^{S}}$${\ displaystyle A, B \ subseteq S}$

${\ Displaystyle A \ mid B \ Leftrightarrow B \ mid A,}$

${\ Displaystyle A \ mid B \ Rightarrow A \ cap B = \ varnothing,}$

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

Příbuzný pár se nazývá oddělovací a často říkáme, že A je oddělena od B . K rekonstrukci separoidu stačí znát maximální separace. ${\ displaystyle A \ mid B}$

Mapping je morphism z separoids pokud nalezení multivzorů separace jsou výtažky; tedy pro${\ Displaystyle \ varphi \ colon S \ to T}$${\ displaystyle A, B \ subseteq T}$

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

Příklady

Příklady separoidů lze nalézt téměř v každém oboru matematiky . Zde uvádíme jen několik.

1. Vzhledem k grafu G = (V, E) můžeme na jeho vrcholech definovat separoid tím, že řekneme, že dvě (disjunktní) podmnožiny V, řekněme A a B, jsou odděleny, pokud z jedné do druhé nevedou žádné hrany ; tj,

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

2. Vzhledem k orientovanému matroidu M = ( E , T ), danému jeho vrcholy T , můžeme definovat separoid na E tím, že dvě podmnožiny jsou odděleny, pokud jsou obsaženy v opačných znacích vrcholu. Jinými slovy, vrcholy orientovaného matroidu jsou maximální separace separoidu. Tento příklad samozřejmě zahrnuje všechny směrované grafy .

3. Vzhledem k rodině objektů v euklidovském prostoru můžeme definovat separoid v něm tím, že řekneme, že dvě podmnožiny jsou odděleny, pokud existuje hyperplane, která je odděluje ; tj. nechat je na dvou protilehlých stranách.

4. Vzhledem k topologickému prostoru můžeme definovat separoid, který říká, že jsou odděleny dvě podmnožiny, pokud existují dvě nesouvislé otevřené množiny, které je obsahují (pro každou z nich jednu).

Základní lemma

Každý separoid může být reprezentován skupinou konvexních množin v nějakém euklidovském prostoru a jejich separacemi hyperplanes.

Reference

Další čtení

• Strausz, Ricardo (1998). „Separoides“. Situs, řada B, č. 5 . Universidad Nacional Autónoma de México.
• Montellano-Ballesteros, Juan José; Por, Attila; Strausz, Ricardo (2006). „Věty Tverbergova typu pro separoidy“ . Diskrétní a výpočetní geometrie . 35 (3): 513–523. doi : 10,1007/s00454-005-1229-4 .
• Bracho, Javier; Strausz, Ricardo (2006). „Dvě geometrická znázornění separoidů“ . Periodica Mathematica Hungarica . 53 (1–2): 115–120. doi : 10,1007/s10998-006-0025-0 .
• Strausz, Ricardo (2008). „Erdös-Szekeresovy věty o šťastném konci pro separoidy“ . Evropský žurnál kombinatoriky . 29 (4): 1076–1085. doi : 10.1016/j.ejc.2007.11.011 .