$4$-choosability of $K_{10,10}$ A graph is $k$-choosable if no matter how one assigns a list of $k$ colors to each vertex, the vertices in the graph can be coloured in a way that each vertex receives a colour from its list and any two adjacent vertices have different colours.
One can prove that the complete bipartite graph $K_{10,10}$ is not $3$-choosable by considering the scenario when the vertices on the left part receive all $\binom{5}{3} = 10$ different subsets of $\{1,2,3,4,5\}$ and same for the vertices on the right.
A natural question: is $K_{10,10}$ $4$-choosable? If yes, how can we prove it. (Some kind of greedy algorithm?) One can show that it is $5$-choosable, as in Theorem 1.4.2 at https://yufeizhao.com/pm/probmethod_notes.pdf
 A: Yes, $K_{10,10}$ is $4$-choosable.
The paper "Choosability in Graphs" by Erdős, Rubin and Taylor relates $\chi_l(K_{m,n})$ to $2$-coloring hypergraphs (also known as property B in the literature). A hypergraph has property B if we can $2$-color its edges so that no edge is monochromatic. We write $m(k)$ for the minimum number of edges in a $k$-uniform hypergraph that does not have property B - in other words, any set $S$ that intersects every edge must contain some edge.
Erdős, Rubin and Taylor prove that:
Fact 1. The complete bipartite graph $K_{m(k), m(k)}$ is not $k$-choosable.
Proof. Take a $k$-uniform hypergraph $\mathcal H$ with $m(k)$ edges that does not have property B, and use $E(\mathcal H$) as the color lists on each side of $K_{m(k),m(k)}$. Suppose we color all the vertices on one side of the bipartite graph; let $S$ be the set of colors used. Then $S$ must intersect every edge of $\mathcal H$, because every vertex gets a color. Therefore $S$ contains an edge of $\mathcal H$; the corresponding vertex on the other side cannot be colored.
Fact 2. If $a + b < m(k)$, then the complete bipartite graph $K_{a,b}$ is $k$-choosable.
Proof. For any $k$-list assignment of $K_{a,b}$, let $\mathcal H$ be the hypergraph whose edges are the color lists from both sides. (If color lists repeat, that's fine; we only need to include the edge once.) Since $\mathcal H$ has at most $a+b$ edges, it has property B, so let's $2$-color the vertices of $\mathcal H$ red and blue so that every edge has a red vertex and a blue vertex.
To get a list coloring, choose colors as follows: for every vertex on the first side of $K_{a,b}$, choose a color such that the corresponding vertex of $\mathcal H$ is red. For every vertex on the second side of $K_{a,b}$, choose a color such that the corresponding vertex of $\mathcal H$ is blue.

It was already known to Erdős, Rubin and Taylor that $m(1)=1$, $m(2)=3$, and $m(3)=7$. This proves, for example, that not just $K_{10,10}$ but even $K_{7,7}$ is not $3$-choosable. Use the following color lists on each side of $K_{7,7}$: $$\{1,2,3\}\;\{1,4,5\}\;\{1,6,7\}\; \{2,4,6\}\; \{2,5,7\}\; \{3,4,7\}\; \{3,5,6\}$$These are based on the Fano plane, which is the hypergraph that gives us $m(3)=7$: if you pick a point on every line of the Fano plane, there is some line on which every point is picked.
A more recent paper, "On the minimum size of 4-uniform hypergraphs without property  $B$" by Patric Östergård, shows that $m(4) = 23$. It follows that whenever $a+b < 23$, $K_{a,b}$ is $4$-choosable; in particular, $K_{10,10}$ (and even $K_{11,11})$ is $4$-choosable.
