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.