Homotopy and Hom construction in the category of finite hypergraphs. (English) Zbl 1519.05185
Summary: We define notions of a weak homotopy for finite hypergraphs and an exponential hypergraph with a right adjoint to the categorical product of finite hypergraphs, and investigate a connection between the weak homotopy and the exponential hypergraph. Then we discuss a Hom construction associated to a pair of finite hypergraphs and prove that the homotopy of hypergraph homomorphisms, defined in [A. Grigor’yan et al., Topology Appl. 267, Article ID 106877, 25 p. (2019; Zbl 1422.05076)], could be characterized by properties of the Hom construction. In addition, we establish some properties of Hom constructions involving the categorical product of finite hypergraphs. As an application we show that the homotopy of \(d\)-colorings of a simple hypergraph \({\mathcal{H}}\) could be characterized by properties of Hom constructions associated to the maximum simple hypergraph and \({\mathcal{H}}\).
MSC:
| 05C65 | Hypergraphs |
| 55P99 | Homotopy theory |
| 05C15 | Coloring of graphs and hypergraphs |
| 55N35 | Other homology theories in algebraic topology |
Keywords:
Hom construction; homotopy of hypergraphs; exponential hypergraphs; hypergraph homomorphisms; colorings of hypergraphs; maximum simple hypergraphsCitations:
Zbl 1422.05076References:
| [1] | Alexandroff, P.S.: Diskrete Räume. Mathematicheskii Sbornik(N.S.) 2, 501-518 (1937) |
| [2] | Alon, N.; Frankl, P.; Lovász, L., The chromatic number of Kneser hypergraphs, Trans. Am. Math. Soc., 298, 1, 359-370 (1986) · Zbl 0605.05033 · doi:10.1090/S0002-9947-1986-0857448-8 |
| [3] | Björner, A.: Topological Methods. In: Handbook of Combinatorics vol 1. pp. 1819-1872. Elsevier, Amsterdam. (1995) · Zbl 0851.52016 |
| [4] | Babson, E.; Kozlov, DN, Complexes of graph homomorphisms, Israel J. Math., 152, 285-312 (2006) · Zbl 1205.52009 · doi:10.1007/BF02771988 |
| [5] | Babson, E.; Kozlov, DN, Proof of the Lovász conjecture, Ann. Math., 165, 3, 965-1007 (2007) · Zbl 1132.05019 · doi:10.4007/annals.2007.165.965 |
| [6] | Bar-Noy, A., Cheilaris, P., Olonetsky, S., Smorodinsky, S.: Online Conflict-Free Colorings for Hypergraphs. In: Arge L., Cachin C., Jurdziński T., Tarlecki A. (eds) Automata, Languages and Programming. ICALP 2007. Lecture Notes in Computer Science, vol 4596. Springer, Berlin, Heidelberg (2007). doi:10.1007/978-3-540-73420-8_21 · Zbl 1171.05422 |
| [7] | Barmak, JA, Algebraic topology of finite topological spaces and applications (2011), Berlin: Springer, Berlin · Zbl 1235.55001 · doi:10.1007/978-3-642-22003-6 |
| [8] | Breuer, F.; Dall, A.; Kubitzke, M., Hypergraph coloring complexes, Discret. Math., 312, 16, 2407-2420 (2012) · Zbl 1246.05111 · doi:10.1016/j.disc.2012.04.027 |
| [9] | Bressan, S.; Li, J.; Ren, S.; Wu, J., The embedded homology of hypergraphs and applications, Asian J Math, 23, 3, 1-18 (2016) · Zbl 1432.55032 |
| [10] | Caro, Y.; Tuza, Z., Hypergraph coverings and local colorings, J Comb Theory Ser B, 52, 1, 79-85 (1991) · Zbl 0675.05050 · doi:10.1016/0095-8956(91)90092-X |
| [11] | Dörfler, W.; Waller, DA, A category-theoretical approach to hypergraphs, Arch. Math., 34, 1, 185-192 (1980) · Zbl 0415.05040 · doi:10.1007/BF01224952 |
| [12] | Dochtermann, A., Hom complexes and homotopy theory in the category of graphs, Eur. J. Comb., 30, 490-509 (2009) · Zbl 1167.05017 · doi:10.1016/j.ejc.2008.04.009 |
| [13] | Dochtermann, A., Homotopy groups of Hom complexes of graphs, J Comb Theory Ser A, 116, 1, 180-194 (2009) · Zbl 1193.05088 · doi:10.1016/j.jcta.2008.06.001 |
| [14] | Francisco, CA; Hà, HT; Tuyl, AV, Colorings of hypergraphs, perfect graphs, and associated primes of powers of monomial ideals, J. Algebra, 331, 1, 224-242 (2009) · Zbl 1227.13016 · doi:10.1016/j.jalgebra.2010.10.025 |
| [15] | Ghosh, P.; Pal, A., Coloring of hypergraphs, J Math Inf, 8, 37-44 (2017) · doi:10.22457/jmi.v8a5 |
| [16] | Grigor’Yan, A.; Jimenez, R.; Muranov, Y.; Yau, ST, Homology of path complexes and hypergraphs, Topol Appl, 267 (2019) · Zbl 1422.05076 · doi:10.1016/j.topol.2019.106877 |
| [17] | Hellmuth, M.; Ostermeier, L.; Stadler, PF, A survey on hypergraph products, Math. Comput. Sci., 6, 1-32 (2012) · Zbl 1262.05110 · doi:10.1007/s11786-012-0109-6 |
| [18] | Iriye, K.; Kishimoto, D., Hom complexes and hypergraph colorings, Topol Appl, 160, 12, 1333-1344 (2013) · Zbl 1283.05103 · doi:10.1016/j.topol.2013.05.002 |
| [19] | Jonsson, J.: Simplicial Complexes of Graphs. Lecture Notes in Mathematics, vol. 192. Springer-Verlag, Berlin (2008) · Zbl 1152.05001 |
| [20] | Kozlov, D.N.: Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes (2005). doi:10.48550/arXiv:math/0505563 · Zbl 1139.05022 |
| [21] | Kozlov, DN, Simple homotopy types of Hom-complexes, neighborhood complexes, Lovász complexes, and atom crosscut complexes, Topol Appl., 153, 14, 2445-2454 (2006) · Zbl 1105.57021 · doi:10.1016/j.topol.2005.09.005 |
| [22] | Kozlov, DN, Combinatorial algebraic topology. Algorithms and computation in mathematics (2008), Berlin: Springer, Berlin · Zbl 1130.55001 |
| [23] | Lange, C.: On generalised Kneser colourings. Mathematics (2003) |
| [24] | Mirzakhani, M.,Vondrák, J.: Sperner’s Colorings, Hypergraph Labeling Problems and Fair Division. Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015, 873-886 (2015) · Zbl 1371.05094 |
| [25] | Matsushita, T., Morphism complexes of sets with relations, Osaka J. Math., 53, 267-283 (2016) · Zbl 1345.55004 |
| [26] | Matsushita, T., Box complexes and homotopy theory of graphs, Homol Homot Appl, 19, 2, 175-197 (2017) · Zbl 1400.55010 · doi:10.4310/HHA.2017.v19.n2.a10 |
| [27] | Matsushita, T., Homotopy types of the Hom complexes of graphs, Eur. J. Comb., 63, 2017, 216-226 (2017) · Zbl 1365.05096 · doi:10.1016/j.ejc.2017.03.009 |
| [28] | Singh, A.: Hom complexes of graphs of diameter 1(2019). doi:10.48550 / arXiv:1807.10498 |
| [29] | Thansri, T., simple \(\Sigma_r\)-homotopy types of Hom complexes and box complexes assigned to \(r\)-graphs, Kyushu J Math, 2012, 66, 493-508 (2012) · Zbl 1258.05088 · doi:10.2206/kyushujm.66.493 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
