# Separoid

In mathematics, a separoid is a binary relation between disjoint sets which is stable as an ideal in the canonical order induced by inclusion. 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, and polytopes. 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).

In this general framework, some results and invariants of different categories turn out to be special cases of the same aspect; e.g., the pseudoachromatic number from graph theory and the Tverberg theorem from combinatorial convexity are simply two faces of the same aspect, namely, complete colouring of separoids.

## The axioms

A separoid [2] is a set ${\displaystyle S}$  endowed with a binary relation ${\displaystyle \mid \ \subseteq 2^{S}\times 2^{S}}$  on its power set, which satisfies the following simple properties for ${\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.}$

A related pair ${\displaystyle A\mid B}$  is called a separation and we often say that A is separated from B. It is enough to know the maximal separations to reconstruct the separoid.

A mapping ${\displaystyle \varphi \colon S\to T}$  is a morphism of separoids if the preimages of separations are separations; that is, for ${\displaystyle A,B\subseteq T}$

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

## 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.,

${\displaystyle 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).

## The basic lemma

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

## 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.
• Nešetřil 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.