Separoid

From Wikipedia, the free encyclopedia

 This article or section includes a list of references or external links, but its sources remain unclear because it lacks in-text citations.
You can improve this article by introducing more precise citations.

In mathematics, a separoid is a relation defined in pairs of disjoint sets which is stable as an ideal in the canonical order induced by the contention. Many mathematical objects which appear to be quite different, find a common generalisation in the framework of separoids; e.g., graphs, configurations of convex sets, oriented matroids, polytopes, to mention just a few. Indeed, any countable category is an induced subcategory of separoids when they are endowed with homomorphisms [1] (viz., mappings that preserve the so-called minimal Radon partitions).

Contents

[edit] The axioms

A separoid [2] is a set S endowed with a symmetric relation \mid\ \subseteq{2^S\choose2} defined in its power set, which satisfies the following simple properties for A,B\subseteq S:

\bullet\qquad A\mid B\Rightarrow A\cap B=\varnothing,
\bullet\qquad A\mid B \hbox{ and } A'\subset A\Rightarrow A'\mid B.

A related pair A\mid B is called a separation and we often say that A is separated from B. Clearly, it is enough to know the maximal separations to reconstruct the separoid.

A mapping \varphi\colon S\to T is a morphism of separoids if the preimage of separations are separations; that is, for A,B\subseteq T

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

[edit] Examples

Examples of separoids can be found in almost every branch of mathematics. Here we list just a few.

1. Given a graph G=(V,E), we can define a separoid on its vertices by saying that two (disjoint) subsets of V, say A and B, are separated if there are no edges going from one to the other; i.e.,

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

2. Given an oriented matroid [3] M = (E,T), given in terms of its topes T, we can define a separoid on E by saying that two subsets are separated if they are contained in opposite signs of a tope. In other words, the topes of an oriented matroid are the maximal separations of a separoid. This example includes, of course, all directed graphs.

3. Given a family of objects in an Euclidean space, we can define a separoid in it by saying that two subsets are separated if there exists a hyperplane that separates them; i.e., leaving them in the two opposite sides of it.

4. Given a topological space, we can define a separoid saying that two subsets are separated if there exist two disjoint open sets which contains them (one for each of them).

[edit] The basic lemma

Every separoid can be represented with a family of convex sets in some Euclidean space and their separations by hyperplanes.

[edit] References

  • Strausz Ricardo; "Separoides". Situs, serie B, no. 5 (1998), Universidad Nacional Autónoma de México.
  • Arocha Jorge Luis, Bracho Javier, Montejano Luis, Oliveros Deborah, Strausz Ricardo; "Separoids, their categories and a Hadwiger-type theorem for transversals". Discrete and Computational Geometry 27 (2002), no. 3, 377--385.
  • Strausz Ricardo; "Separoids and a Tverberg-type problem". Geombinatorics 15 (2005), no. 2, 79--92.
  • Montellano-Ballesteros Juan Jose, Por Attila, Strausz Ricardo; "Tverberg-type theorems for separoids". Discrete and Computational Geometry 35 (2006), no.3, 513--523.
  • Nesetril Jaroslav, Strausz Ricardo; "Universality of separoids". Archivum Mathematicum (Brno) 42 (2006), no. 1, 85--101.
  • Bracho Javier, Strausz Ricardo; "Two geometric representations of separoids". Periodica Mathematica Hungarica 53 (2006), no. 1-2, 115--120.
  • Strausz Ricardo; "Homomorphisms of separoids". 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, 461--468, Electronic Notes on Discrete Mathematics 28, Elsevier, Amsterdam, 2007.
  • Strausz Ricardo; "Edrös-Szekeres 'happy end'-type theorems for separoids". European Journal of Combinatorics 29 (2008), no. 4, 1076--1085.