Universality of separoids

Nešetřil, Jaroslav ; Strausz, Ricardo

Archivum mathematicum, Tome 42 (2006) no. 1, pp. 85-101

Résumé

A separoid is a symmetric relation $\dagger \subset {2^S\atopwithdelims ()2}$ 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^{\prime }\dagger B^{\prime }\iff A\subseteq A^{\prime }$ and $B\subseteq B^{\prime }$). We introduce the notion of 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 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 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).

Détail

Classification : 05B35
Keywords: graphs; separoids; homomorphisms; universality; density; Radon’s theorem; oriented matroids; Hedetniemi’s conjecture