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.
Articles by others on the same topic
There are currently no matching articles.