Separoid

Last updated November 29, 2022

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 $S$ endowed with a binary relation $\mid \ \subseteq 2^{S}\times 2^{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.^[3]^[4]^[5] 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^[5]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, 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.

Related Research Articles

In topology and related branches of mathematics, a normal space is a topological space X that satisfies Axiom T₄: every two disjoint closed sets of X have disjoint open neighborhoods. A normal Hausdorff space is also called a T₄ space. These conditions are examples of separation axioms and their further strengthenings define completely normal Hausdorff spaces, or T₅ spaces, and perfectly normal Hausdorff spaces, or T₆ spaces.

In mathematical logic, the compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of it has a model. This theorem is an important tool in model theory, as it provides a useful method for constructing models of any set of sentences that is finitely consistent.

In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox. Today, Zermelo–Fraenkel set theory, with the historically controversial axiom of choice (AC) included, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics. Zermelo–Fraenkel set theory with the axiom of choice included is abbreviated ZFC, where C stands for "choice", and ZF refers to the axioms of Zermelo–Fraenkel set theory with the axiom of choice excluded.

In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite matroid is equivalent to a geometric lattice.

In mathematical analysis, a function of bounded variation, also known as $BV$ function, is a real-valued function whose total variation is bounded (finite): the graph of a function having this property is well behaved in a precise sense. For a continuous function of a single variable, being of bounded variation means that the distance along the direction of the $y$ -axis, neglecting the contribution of motion along $x$ -axis, traveled by a point moving along the graph has a finite value. For a continuous function of several variables, the meaning of the definition is the same, except for the fact that the continuous path to be considered cannot be the whole graph of the given function, but can be every intersection of the graph itself with a hyperplane parallel to a fixed $x$ -axis and to the $y$ -axis.

In the mathematical field of measure theory, an outer measure or exterior measure is a function defined on all subsets of a given set with values in the extended real numbers satisfying some additional technical conditions. The theory of outer measures was first introduced by Constantin Carathéodory to provide an abstract basis for the theory of measurable sets and countably additive measures. Carathéodory's work on outer measures found many applications in measure-theoretic set theory, and was used in an essential way by Hausdorff to define a dimension-like metric invariant now called Hausdorff dimension. Outer measures are commonly used in the field of geometric measure theory.

In combinatorics, a greedoid is a type of set system. It arises from the notion of the matroid, which was originally introduced by Whitney in 1935 to study planar graphs and was later used by Edmonds to characterize a class of optimization problems that can be solved by greedy algorithms. Around 1980, Korte and Lovász introduced the greedoid to further generalize this characterization of greedy algorithms; hence the name greedoid. Besides mathematical optimization, greedoids have also been connected to graph theory, language theory, order theory, and other areas of mathematics.

In mathematics, specifically in operator theory, each linear operator $on a Euclidean vector space defines a Hermitian adjoint operator on that space according to the rule$

In mathematics, the total variation identifies several slightly different concepts, related to the structure of the codomain of a function or a measure. For a real-valued continuous function f, defined on an interval [a, b] ⊂ R, its total variation on the interval of definition is a measure of the one-dimensional arclength of the curve with parametric equation x ↦ f(x), for x ∈ [a, b]. Functions whose total variation is finite are called functions of bounded variation.

In the mathematical theory of matroids, a graphic matroid is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids. A matroid that is both graphic and co-graphic is sometimes called a planar matroid ; these are exactly the graphic matroids formed from planar graphs.

In geometry, Radon's theorem on convex sets, published by Johann Radon in 1921, states that any set of d + 2 points in R^d can be partitioned into two sets whose convex hulls intersect. A point in the intersection of these convex hulls is called a Radon point of the set.

In additive combinatorics, Freiman's theorem is a central result which indicates the approximate structure of sets whose sumset is small. It roughly states that if $is small, then can be contained in a small generalized arithmetic progression.$

In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations that are defined on it.

In mathematics, in particular in measure theory, an inner measure is a function on the power set of a given set, with values in the extended real numbers, satisfying some technical conditions. Intuitively, the inner measure of a set is a lower bound of the size of that set.

In topology, a branch of mathematics, the ends of a topological space are, roughly speaking, the connected components of the "ideal boundary" of the space. That is, each end represents a topologically distinct way to move to infinity within the space. Adding a point at each end yields a compactification of the original space, known as the end compactification.

In algebraic geometry, Mnëv's universality theorem is a result which can be used to represent algebraic varieties as realizations of oriented matroids, a notion of combinatorics.

An oriented matroid is a mathematical structure that abstracts the properties of directed graphs, vector arrangements over ordered fields, and hyperplane arrangements over ordered fields. In comparison, an ordinary matroid abstracts the dependence properties that are common both to graphs, which are not necessarily directed, and to arrangements of vectors over fields, which are not necessarily ordered.

In matroid theory, a field within mathematics, a gammoid is a certain kind of matroid, describing sets of vertices that can be reached by vertex-disjoint paths in a directed graph.

A geometric separator is a line that partitions a collection of geometric shapes into two subsets, such that proportion of shapes in each subset is bounded, and the number of shapes that do not belong to any subset is small.

A sparsity matroid is a mathematical structure that captures how densely a multigraph is populated with edges. To unpack this a little, sparsity is a measure of density of a graph that bounds the number of edges in any subgraph. The property of having a particular matroid as its density measure is invariant under graph isomorphisms and so it is a graph invariant.

References

↑ Strausz, Ricardo (1 March 2007). "Homomorphisms of separoids". Electronic Notes in Discrete Mathematics. 28: 461–468. doi:10.1016/j.endm.2007.01.064. Zbl 1291.05036.
↑ Strausz, Ricardo (2005). "Separoids and a Tverberg-type problem". Geombinatorics . 15 (2): 79–92. Zbl 1090.52005.
↑ Arocha, Jorge Luis; Bracho, Javier; Montejano, Luis; Oliveros, Deborah; Strausz, Ricardo (2002). "Separoids, their categories and a Hadwiger-type theorem for transversals". Discrete and Computational Geometry . 27 (3): 377–385. doi: 10.1007/s00454-001-0075-2 .
↑ Nešetřil, Jaroslav; Strausz, Ricardo (2006). "Universality of separoids" (PDF). Archivum Mathematicum (Brno). 42 (1): 85–101.
1 2 Montellano-Ballesteros, Juan José; Strausz, Ricardo (July 2006). "A characterization of cocircuit graphs of uniform oriented matroids". Journal of Combinatorial Theory . Series B. 96 (4): 445–454. doi: 10.1016/j.jctb.2005.09.008 . Zbl 1109.52016.