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.