Abstract
This paper is devoted to studying a topological version of the famous Hedetniemi conjecture which says: The Z/2-index of the Cartesian product of two Z/2-spaces is equal to the minimum of their Z/2-indexes. We fully confirm the version of this conjecture for the homological index via establishing a stronger formula for the homological index of the join of Z/2-spaces. Moreover, we confirm the original conjecture for the case when one of the factors is an n-sphere. In particular, we answer a question about computing the index of some non-trivial products, raised by Marcin Wrochna. There is a generalization of Hedetniemi's conjecture for hypergraphs by Xuding Zhu. The surprising counterexample of the Hedetniemi conjecture which has been found very recently by Yaroslav Shitov shows that Hedetniemi's conjecture, and hence its generalization, only can be valid under additional assumptions. To approach Zhu's conjecture, we establish a topological lower bound for the chromatic number of the categorical product of hypergraphs. Consequently, we enrich the family of known hypergraphs satisfying Zhu's conjecture. In particular, this leads to a new proof for the fact that Zhu's conjecture is valid for the usual Kneser r-hypergraphs which has been established recently by Hossein Hajiabolhassan and Frédéric Meunier as a first non-trivial example of hypergraphs satisfying Zhu's conjecture.
Original language | English |
---|---|
Article number | 105721 |
Journal | Journal of Combinatorial Theory - Series A |
Volume | 195 |
DOIs | |
Publication status | Published - Apr 2023 |
Keywords
- Chromatic number
- Equivariant maps
- Hedetniemi's conjecture
- Homological index
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics