TITLE: On a conjecture of Berge and Simonovits on hypergraph products
SPEAKER: Dhruv Mubayi, University of Illinois, Chicago
WHEN: October 27, 12-1pm
WHERE: Wean Hall 5403
ABSTRACT:
The product of hypergraphs $G$ and $H$ has vertex set equal to the cartesian product of $V(G)$ and $V(H)$, and edge set equal to the set of all cartesian products of edges in $G$ with edges in $H$. We construct a hypergraph sequence $G_n$ for which the chromatic number of $G_n$ approaches infinity, and yet the chromatic number of the product of $G_n$ with itself is $2$. This disproves a conjecture of Berge and Simonovits from the early 70’s. On the other hand, we show that if $G$ and $H$ are hypergraphs with infinite chromatic number and finite edge sizes, then the chromatic number of the product of G and H is also infinite. We also provide a counterexample to a “dual” version of their conjecture, by constructing a graph sequence $G_n$ for which the independence ratio tends to $0$, and yet the independence ratio of the product tends to $1/2$. The constant $1/2$ cannot be replaced by a larger number. The construction is obtained via connections to Ramsey-Turan theory, and addresses a question of Kostochka. We will end with some open problems.
This is joint work with Vojtech Rodl.
