This dissertation contains a variety of results in quantitative combinatorial geometry, as well as applications to optimization and number theory.
We use Ehrhart theory, the study of the number of lattice points in polytopes, to prove a Rainbow Ramsey analogue of Richard Rado's 1933 result in Ramsey Theory. There were some conjectures as to what this analogue would be; they are disproven by our result. We also prove a few corollaries.
A portion of this dissertation contains new quantitative variants of classical convexity theorems: whereas the classical theorems have hypotheses and conclusions requiring certain sets to be nonempty, their quantitative variants require that the sets have a certain "size" (volume, diameter, etc). The three classical theorems we quantize are Carathéodory's Theorem, Helly's Theorem, and Tverberg's Theorem. The Helly portion contains new non-quantitative results as well. The Tverberg portion proves that any Helly-type theorem implies a corresponding Tverberg-type theorem.
A maximal 1-lattice polytope is a lattice polytope containing exactly one interior lattice point whose facets each contain at least one interior lattice point. In this dissertation, we bound the size of all maximal 1-lattice pyramids and prisms. These bounds may be used with a brute-force algorithm to quickly enumerate all maximal 1-lattice pyramids and prisms up to equivalence.
S-optimization, a generalization of continuous, integer, and mixed-integer optimization in which variables take values from a set S, is introduced and studied in the last part of this dissertation. We generalize two traditional optimization algorithms to S-optimization: the chance-constrained algorithm of Calafiore and Campi, and the sampling algorithm of Clarkson. Interestingly, the complexities of the generalized algorithms are dependent upon the same Helly numbers studied elsewhere in this dissertation.
|Advisor:||De Loera, Jesus|
|Commitee:||Bai, Zhaojun, Koppe, Matthias|
|School:||University of California, Davis|
|School Location:||United States -- California|
|Source:||DAI-B 78/03(E), Dissertation Abstracts International|
|Keywords:||Combinatorics, Convex geometry|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be