Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Final Defense

Sam Spiro

UCSD

Extremal Problems for Random Objects

Abstract:

This dissertation lies at the intersection of extremal combinatorics and probabilistic combinatorics.  Roughly speaking, 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 $\frac{1}{4} n^2$ edges.  The area of 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 problems related to extremal properties of random objects.  In particular we study a certain card guessing game, $F$-free subgraphs of random hypergraphs, and thresholds of random hypergraphs.  Minimal prerequisites will be assumed.

Advisor: Jacques Verstraete

May 18, 2022

9:30 AM

AP&M 6402

Zoom link available upon request

****************************