UC San Diego

This dissertation lies at the intersection of extremal combinatorics and probabilistic combinatorics. Roughly speaking, \textit{extremal combinatorics} studies how large a combinatorial object can be. For example, a classical result of Mantel's says that every $n$-vertex triangle-free graph has at most $\quart n^2$ edges. The area of \textit{probabilistic combinatorics} encompasses both the application of probability to combinatorial problems, as well as the study of random combinatorial objects such as random graphs and random permutations. In this dissertation we study three problems related to extremal properties of random objects. First, we study the maximum score of a certain guessing game which uses a randomly shuffled deck of cards, and in doing so we solve a 40 year conjecture of Diaconis and Graham. Next, we study the Tur an problem in random hypergraphs. Specifically, we examine the function $\ex(H_{n,p}^r,\c{F})$, which is the maximum number of hyperedges that an $\c{F}$-free subgraph of the random hypergraph $H_{n,p}^r$ can have. By using a novel counting technique, we obtain effective bounds when $\c{F}$ consists of a collection of Berge cycles. Finally, we study thresholds of random graphs and hypergraphs, which essentially asks how large $p$ must be in order for $H_{n,p}^r$ to contain a given structure. We give a common generalization of recent breakthrough work done by Alweiss, Lovett, Wu, and Zhang related to the Erd\H{o}s sunflower problem; and of work by Kahn, Narayanan, and Park related to the threshold for squares of Hamiltonian cycles in $G_{n,p}$.