The proposed research will apply methods from model theory to study the generic interactions between families of finite combinatorial objects in models of unstable theories. These questions naturally admit, and benefit from, ideas and methods from graph theory and finite combinatorics. More precisely, Malliaris will work to further develop the theory of characteristic sequences, which are countable sequences of hypergraphs defined on the parameter space of a first-order formula. Malliaris has shown that a deep collection of techniques from graph theory and combinatorics, including Szemeredi regularity, can be brought to bear on model-theoretic structure via the characteristic sequence. Malliaris proposes to further explore these promising connections, which are relevant to many structural questions in unstable theories, including the fine structure of order and independence and the classification of theories with the independence property, as well as to understanding the model-theoretic significance of graph-theoretic phenomena such as edge density and hypergraph regularity in this context. Moreover, these investigations shed light on the ways in which families of types are realized and omitted in regular ultrapowers, and are therefore relevant to the longstanding open problem of the structure of Keisler's order on unstable theories (a preorder on countable theories which, roughly speaking, measures the difficulty of producing saturated regular ultrapowers).

Model theory is a branch of mathematics which studies the fundamental structure of certain classes of mathematical objects, the models of a given theory. The structural variation which occurs within a given class (or between comparable models of different classes) sheds light on the inherent simplicity, or complexity, of the theory itself. The work in this proposal arises from new indications that certain theories may have deep and previously undetected structural similarities. These similarities have to do with possible limit behavior, that is, with the complexity of infinite configurations which arise from families of finite combinatorial objects within models of the theory. One broad aim of this work is the development of finer tools to detect this behavior in certain invariants of the theory (e.g. the persistence and distribution of graphs in the characteristic sequence of certain formulas of T). These ideas would give new leverage in the ongoing program of classifying unstable theories. Model-theoretic classification theory has, over the last forty years, developed a richly informative toolbox for analyzing the complexity of first-order theories and isolated many useful indicators of complexity, but much remains to be done. In particular, a second underlying goal of this work is to give a language in which to precisely ask, and to explore, the largely open questions of distribution and density of these indicators: how and where they cluster and how they interact with other objects in the model, e.g. base sets for types.

Project Report

Intellectual Merit: This award supported foundational research in model theory: on one hand furthering the connections of model theory to combinatorics via phenomena such as Szemeredi regularity, and on the other advancing the long standing open problem of Keisler's order which, after many years of little progress, had been revived in the PI's doctoral thesis and early papers. The award included a supplement which supported the PI's visit to Jerusalem to collaborate with Saharon Shelah, who had been responsible for the major early work on Keisler's order. In a notable outcome of this productive collaboration, Malliaris and Shelah applied model-theoretic techniques developed for the study of Keisler's order to connect and solve two a priori unrelated open problems: a sufficient condition for maximality in Keisler's order and a 60-year-old problem in set theory/general topology, the oldest problem on cardinal invariants of the continuum. These results were announced in the article: M. Malliaris and S. Shelah, "General topology meets model theory, on p and t." Proc Natl Acad Sci USA 110, 33 (2013) 13300-13305, which was the subject of a PNAS Commentary. As of summer 2014, nine research papers had been written under this award. Results of these papers support earlier evidence that regularity phenomena such as that of Szemeredi are connected to model-theoretic phenomena, both via classification theory and via the characteristic sequence of hypergraphs associated to a first-order formula. There were significant advances in the construction of regular ultrafilters, notably, insight that the construction may be separated into a more set-theoretic and a more model-theoretic component, by working with a certain quotient Boolean algebra. Moreover, Keisler's order appears connected with structure/ randomness dichotomies in model theory, documented in various ways in the papers produced. Among the theorems which appear in papers under this grant we mention the following. First, there is a Keisler-minimum TP2 theory which is saturated precisely by ultrafilters which admit internal bijections between any two small sets. Second, the existence of half-graphs precisely characterizes the existence of irregular pairs in Szemeredi's celebrated regularity lemma. Third, Keisler's order has at least two classes within the simple unstable theories. Fourth, the strong tree property SOP2 implies maximality in Keisler's order. Fifth, "p=t" as mentioned above, solving the oldest problem on cardinal invariants of the continuum. Broader Impact: During the course of the grant, PI gave a number of research talks to the mathematical community including ten invited conference talks, three math department colloquia, two logic colloquia, and six seminar talks. PI developed and taught several graduate courses at U. Chicago, including one on ultrapowers which introduced some main topics of the grant. PI taught in the U. Chicago summer REU and supervised several undergraduate reading courses in logic. PI served as one of two postdoctoral assistants for a Math Research Community at Snowbird, and co-organized a one-day logic conference at U. Chicago. PI spoke at a junior high school career day, was interviewed for a high school newspaper, twice taught a "model class" in logic on Parents' Weekend, and served on a panel for local graduate students about postdocs in mathematics.

Agency
National Science Foundation (NSF)
Institute
Division of Mathematical Sciences (DMS)
Application #
1001666
Program Officer
Tomek Bartoszynski
Project Start
Project End
Budget Start
2010-07-01
Budget End
2014-06-30
Support Year
Fiscal Year
2010
Total Cost
$174,659
Indirect Cost
Name
University of Chicago
Department
Type
DUNS #
City
Chicago
State
IL
Country
United States
Zip Code
60637