The list chromatic number of a graph with average degree d is at least (1+o(1))log_2 d

You need to know: Graph, simple graph (one with no loops and multiple edges), degree of a vertex in the graph, average degree of a graph, small o notation. You also need to know chromatic number of graph and complete bipartite graph $K_{d,d}$ for the context section.

Background: A graph G is called k-choosable if, whenever for each vertex v of G we assign a list $L_v$ of k colours to v, then it is possible to choose a colour for v from the list $L_v$ , so that no two adjacent vertices receive the same colour. The list chromatic number $\chi_l(G)$ is the smallest k such that G is k-choosable.

The Theorem: On 30th April 2012, David Saxton and Andrew Thomason submitted to arxiv a paper in which they proved, among other results, that if G is a simple graph with average degree d, then $\chi_l(G) \geq (1+o(1))\log_2 d$ as $d\to \infty$ .

Short context: List chromatic number $\chi_l(G)$ is a natural version of the ordinary chromatic number $\chi(G)$ of G (which corresponds to the case when all $L_v$ are the same). It is known that $\chi_l(K_{d,d})=(1+o(1))\log_2 d$ , in sharp contrast with $\chi(K_{d,d})=2$ . In fact, Alon proved that $\chi_l(G) \geq (1/2+o(1))\log_2 d$ for graphs G of minimum degree d. The Theorem improves this inequality by a factor of 2 and is the best possible, as example $G=K_{d,d}$ shows. In fact, the Theorem is just one out of many corollaries of the general theorem proved by the authors, see the original paper for details.