Hedetniemi's conjecture from the topological viewpoint

Hamid Reza Daneshpajouh, Roman Karasev, Alexey Volovikov

Research output: Journal PublicationArticlepeer-review

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 languageEnglish
Article number105721
JournalJournal of Combinatorial Theory - Series A
Volume195
DOIs
Publication statusPublished - 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

Fingerprint

Dive into the research topics of 'Hedetniemi's conjecture from the topological viewpoint'. Together they form a unique fingerprint.

Cite this