Existence and construction of certain combinatorial and algebraic structures

Many problems in combinatorics and computer science use algebraic methods in their solutions, even if they do not look inherently algebraic. Polynomial methods [49], rank arguments [16], and spectral graph theory [48] are among the most popular techniques in this area. In this thesis, we study two different problems in discrete math and theoretical computer science and show two results using algebraic methods. In the first part of the thesis, we study the game of Cops and Robbers [10]. Specifically, we present several families of abelian Cayley graphs whose cop numbers are asymptotically optimal. More precisely, we present several constructions of families of abelian Cayley graphs G on n vertices whose cop number isΩ(√n). This complements the recent result of Bradshaw [12], who proved that for all abelian Cayley graphs on n vertices the cop number is at most O(√n). In the second part of the thesis, we study explicit constructions of tree codes [46, 45]. We focus on applying techniques from linear algebra to prove the existence of certain combinatorial objects, whose explicit construction implies tree codes with a constant rate. More specifically, we study lower-triangular totally-non-singular matrices. These matrices are the key ingredients in all recent constructions of tree codes [18, 34].