The emergence of structures in random processes and random graphs
Abstract/Contents
- Abstract
- This thesis concerns phenomena around the emergence of structures in random graphs, hypergraphs and processes. Sparse random graphs are central objects in probability and combinatorics. An important aspect of random graphs that has been extensively studied in the past four decades is the threshold phenomenon. The threshold of an increasing graph property is the density at which a random graph transitions from unlikely satisfying to likely satisfying the property. Kahn and Kalai conjectured that this threshold is always within a logarithmic factor of the expectation threshold, a natural lower bound to the threshold which is often much easier to compute. In probabilistic combinatorics and random graph theory, the Kahn-Kalai conjecture directly implies a number of difficult results, such as Shamir's problem on hypergraph matchings. We will discuss the full resolution of the Kahn-Kalai conjecture. Interestingly, the proof of the Kahn-Kalai conjecture is motivated by main ideas behind the resolution of a conjecture of Talagrand on extreme events of suprema of certain stochastic processes driven by sparse Bernoulli random variables (known as selector processes), and a question of Talagrand on suprema of general positive empirical processes. These conjectures play an important role in generalizing the study of suprema of stochastic processes beyond the Gaussian case, and given recent advances on chaining and the resolution of the (generalized) Bernoulli conjecture, our results give the first steps towards Talagrand's last ``Unfulfilled dreams'' in the study of suprema of general empirical processes. One of the key ideas behind the proof of Talagrand's conjecture is the introduction of ``minimum fragments'', which readily yields a short proof of the Kahn-Kalai conjecture. We will also discuss a further application of this key idea on sunflowers in set systems with bounded VC dimension. Given the resolution of the Kahn-Kalai conjecture, determining thresholds in general setups reduces to estimation of the expectation threshold. While this is straightforward in simple examples, it immediately becomes challenging for nontrivial examples. Towards a development of general techniques for estimating expectation thresholds, we will discuss the resolution of several conjectures of Johansson, Keevash, Luria and Simkin, Casselgren and Haggkvist, and Kang, Kelly, Kuhn, Methuku and Osthus on the thresholds for containment of Latin squares and Steiner triple systems. We will also discuss the estimation of thresholds in robust setting, particularly showing a robust common strengthening of the Corradi-Hajnal theorem and the result of Johansson, Kahn and Vu and thresholds for clique factors in Erdos-Renyi random graphs. While the threshold phenomenon focuses only on the emergence of structures in typical instances, it is also of interest to zoom into finer details and study extreme events and tail behaviors of structures inside random graphs. This is an area of study in large deviations theory. We will discuss nonlinear large deviation results for subgraph counts of sparse Erdos-Renyi random graphs and hypergraphs. This is built on a development of a version of the regularity method, a powerful framework in modern probabilistic combinatorics, that applies much more efficiently to random graphs and hypergraphs.
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 | Pham, Huy Tuan |
|---|---|
| Degree supervisor | Fox, Jacob, 1984- |
| Thesis advisor | Fox, Jacob, 1984- |
| Thesis advisor | Dembo, Amir |
| Thesis advisor | Vondrak, Ján, (Mathematician) |
| Degree committee member | Dembo, Amir |
| 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 | Huy Tuan Pham. |
|---|---|
| Note | Submitted to the Department of Mathematics. |
| Thesis | Thesis Ph.D. Stanford University 2023. |
| Location | https://purl.stanford.edu/kz832sm0345 |
Access conditions
- Copyright
- © 2023 by Huy Tuan Pham
- 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...