## Universality of separoids

##
*Jaroslav Nesetril
and Ricardo Strausz*

**Address.**

Department of Applied Mathematics, and
Institute of Theoretical Computer Science (ITI),
Charles University, Prague

**E-mail. **nesetril@kam.mff.cuni.cz

**E-mail. **strausz@math.unam.mx

**Abstract.**

A {\it separoid\/} is a symmetric relation
$\dagger\subset{2^S\choose2}$ defined on disjoint pairs of subsets
of a given set $S$ such that it is closed as a filter in the
canonical partial order induced by the inclusion (i.e., $A\dagger
B\preceq A'\dagger B'\iff A\subseteq A'$ and $B\subseteq B'$). We
introduce the notion of {\it homomorphism\/} as a map which
preserve the so-called ``minimal Radon partitions'' and show that
separoids, endowed with these maps, admits an embedding from the
category of all finite graphs. This proves that separoids
constitute a {\it countable universal partial order\/}.
Furthermore, by embedding also all hypergraphs (all set systems)
into such a category, we prove a ``stronger'' universality
property.
We further study some structural aspects of the category of separoids.
We completely solve the {\it density\/} problem for (all) separoids as
well as for separoids of points. We also generalise the classic Radon's
theorem in a categorical setting as well as Hedetniemi's product conjecture
(which can be proved for oriented matroids).

**AMSclassification. **05E99, 06A07, 18B99.

**Keywords. **Graphs, separoids, homomorphisms,
universality, density, Radon's theorem, oriented matroids, Hedetniemi's
conjecture.