2005/12/01 by Michael Krivelevich, Krivelevich, Michael, Asaf Nachmias +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR) #math.CO #math.PR
paper · pdf · doi:10.48550/arxiv.math/0512010
14 pages. To appear in Random Structures and Algorithms
arxiv created 2005/12/01 · openalex publication_date 2005/12/01 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let Kn,n be the complete bipartite graph with n vertices in each side. For each vertex draw uniformly at random a list of size k from a base set S of size s=s(n). In this paper we estimate the asymptotic probability of the existence of a proper colouring from the random lists for all fixed values of k and growing n. We show that this property exhibits a sharp threshold for k≥ 2 and the location of the threshold is precisely s(n)=2n for k=2, and approximately s(n)=\fracn2k-1ln 2 for k≥ 3.