University of Illinois Chicago
Browse

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

Download (1.45 MB)
thesis
posted on 2016-10-19, 00:00 authored by Caroline Terry
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.

History

Advisor

Marker, David

Department

Mathematics, Statistics, and Computer Science

Degree Grantor

University of Illinois at Chicago

Degree Level

  • Doctoral

Committee Member

Mubayi, Dhruv Baldwin, John Malliaris, Maryanthe Starchenko, Sergei

Submitted date

2016-08

Language

  • en

Issue date

2016-10-19

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC