Problems in Coding Theory and Extremal Combinatorics

This dissertation consists of ?five papers whose subjects are mostly disjoint. Below are their abstracts and citation information.

On a fractional version of Haemers' bound. In this note, we present a fractional version of Haemers' bound on the Shannon capacity of a graph, which is originally due to Blasiak. This bound is a common strengthening of both Haemers' bound and the fractional chromatic number

of a graph. We show that this fractional version outperforms any bound on the Shannon capacity that could be attained through Haemers' bound. We show also that this bound is multiplicative, unlike Haemers' bound.

With Boris Bukh.

In IEEE Transactions on Information Theory, vol. 65, no. 6, pp. 3340{3348, Jun. 2019.

Inverting the Turan problem. Classical questions in extremal graph theory concern the asymptotics of ex(G;H) where H is a ?fixed family of graphs and G = Gn is taken from a "standard" increasing sequence of host graphs (G1;G2; : : : ) most often Kn or Kn;n. Inverting the question, we can instead ask how large e(G) can be with respect to ex(G;H). We show that the standard sequences indeed maximize e(G) for some choices of H, but not for others. Many interesting questions and previous results arise very naturally in this context, which also, perhaps unusually, gives rise to sensible extremal questions concerning multigraphs and non-uniform hypergraphs.

With Joe Briggs.

In Discrete Mathematics, vol. 342, no. 7, pp. 1865{1884, Jul. 2019.