Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
graphs; separoids; homomorphisms; universality; density; Radon’s theorem; oriented matroids; Hedetniemi’s conjecture
graphs; separoids; homomorphisms; universality; density; Radon’s theorem; oriented matroids; Hedetniemi’s conjecture
Summary:
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).
References:
[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. MR 1921560 | Zbl 1002.52008
[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. MR 1226888 | Zbl 0773.52001
[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). MR 1047555 | Zbl 0639.05023
[5] Hell P., Nešetřil J.: Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and its Applications 28, Oxford University Press, 2004. MR 2089014
[6] Hochstättler W., Nešetřil J.: Linear programming duality and morphisms. Comment. Math. Univ. Carolin. 40(3) (1999), 577–592. MR 1732478
[7] Las Vergnas M.: Matroïdes orientables. C. N. R. S. Paris, 1974.
[8] Montellano-Ballesteros J. J., Pór A., Strausz R.: Tverberg-type theorems for separoids. Discrete Comput. Geom. 35 (3) (2006), 513–523. MR 2202117 | Zbl 1091.52500
[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. MR 2050119 | Zbl 1042.05024
[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. MR 1778201 | Zbl 1024.05078
[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. MR 0563525
[13] Radon J.: Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten. Math. Ann. 83 (1921), 113–115. MR 1512002
[14] Strausz R.: Separoides. Situs Ser. B, Universidad Nacional Autónoma de México 5(1998), 36–41.
[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.
Search
Partner of
