CAREER: Model theory, measures and combinatorics

University Of California-Los Angeles, Los Angeles CA

Investigators

Abstract

Model theory is an area of mathematical logic studying families of (typically) infinite structures and their properties definable in a formal language. While this method originates in foundational questions, over the years profound applications to the study of many central objects of classical mathematics and computer science were discovered. This project will investigate an emerging connection to the area of graph theory. Graphs are the basic discrete mathematical objects used to model networks and related systems. In combinatorics, one often investigates the asymptotic behavior of various quantitative properties (such as the density of the edges, or the size of a certain regular pattern) for large finite graphs. Model theory provides a method of converting asymptotic quantitative questions about properties of a family of graphs into qualitative questions about the shape, volume or dimension of a certain limiting infinite object (via the so-called ultraproduct construction). Infinitary model-theoretic machinery to study such limit objects will be used to address questions in finite graph combinatorics, and conversely rich body of results in combinatorics will be used to attack open questions in model theory. As demonstrated in the previous work of the principal investigator and other researchers, recent advances on pseudo-randomness and Ramsey-type phenomena for restricted families of graphs (e.g. semialgebraic regularity lemma by Fox et al., Tao's algebraic regularity lemma over finite fields, regularity lemma for graphs of finite Vapnik-Chervonenkis dimension by Lovasz-Szegedy, etc.) admit a uniform model-theoretic treatment well-aligned with the methods and ideas in Shelah's classification theory. This project initiates a systematic program of investigating these connections, centered around the study of Keisler measures and various model-theoretic notions of dimension (e.g. coming from forking independence or pseudofinite counting) in tame classes of first-order structures (stable, distal, dependent, simple, NTP2, etc.), as well as the finer questions on generalized "incidence bounds" and their relation to Zilber's trichotomy phenomena.