mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, a separoid is a

binary relation In mathematics, a binary relation associates some elements of one Set (mathematics), set called the ''domain'' with some elements of another set called the ''codomain''. Precisely, a binary relation over sets X and Y is a set of ordered pairs ...

between

disjoint sets In set theory in mathematics and Logic#Formal logic, formal logic, two Set (mathematics), sets are said to be disjoint sets if they have no element (mathematics), element in common. Equivalently, two disjoint sets are sets whose intersection (se ...

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 set In geometry, a set of points is convex if it contains every line segment between two points in the set. For example, a solid cube (geometry), cube is a convex set, but anything that is hollow or has an indent, for example, a crescent shape, is n ...

s, oriented matroids, and

polytopes In elementary geometry, a polytope is a geometric object with Flat (geometry), flat sides (''Face (geometry), faces''). Polytopes are the generalization of three-dimensional polyhedron, polyhedra to any number of dimensions. Polytopes may exist ...

. Any countable

category Category, plural categories, may refer to: General uses *Classification, the general act of allocating things to classes/categories Philosophy * Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) * Category ( ...

is an induced subcategory of separoids when they are endowed with

homomorphism In algebra, a homomorphism is a morphism, structure-preserving map (mathematics), map between two algebraic structures of the same type (such as two group (mathematics), groups, two ring (mathematics), rings, or two vector spaces). The word ''homo ...

s (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 is a

set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...

S

endowed with a binary relation

\mid\ \subseteq2^S\times2^S

on its

power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...

, which satisfies the following simple properties for

A,B\subseteq S

: :

A\mid B\Leftrightarrow B\mid A,

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

A\mid B \hbox 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''. It is enough to know the ''maximal'' separations to reconstruct the separoid. A mapping

\varphi\colon S\to T

is a

morphism In mathematics, a morphism is a concept of category theory that generalizes structure-preserving maps such as homomorphism between algebraic structures, functions from a set to another set, and continuous functions between topological spaces. Al ...

of separoids if the preimages of separations are separations; that is, for

A,B\subseteq T

A\mid B\Rightarrow\varphi^(A)\mid\varphi^(B).

Examples

Examples of separoids can be found in almost every branch of

. 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\hboxb\in B\colon ab\not\in E.

2. Given an oriented matroid ''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 a

Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...

, we can define a separoid in it by saying that two subsets are separated if there exists a

hyperplane In geometry, a hyperplane is a generalization of a two-dimensional plane in three-dimensional space to mathematical spaces of arbitrary dimension. Like a plane in space, a hyperplane is a flat hypersurface, a subspace whose dimension is ...

that ''separates'' them; i.e., leaving them in the two opposite sides of it. 4. Given a

topological space In mathematics, a topological space is, roughly speaking, a Geometry, geometrical space in which Closeness (mathematics), closeness is defined but cannot necessarily be measured by a numeric Distance (mathematics), distance. More specifically, a to ...

, we can define a separoid saying that two subsets are separated if there exist two disjoint

open set In mathematics, an open set is a generalization of an Interval (mathematics)#Definitions_and_terminology, open interval in the real line. In a metric space (a Set (mathematics), set with a metric (mathematics), distance defined between every two ...

s 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.

The axioms

Examples

The basic lemma

References

Further reading