# Advances in Ramsey theory and discrepancy theory

## Abstract/Contents

- Abstract
- A common theme in extremal combinatorics is to find structured small configurations inside sufficiently large systems. For example, many results in Ramsey theory are in the form of, for any sufficiently large system colored in a bounded number of colors, there exists a small fixed monochromatic configuration. In discrepancy theory, the monochromaticity is relaxed to large discrepancy in the number of elements in each color. In this thesis, we use probabilistic, combinatorial, and analytical tools to make progress on several problems in these two areas. Firstly, in Chapter 2, we study the Ramsey and Turán problems for sparse hypergraphs. For graphs, degeneracy plays an important role in understanding Ramsey- and Turán-type properties. We extend this notion to hypergraphs and show that this new notion of degeneracy can capture analogous Ramsey and Turán properties for sparse hypergraphs. The proofs utilizes the technique of dependent random choice and the ``random greedy process'' introduced by Lee in his resolution of the Burr-Erdős conjecture which captures the relation between degeneracy and the Ramsey number for graphs. Next, in Chapter 3, we study discrepancy theory. We introduce a partial coloring lemma proved by Lovett and Meka in preparation for Chapters 4 and 5, and use it to improve the upper bound of a discrepancy result of Chazelle and Lvov on set families from point-line incidences. In Chapters 4 and 5, we study generalizations of celebrated theorems of Roth and of Matoušek and Spencer showing that the discrepancy of arithmetic progressions in the first n integers is n^{1/4} up to constant factors. In Chapter 4, we extend this result to consider modular arithmetic progressions and find out that the discrepancy depends on the arithmetic properties of the modular n. We determine the discrepancy up to a constant factor for some n (e.g. when n is a prime power), and determine it up to a factor of n^{o(1)} for all n. The proofs require the partial coloring lemma and new Fourier-analytic observations. In Chapter 5, we generalize the results of Roth and of Matoušek and Spencer to arithmetic progressions in the d-dimensional grid \{1, 2, \dots, n\}^d and prove that the discrepancy is n^\frac{d}{2d+2} up to a multiplicative factor depending only on d. This removes a polylogarithmic factor from the previous upper bound by Valkó. We further prove similarly tight bounds for grids of differing side lengths in many cases.

## 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 | 2024; ©2024 |

Publication date | 2024; 2024 |

Issuance | monographic |

Language | English |

## Creators/Contributors

Author | Zhou, Yunkun |
---|---|

Degree supervisor | Fox, Jacob, 1984- |

Thesis advisor | Fox, Jacob, 1984- |

Thesis advisor | Soundararajan, Kannan, 1973- |

Thesis advisor | Vondrák, Jan, (Mathematician) |

Degree committee member | Soundararajan, Kannan, 1973- |

Degree committee member | Vondrák, Jan, (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 | Yunkun Zhou. |
---|---|

Note | Submitted to the Department of Mathematics. |

Thesis | Thesis Ph.D. Stanford University 2024. |

Location | https://purl.stanford.edu/xd810gp2368 |

## Access conditions

- Copyright
- © 2024 by Yunkun Zhou
- 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...