Thesis Defense

Applications of Spectral Graph Theory to Some Classical Problems in Combinatorics and Number Theory

Yesim Demiroglu, University of Rochester

Tuesday, May 29th, 2018
11:00 AM - 12:00 PM
Hylan 1106A

In the first half of this thesis, we obtain sharp results for Waring’s problem over general finite rings, by using a combination of Artin-Wedderburn theory and Hensel’s lemma and building on new proofs of analogous results over finite fields that are achieved using spectral graph theory. We also prove an analogue of Sárközy’s theorem for finite fields.

In the second half of the thesis, we investigate the unit-graphs and the special unit-digraphs on matrix rings and we show that every \(n \times n\) nonzero matrix over \(\Bbb F_q\) can be written as a sum of two \(\operatorname{SL}_n\)-matrices when \(n>1\). We compute the eigenvalues of these graphs in terms of Kloosterman sums and study their spectral properties. We prove that if \(X\) is a subset of \(\operatorname{Mat}_2 (\Bbb F_q)\) with size \(\|X\| > \frac{2 q^3 \sqrt{q}}{q - 1}\), then \(X\) contains at least two distinct matrices whose difference has determinant \(\alpha\) for any \(\alpha \in \Bbb F_q^{\ast}\). Using this result we also prove a sum-product type result: if \(A,B,C,D \subseteq \Bbb F_q\) satisfy \(\sqrt[4]{\|A\|\|B\|\|C\|\|D\|}= \Omega (q^{0.75})\) as \(q \rightarrow \infty\), then \((A - B)(C - D)\) equals all of \(\Bbb F_q\). In particular, if \(A\) is a subset of \(\Bbb F_q\) with cardinality \(\|A\| > \frac{3} {2} q^{\frac{3}{4}}\), then the subset \((A - A) (A - A)\) equals all of \(\Bbb F_q\). We also recover some classical results, e.g. every element in any finite ring of odd order can be written as the sum of two units, and we also derive some character sum identities.

Event contact: hazel dot mcknight at rochester dot edu