Text

theses

This thesis studies three problems in linear algebraic and additive combinatorics.
Our first result gives new upper bounds for the determinant of an $nimes n$ zero-one matrix containing $kn$ ones. Our results improve upon a result of Ryser for $k=o(n^{1/3})$. For fixed $kge 3$ it was an open question~cite{bruhn} whether Hadamard's inequality could be exponentially improved. We answer this in the affirmative. Our approach revolves around studying $mimes n$ matrices whose rows sum to $k$ and bounding their Gram determinants. For the class of $nimes n$ matrices whose rows sum to $k$ we show that Ryser's result can be improved for $kle sqrt{n/10}$. Our technique also allows us to give upper bounds when these matrices are perturbed.
Our second result concerns a question in additive combinatorics. For a prime $p>2$, we say a nonempty set $Asubseteq F_p$ is emph{unique sum free} (USF) if every element of the sumset $A+A$ can be written as a sum of two elements from $A$ in at least two different ways. That is for any $s in A+A$ there exist $a,b,c,d$ with ${a,b}e{c,d}$ such that $s=a+b=c+d$. If $mu(p)$ is the size of the smallest USF set in $F_p$ it is straightforward to show that $mu(p) = O(sqrt{p}).$ Kopparty~cite{koppartyconference} conjectured that $mu(p)=Theta(sqrt{p})$. However, we show constructively that $mu(p)=O(log^2 p)$.
Our third result concerns a graph theoretic problem on the Hamming cube, $Q_n$. For a graph, $G$, we say a proper $k$-coloring of $G$ is a fall $k$-coloring if each vertex is adjacent to a vertex in each of the $k-1$ other color classes. A result of Laskar and Lyle~cite{laskar} shows that for $ke 3$ and $n$ sufficiently large $Q_n$ has a fall $k$-coloring. It is natural to identify the Hamming cube, $Q_n$, with the vector space $F_2^n$. In this context we may seek fall $k$-colorings of $F_2^n$ in which each color class is an affine subspace. Our main result is that for even $k$ and $n$ sufficiently large there exist affine fall $k$-colorings of $F_2^n$. In particular, we show these exist for the same range of values of $n$ as in the construction of Laskar and Lyle.

ETD_9794

Ph.D.

Includes bibliographical references

doi:10.7282/t3-1w2k-jr68

ETD doctoral

The author owns the copyright to this work.