Speaker: Dömötör Pálvölgyi
Title: Coloring Fat Hypergraphs
Abstract: A hypergraph is m-fat if each edge contains at least m vertices.
A k-coloring of the vertices of a hypergraph is proper, if no edge is monochromatic, and it is polychromatic, if every edge contains all k colors.
I will mainly talk about colorings of fat geometric hypergraphs, defined by incidences between points and geometric shapes.
For example, the vertices of a pt/disk hypergraph are some planar points, and its edges are the points that are contained in some disk.
The newest result (joint work with Damasdi) is that there is an arbitrarily fat pt/disk hypergraph that is not proper 3-colorable.
It is an easy exercise to show that every pt/disk hypergraph is 4-colorable, while it is a result of Pach-Tardos-Toth that some are not 2-colorable.
An abstract hypergraph family is monotone if it is closed for taking partial subhypergraphs.
Berge proved that for a monotone hypergraph family if its 2-fat members are 2-colorable, then its k-fat members are polychromatic k-colorable.
But what happens if we only know that its 3-fat members are 2-colorable?