On the chromatic number and independence number of hypergraph products

The hypergraph product G □ H has vertex set V ( G ) × V ( H ) , and edge set { e × f : e ∈ E ( G ) , f ∈ E ( H ) } , where × denotes the usual Cartesian product of sets. We construct a hypergraph sequence { G n } for with χ ( G n ) → ∞ and χ ( G n □ G n ) = 2 for all n. This disproves a conjecture of Berge and Simonovits [C. Berge, M. Simonovits, The coloring numbers of the direct product of two hypergraphs, in: Hypergraph Seminar, Proc. First Working Sem., Ohio State Univ., Columbus, OH, 1972; Dedicated to Arnold Ross, in: Lecture Notes in Math., vol. 411, Springer, Berlin, 1974, pp. 21–33]. On the other hand, we show that if G and H are hypergraphs with infinite chromatic number, then the chromatic number of G □ H is also infinite. o provide a counterexample to a “dual” version of their conjecture, by constructing a graph sequence { G n } with α ( G n ) / | V ( G n ) | → 0 and α ( G n □ G n ) / | V ( G n ) | 2 → 1 / 2 . The constant 1/2 cannot be replaced by a larger number.