Freddie Illingworth

University of Oxford


Defective colouring of hypergraphs


Combinatorics Seminar


25th October 2022, 11:00 am – 12:00 pm
Fry Building, 2.04


Erdös and Lovász originally proved the local lemma to show that every (r + 1)-uniform hypergraph G with maximum degree Δ has chromatic number O(Δ^(1/r)). We prove the following generalisation of this result. A d-defective colouring of a hypergraph is a vertex-colouring in which every vertex is in at most d monochromatic edges (so d = 0 is exactly a proper colouring). We prove that every (r + 1)-uniform hypergraph G with maximum degree Δ has a d-defective colouring using at most 100 (Δ/(d + 1))^(1/r) colours. This is tight up to the leading constant. Our proof uses a semirandom argument together with a sunflower decomposition trick. In the talk I will discuss the proof as well as some ideas that don't work.

This is joint work with António Girão (Oxford), Alex Scott (Oxford), and David Wood (Monash).






Comments are closed.
css.php