YouTube recording: https://www.youtube.com/watch?v=veVUV1Ti0Wc

Time: Thursday, Mar 2, 3pm EST (8pm GMT, 9am Fri NZDT)
Zoom: https://gatech.zoom.us/j/8802082683

Speaker: Raphael Steiner, ETH Zürich
Title: Coloring hypergraphs with excluded minors

Abstract: Hadwiger’s conjecture, among the most famous open problems in graph theory, states that every graph that does not contain $K_t$ as a minor is properly (t−1)-colorable. The purpose of this work is to demonstrate that a natural extension of Hadwiger’s problem to hypergraph coloring exists, and to derive some first partial results and applications. Generalizing ordinary graph minors to hypergraphs, we say that a hypergraph $H_1$ is a minor of a hypergraph $H_2$, if a hypergraph isomorphic to $H_1$ can be obtained from $H_2$ via a finite sequence of vertex- and hyperedge-deletions, and hyperedge contractions. We first show that a weak extension of Hadwiger’s conjecture to hypergraphs holds true: For every positive integer t, there exists a finite (smallest) integer h(t) such that every hypergraph with no $K_t$-minor is h(t)-colorable, and we prove $$\lceil 3/2(t-1) \rceil \le h(t) \le 2g(t)$$ where g(t) denotes the maximum chromatic number of graphs with no $K_t$-minor. Using the recent result by Delcourt and Postle that $g(t) = O(t \log\log t)$, this yields $h(t) = O(t\log\log t)$. We further conjecture that $h(t) = \lceil 3/2(t-1) \rceil$, i.e., that every hypergraph with no $K_t$-minor is $\lceil 3/2(t-1) \rceil$-colorable for all t, and prove this conjecture for all hypergraphs with independence number at most 2. By considering special classes of hypergraphs, the above additionally has some interesting applications for ordinary graph coloring, such as:
-graphs of chromatic number $Ckt\log\log t$ contain $K_t$-minors with k-edge-connected branch-sets,
-graphs of chromatic number $Cqt\log\log t$ contain $K_t$-minors with modulo-q-connected branch sets,
-by considering cycle hypergraphs of digraphs we recover known results on strong minors in digraphs of large dichromatic number as special cases.