Separoid

Quality 0.50 · 0 views · Updated 2 months ago

Relation on disjoint pairs of sets

title: "Separoid" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["binary-relations"] description: "Relation on disjoint pairs of sets" topic_path: "general/binary-relations" source: "https://en.wikipedia.org/wiki/Separoid" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Relation on disjoint pairs of sets ::

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{{cite journal | last1=Strausz | first1=Ricardo | title=Homomorphisms of separoids | journal=Electronic Notes in Discrete Mathematics | volume=28 | date=1 March 2007 | pages=461–468 | doi=10.1016/j.endm.2007.01.064 | zbl=1291.05036}} (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{{cite journal | last1=Strausz | first1=Ricardo | title=Separoids and a Tverberg-type problem | journal=Geombinatorics | volume=15 | year=2005 | issue=2 | pages=79–92 | zbl=1090.52005}} is a set S endowed with a binary relation \mid\ \subseteq2^S\times2^S on its power set, 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{ 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. 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 preimages of separations are separations; that is, for A,B\subseteq T

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

Examples

Examples of separoids can be found in almost every branch of mathematics.{{cite journal | last1=Arocha | first1=Jorge Luis | last2=Bracho | first2=Javier | last3=Montejano | first3=Luis | last4=Oliveros | first4=Deborah | author4-link = Déborah Oliveros | last5=Strausz | first5=Ricardo | title=Separoids, their categories and a Hadwiger-type theorem for transversals | journal=Discrete and Computational Geometry | volume=27 | year=2002 | issue=3 | pages=377–385 | doi=10.1007/s00454-001-0075-2 | doi-access=free}}{{cite journal | last1=Nešetřil | first1=Jaroslav | authorlink1=Jaroslav Nešetřil | last2=Strausz | first2=Ricardo | title=Universality of separoids | journal=Archivum Mathematicum (Brno) | volume=42 | year=2006 | issue=1 | pages=85–101 | url=https://www.emis.de/journals/AM/06-1/neset1.pdf}}{{cite journal | last1=Montellano-Ballesteros | first1=Juan José | last2=Strausz | first2=Ricardo | title=A characterization of cocircuit graphs of uniform oriented matroids | journal=Journal of Combinatorial Theory | series=Series B | volume=96 | issue=4 | date=July 2006 | pages=445–454 | doi=10.1016/j.jctb.2005.09.008 | doi-access=free | zbl=1109.52016}} 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.

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

  2. Given a family of objects in a 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.

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

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::

binary-relations