Home
Resource
Several problems in linear algebraic and additive combinatorics
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(797.36 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Scheinerman, Daniel. Several problems in linear algebraic and additive combinatorics. Retrieved from https://doi.org/doi:10.7282/t3-1w2k-jr68

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitleSeveral problems in linear algebraic and additive combinatorics
NameScheinerman, Daniel (author); Kopparty, Swastik (chair); Beck, Jozsef (internal member); Narayanan, Bhargav (internal member); Lev, Vsevolod (outside member); Rutgers University; School of Graduate Studies
Date Created2019
Other Date2019-05 (degree)
SubjectMathematics, Additive combinatorics
Extent1 online resource (x, 92 pages) : illustrations
DescriptionThis 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.
NotePh.D.
NoteIncludes bibliographical references
Genretheses, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/t3-1w2k-jr68
LanguageEnglish
CollectionSchool of Graduate Studies Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024