Georgia Institute of Technology College of Sciences

The talk starts with Rödl's Theorem that graphs with huge chromatic number contain triangle-free subgraphs with large chromatic number. We will look at various related results and conjectures, with a notable matroid bias; the new results are joint work with Peter Nelson and Raphael Steiner.

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.

The Bluejeans link of the defense is https://gatech.bluejeans.com/233874892