Graphs, codes, and colorings

\noindent{This thesis focuses on topics in extremal combinatorics.} Given an integer-valued function $f$ defined on the vertices of a graph $G$, we say $G$ is {\em $f$-choosable} if for every collection of lists with list sizes specified by $f$ there is a proper coloring using the colors from the lists. The {\em sum choice number}, $\chi_{sc}(G)$, is the minimum of $\sum f(v)$ such that $G$ is $f$-choosable. We show that if $q\geq 4 a^2\log a$, then there exist constants $c_1$ and $c_2$ such that \[ 2q+c_1a\sqrt{q\log {a}}\leq \chi_{\rm sc}(K_{a,q})\leq 2q+c_2a\sqrt{q\log {a}}.\] As a consequence, $\chi_{sc}(G)/|V(G)|$ can be bounded while the minimum degree $\delta_{\rm min}(G)\to \infty$. This is not true for the list chromatic number, $\chi_\ell(G)$. We further prove that, for fixed $a$, the limit $\lim_{q\to \infty} (\chi_{\rm sc}(K_{a,q})-2q)/\sqrt{q}$ exists, and we give tight bounds for sum choice numbers of the graphs $G_{a,q}$, which are obtained from $K_{a,q}$ by adding all possible edges in the part of size $a$. A pair of ordered $k$-tuples $(x_1,...,x_k)$, $(y_1,...,y_k)$ is {\em reverse-free} if, for all $i