Two Questions about Properties of Large Graphs: On Generalized Turán Numbers and the Chromatic Number of Random Lifts
JD Nir · Lincoln (University of Nebraska) · 2020
In this thesis, I consider questions and results from two fields: extremal graph theory and random graph theory. First, I consider a generalization of the classic theorem of Turán that states that the maximum number of edges in a clique-free graph is uniquely obtained by a balanced complete r-partite graph. Following Alon and Shikhelman, instead of counting edges while forbidding cliques, I count copies of a target graph T while forbidding copies of F. I investigate the behavior of the extremal graphs and their graphon limits in the case where T and F are stars or cliques and provide partial results in more general cases. Second, using the small subgraph conditioning method and several other techniques, I obtain an upper bound for the chromatic number of random lifts of a general d-regular graph. In the case where the host graph G is complete, I provide a nearly matching lower bound to prove that asymptotically almost surely the chromatic number of a random n-lift of a clique takes one of at most two values. This result complements results on the chromatic number of regular graphs chosen uniformly with the configuration model.