Georgia Institute of Technology
Large-scale Phenomena in Geometry, Probability, and Combinatorics
Abstract
dc:description.abstractIn this dissertation we study the presence of large-scale phenomena in the areas of geometry, probability, and combinatorics. The contributions of this thesis are as follows: In chapter 2 we study the \ell0 isoperimetric coefficient for measurable sets in \Rn. Firstly we show that the \ell0 isoperimetric coefficient of an axis-aligned cube is of order n-1/2, answering a question of Laddha and Vempala, and consequently improve the best known lower bound on the coefficient for sufficiently regular convex bodies. Secondly, we show that the \ell0 isoperimetric coefficient of any measurable set is at most of order n-1/2. These two results imply that the cube essentially maximizes the \ell0 isoperimetric coefficient. In chapter 3 we consider two problems from non-asymptotic random matrix theory. We first study the problem of estimating the distance between a random vector and subspace in \Rn. We obtain a small ball estimate for the distance between a random vector X and subspace H, where the entries of X and the vectors spanning H are independent, inhomogeneous and heavy-tailed. Our results generalize work of Livshyts, Tikhomirov and Vershynin by allowing H to have co-dimension up to order n/logninasetting where previous results required H to have co-dimension 1. Next, we study the problem of estimating the smallest singular value of a random rectangular matrix. We obtain a small ball estimate for the smallest singular value of a random rectangular matrix whose entries are independent, inhomogeneous and heavy-tailed. Our results generalize recent work of Livshyts and Livshyts, Tikhomirov and Vershynin. In addition, our small ball estimates for rectangular matrices are the first to match those obtained by Rudelson and Vershynin in the far more restrictive setting of rectangular matrices with i.i.d. and sub-gaussian entries. From a larger context, the generality of our results provide another example of the universality phenomenon in random matrices. In chapter 4 we study the behavior of the clique chromatic number of a simple graph in the binomial random graph model G_{n,p}. For ranges of sparse p we determine the order of magnitude and asymptotics of its typical value. Our results answer a question of Alon and Krivelevich and resolve a conjecture of Lichev, Mitsche, and Warnke.
Degree
thesis:*- Level thesis:degree_level
- Doctoral
- Department dc:contributor.department
- Mathematics
- Grantor dc:publisher
- Georgia Institute of Technology
- Year dc:date.issued
- 2025
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Fernandez, Manuel
- Advisor dc:contributor.advisor
-
- Livshyts, Galyna
- Committee members dc:contributor.committeemember
-
- Koltchinskii, Vladimir
- Mckenna, Benjamin
- Tikhomirov, Konstantin
- Vempala, Santosh
Subjects
dc:subject × 3Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/77918