Colouring complete bipartite graphs from random lists
| dc.creator | Krivelevich, Michael | |
| dc.creator | Nachmias, Asaf | |
| dc.date | 2005-12-01 | |
| dc.date.accessioned | 2026-07-07T06:54:44Z | |
| dc.date.available | 2026-07-07T06:54:44Z | |
| dc.description | Let $K_{n,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\geq 2$ and the location of the threshold is precisely $s(n)=2n$ for $k=2$, and approximately $s(n)=\frac{n}{2^{k-1}\ln 2}$ for $k\geq 3$. | |
| dc.description | 14 pages. To appear in Random Structures and Algorithms | |
| dc.identifier | https://arxiv.org/abs/math/0512010 | |
| dc.identifier | http://arxiv.org/abs/math/0512010 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/106043 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.title | Colouring complete bipartite graphs from random lists | |
| dc.type | text |