Universality of separoids

Jaroslav Nešetřil; Ricardo Strausz

Archivum Mathematicum (2006)

  • Volume: 042, Issue: 1, page 85-101
  • ISSN: 0044-8753

Abstract

top
A separoid is a symmetric relation † ⊂ 2 S 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 † B ⪯ A ' † B ' ⇔ A ⊆ A ' and B ⊆ B ' ). 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).

How to cite

top

Nešetřil, Jaroslav, and Strausz, Ricardo. "Universality of separoids." Archivum Mathematicum 042.1 (2006): 85-101. <http://eudml.org/doc/249789>.

@article{Nešetřil2006,
abstract = {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).},
author = {Nešetřil, Jaroslav, Strausz, Ricardo},
journal = {Archivum Mathematicum},
keywords = {graphs; separoids; homomorphisms; universality; density; Radon’s theorem; oriented matroids; Hedetniemi’s conjecture; Radon's theorem; oriented matroids; Hedetniemi's conjecture; separoids; hypergraphs},
language = {eng},
number = {1},
pages = {85-101},
publisher = {Department of Mathematics, Faculty of Science of Masaryk University, Brno},
title = {Universality of separoids},
url = {http://eudml.org/doc/249789},
volume = {042},
year = {2006},
}

TY - JOUR
AU - Nešetřil, Jaroslav
AU - Strausz, Ricardo
TI - Universality of separoids
JO - Archivum Mathematicum
PY - 2006
PB - Department of Mathematics, Faculty of Science of Masaryk University, Brno
VL - 042
IS - 1
SP - 85
EP - 101
AB - 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).
LA - eng
KW - graphs; separoids; homomorphisms; universality; density; Radon’s theorem; oriented matroids; Hedetniemi’s conjecture; Radon's theorem; oriented matroids; Hedetniemi's conjecture; separoids; hypergraphs
UR - http://eudml.org/doc/249789
ER -

References

top
  1. Arocha J. L., Bracho J., Montejano L., Oliveros D., Strausz R., Separoids, their categories and a Hadwiger-type theorem, Discrete Comput. Geom. 27(3) (2002), 377–385. Zbl1002.52008MR1921560
  2. Björner A., Las Vergnas M., Sturmfels B., White N., Ziegler G., Oriented Matroids, Encyclopedia of Mathematics and Its Applications 46, Cambridge University Press, 1993. (1993) Zbl0773.52001MR1226888
  3. Bracho J., Strausz R., Separoids and a characterisation of linear uniform oriented matroids, KAM-DIMATIA Series, Charles University at Prague 17 2002. 
  4. Hell P., Nešetřil J., On the complexity of H-coloring, J. Combin. Theory, Ser. B 48(1) (1990), 92–110. An earlier version appeared in: Combinatorics, graph theory, and computing, Proc. 17th Southeast. Conf., Boca Raton/Fl. 1986, Congr. Numerantium 55, 284 (1986). (1990) Zbl0639.05023MR1047555
  5. Hell P., Nešetřil J., Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and its Applications 28, Oxford University Press, 2004. MR2089014
  6. Hochstättler W., Nešetřil J., Linear programming duality and morphisms, Comment. Math. Univ. Carolin. 40(3) (1999), 577–592. (1999) MR1732478
  7. Las Vergnas M., Matroïdes orientables, C. N. R. S. Paris, 1974. (1974) 
  8. Montellano-Ballesteros J. J., Pór A., Strausz R., Tverberg-type theorems for separoids, Discrete Comput. Geom. 35 (3) (2006), 513–523. Zbl1091.52500MR2202117
  9. Montellano-Ballesteros J. J., Strausz R., A characterisation of cocircuit graphs of uniform oriented matroids, KAM-DIMATIA Series, Charles University at Prague 26 (565), 2002. 
  10. Montellano-Ballesteros J. J., Strausz R., Counting polytopes via the Radon complex, J. Combin. Theory Ser. A 106(1) (2004), 109–121. Zbl1042.05024MR2050119
  11. Nešetřil J., Tardif C., Duality theorems for finite structures (characterising gaps and good characterisations), J. Combin. Theory Ser. B 80(1) (2000), 80–97. Zbl1024.05078MR1778201
  12. Pultr A., Trnková V., Combinatorial, algebraic and topological representations of groups, semigroups and categories, North-Holland Mathematical Library 22, North-Holland Publishing Co., Amsterdam, 1980. (1980) MR0563525
  13. Radon J., Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten, Math. Ann. 83 (1921), 113–115. (1921) MR1512002
  14. Strausz R., Separoides, Situs Ser. B, Universidad Nacional Autónoma de México 5(1998), 36–41. (1998) 
  15. Strausz R., Separoides: el complejo de Radon, Master’s thesis, Universidad Nacional Autónoma de México, 2001. 
  16. Strausz R., On Radon’s theorem and representation of separoids, ITI Series, Charles University at Prague 32 (118), (2003). 
  17. Strausz R., On Separoids, PhD thesis, Universidad Nacional Autónoma de México, 2004. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.