= Independent transversal
For a <graph> whose vertices are partitioned into parts, an independent transversal is an <independent set> containing exactly one vertex from each part. If a cycle's parts each have twelve vertices, choose one vertex uniformly and independently per part. A cycle edge joining distinct parts is selected at both ends with <probability> $1/144$. Each <event> depends on at most $47$ others, since each part meets at most $24$ cycle edges. The <Lovász local lemma> applies because $48e/144<1$, proving existence for an arbitrary such partition.
Back to article page
