AbstractsMathematics

Model Theory and Extremal Combinatorics: Structure, Enumeration, and 0-1 Laws

by Caroline Terry




Institution: University of Illinois – Chicago
Department:
Year: 2016
Keywords: model theory; extremal combinatorics; Ramsey theory; zero-one laws; enumeration
Posted: 02/05/2017
Record ID: 2065823
Full text PDF: http://hdl.handle.net/10027/21323


Abstract

This thesis investigates connections between model theory and extremal combinatorics. The first part of the thesis consists of an analysis of discrete metric spaces and multigraphs, from the point of view of extremal combinatorics. We first consider finite metric spaces with integer distances between 1 and r, where r is a fixed integer at least 2. We prove approximate enumeration and structure theorems for these metric spaces. When r is even, we prove precise structure and enumeration theorems, and obtain new zero-one laws as consequences. An (n,s,q)-graph is a multigraph on n vertices where every set of s vertices spans at most q edges. We study the problem of determining the maximum product of edge multiplicities in (n,s,q)-graphs. We prove sharp results for certain values of s and q, as well as corresponding stability theorems in some cases. These results are joint work with D. Mubayi. The second part of the thesis uses model theory to unify under a general framework, certain definitions and theorems appearing in the first part of the thesis and throughout the literature in extremal combinatorics. In particular, we consider classes of structures in finite relational languages which are closed under model theoretic substructure and isomorphism. In this setting, we give general definitions of extremal structures, asymptotic density, and stability theorems. We prove a general enumeration theorem in terms of asymptotic density, and under the assumption of the existence of a stability theorem, we prove a general approximate structure theorem. We then show these results generalize the arguments appearing in many papers on structure and enumeration of combinatorial objects. The last part of the thesis consists of joint work with M. Malliaris in which we consider a theorem in graph theory from the perspective of model theory. In particular, we reprove a theorem of Chudnovsky, Kim, Oum, and Seymour by reorganizing their proof in such a way that allows us to apply the stable Ramsey theorem in place of the usual Ramsey theorem. We also give an infinitary proof which implies the original finite result. Advisors/Committee Members: Marker, David (advisor).