Modern methods in extremal combinatorics
Abstract/Contents
- Abstract
- In this thesis, we apply modern probabilistic and algebraic techniques to different problems in extremal combinatorics. One of the most recent algebraic techniques is the new polynomial method which Croot, Lev and Pach introduced in 2016. This method has lead to the spectacular breakthrough of Ellenberg and Gijswijt on the cap-set problem, and has had many more applications in additive number theory and extremal combinatorics. In Chapter 2, we use various tools that resulted from the Croot-Lev-Pach polynomial method, combined with probabilistic and combinatorial arguments, to prove new upper bounds on the Erdos-Ginzburg-Ziv constant of F_p^n for a fixed prime p \geq 5 and large n. Chapter 3 also relies on developments arising from the Croot-Lev-Pach polynomial method as well as new combinatorial ideas. We prove a polynomial bound relating the parameters in Green's arithmetic k-cycle removal lemma in F_p^n for all k \geq 3. The special case of k = 3 was previously proved by Fox and Lovasz and is used as the base case of an induction on k in our proof for all k \geq 3. In Chapter 4, we use methods from algebraic geometry (and basic differential topology) to prove an asymptotically tight lower bound for the number of graphs of a certain form where the edges are defined algebraically by the signs of a finite list of polynomials. We present many applications of this result, in particular to counting intersection graphs and containment orders for various families of geometric objects (e.g. segments of disks in the plane). Using probabilistic methods, we prove the so-called Edge-statistics conjecture of Alon, Hefetz, Krivelevich and Tyomkyn in Chapter 5. In a certain range of the parameters, this conjecture already follows from a result of Kwan, Sudakov and Tran. We solve the other cases, and thereby establish the full conjecture. Finally, in Chapter 6 we prove a conjecture of Erdos, Faudree, Rousseau and Schelp from 1990 concerning subgraphs of minimum degree k.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2019; ©2019 |
| Publication date | 2019; 2019 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Sauermann, Lisa | |
|---|---|---|
| Degree supervisor | Fox, Jacob, 1984- | |
| Thesis advisor | Fox, Jacob, 1984- | |
| Thesis advisor | Soundararajan, Kannan, 1973- | |
| Thesis advisor | Vondrak, Ján, (Mathematician) | |
| Degree committee member | Soundararajan, Kannan, 1973- | |
| Degree committee member | Vondrak, Ján, (Mathematician) | |
| Associated with | Stanford University, Department of Mathematics. |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Lisa Sauermann. |
|---|---|
| Note | Submitted to the Department of Mathematics. |
| Thesis | Thesis Ph.D. Stanford University 2019. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2019 by Lisa Sauermann
Also listed in
Loading usage metrics...