Methods for problems in generalized Ramsey theory
Abstract/Contents
- Abstract
- Ramsey theory is the branch of combinatorics that studies the phenomenon of order arising within partitions of a large system. In this thesis, we address several problems involving more general Ramsey-type numbers in a wide range of settings, highlighting the diverse collection of methods and ideas used in making progress towards them. First, we study a recently introduced list-coloring version of the multicolor Ramsey numbers. We use a probabilistic argument based on the Lovász Local Lemma to prove an exponential lower bound on these quantities, then briefly discuss several other related Ramsey-type numbers. Next, we apply regularity methods to analyze another Ramsey number variant known as the blowup Ramsey numbers. We answer a question of Souza by showing an exponential upper bound with a more nuanced dependence on the graphs involved. Then, we investigate a new family of Ramsey-theoretic questions about the sizes of monochromatic components in an edge coloring of a graph, proving tight lower bounds in the 3- and 4-color cases of the problem, building up machinery in the process that aims to also be useful in the more general case. We also address the analogous problem for hypergraphs of higher uniformity, applying some tools from design theory to further understand this setting. Finally, we introduce a new variant of the polynomial method based on so-called "shift operators, " demonstrating its potential utility in additive combinatorics by using it to provide simple alternate proofs of the results of several very different polynomial methods.
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 | 2023; ©2023 |
| Publication date | 2023; 2023 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Luo, Sammy Yiru |
|---|---|
| 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, School of Humanities and Sciences |
| Associated with | Stanford University, Department of Mathematics |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Sammy Luo. |
|---|---|
| Note | Submitted to the Department of Mathematics. |
| Thesis | Thesis Ph.D. Stanford University 2023. |
| Location | https://purl.stanford.edu/qt786dn5083 |
Access conditions
- Copyright
- © 2023 by Sammy Yiru Luo
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...