Dömötör Pálvölgyi: 666-uniform Unit Disk Hypergraphs are 3-colorable

Description of video

Date: 9/24/21
Speaker :Pálvölgyi Dömötör

Abstract: I will present some new tricks about coloring geometric hypergraphs that we have developed with Gabor Damasdi. These will allow us to show that any finite set of planar points can be 3-colored such that any unit disk containing at least 666 points contains two differently colored points. Earlier it was known that 2 colors are not always sufficient and that for (non-unit) disks sometimes even 4 colors are needed. Our proof uses a generalization of the Erdos-Sands-Sauer-Woodrow conjecture. If time permits, I'll also sketch our proof for this generalization, which builds on the recent proof of the original ESSW conjecture of Bousquet, Lochet, and Thomasse.