The probabilistic method in combinatorics
Abstract/Contents
- Abstract
- The probabilistic method is the art of introducing probability to prove results that often do not involve randomness to begin with. In this thesis, we present four applications of this powerful technique, which has become one of the cornerstones of modern combinatorics. First, we prove a new lower bound for online Ramsey numbers, giving for the first time an exponential separation between the lower bounds for classical and online Ramsey numbers. Informally, this means that it is quite difficult to adaptively find a monochromatic clique in an edge-coloring of a large complete graph. Next, we determine the growth rate of a certain off-diagonal hypergraph Ramsey number, answering a question of Erdős and Hajnal from 1972. This is the first nontrivial hypergraph Ramsey number whose exponential order has been determined. The proof introduces a new random model for hypergraphs and relies heavily on the entropy method. Third, we apply the entropy method to extremal graph theory, proving Tomescu's graph-coloring conjecture from 1971. This determines the maximum number of proper k-colorings of any graph with chromatic number k and n vertices. In the proof we use an entropy inequality related to sequential importance sampling, an estimation technique from statistics. Finally, we present a result in probabilistic combinatorics outside graph theory. An n-permutation is called k-universal if it contains every k-permutation as a pattern, and it is known that the shortest k-universal permutation has length O(k^2). It was suggested by Alon that actually almost all n-permutations are k-universal for some n=O(k^2), and he proved that a random permutation of length O(k^2 logk) is k-universal with high probability. Using a structure-versus-randomness approach, we improve this bound to O(k^2 loglogk), almost closing the gap to the conjecture.
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 | 2021; ©2021 |
| Publication date | 2021; 2021 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | He, Xiaoyu |
|---|---|
| Degree supervisor | Fox, Jacob, 1984- |
| Thesis advisor | Fox, Jacob, 1984- |
| Thesis advisor | Diaconis, Persi |
| Thesis advisor | Vondrak, Ján, (Mathematician) |
| Degree committee member | Diaconis, Persi |
| Degree committee member | Vondrak, Ján, (Mathematician) |
| Associated with | Stanford University, Department of Mathematics |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Xiaoyu He. |
|---|---|
| Note | Submitted to the Department of Mathematics. |
| Thesis | Thesis Ph.D. Stanford University 2021. |
| Location | https://purl.stanford.edu/qm498fb2052 |
Access conditions
- Copyright
- © 2021 by Xiaoyu He
Also listed in
Loading usage metrics...