Final doctoral examination and defense of dissertation of He Guo, June 10, 2021
Date: June 10, 2021, at 10:00am EST
Bluejeans Link is https://gatech.bluejeans.com/233874892
Title: Algorithmic Approaches to Problems in Probabilistic Combinatorics
Advisor: Dr. Lutz Warnke, School of Mathematics, Georgia Institute of Technology
Committee:
Dr. Tom Bohman, Department of Mathematical Sciences, Carnegie Mellon University
Dr. Prasad Tetali, School of Mathematics and School of Computer Science, Georgia Institute of Technology
Dr. Eric Vigoda, School of Computer Science, Georgia Institute of Technology
Dr. Lutz Warnke, School of Mathematics, Georgia Institute of Technology
Dr. Xingxing Yu, School of Mathematics, Georgia Institute of Technology
Reader: Dr. Tom Bohman, Department of Mathematical Sciences, Carnegie Mellon University
The dissertation is available here:
https://aco.gatech.edu/sites/default/files/documents/2021/dissertation-h...
Summary of the thesis is below.
Summary:
The probabilistic method is one of the most powerful tools in combinatorics: it has been used to show the existence of many hard-to-construct objects with exciting properties. It also attracts broad interests in designing and analyzing algorithms to find and construct these objects in an efficient way. In this dissertation we obtain four results using algorithmic approaches in probabilistic method:
1. We study the structural properties of the triangle-free graphs generated by a semirandom variant of triangle-free process and obtain a packing extension of Kim’s famous R(3, t) results. This allows us to resolve a conjecture in Ramsey theory by Fox, Grinshpun, Liebenau, Person, and Szabo, and answer a problem in extremal graph theory by Esperet, Kang, and Thomasse.
2. We determine the order of magnitude of Prague dimension, which concerns efficient encoding and decomposition of graphs, of binomial random graph with high probability. We resolve conjectures by Furedi and Kantor. Along the way, we prove a Pippenger-Spencer type edge coloring result for random hypergraphs with edges of size O(log n).
3. We analyze the number set generated by r-AP free process, which answers a problem raised by Li and has connection with van der Waerden number in additive combinatorics and Ramsey theory.
4. We study a refined alteration approach to construct H-free graphs in binomial random graphs, which has applications in Ramsey games.
