Negative colouring error of a forced-set closure

ID: negative-colouring-error-of-a-forced-set-closure

Independently colour each vertex with one of colours and join differently coloured vertices. This complete multipartite graph has no -clique. If a forced set is rainbow but its witnesses are not, condition on the colours of . The disjoint petals make those failure events conditionally independent. For each witness of size at most , the probability of a colour collision is at most . If this is at most , one closure step causes an error with probability at most . There are at most possible steps; apply the union bound.

New to topics? Read the docs here!