Higher classification theory in model theory and applications

About This Grant

Model theory studies the ways in which mathematical objects can be defined in some restricted formal language, and what structural properties are implied by these definability assumptions. It provides methods of converting asymptotic questions about finite structures into qualitative questions about the shape, volume or dimension of certain limiting infinite objects. This method of study originated in questions on foundations of mathematics, but in recent years it has found important applications in the study of some central objects of classical mathematics and computer science. The project investigates further these connections, with the major motivation of extending the existing techniques from binary structures (graphs) to structures of higher arity (hypergraphs), which represent a mathematical way of describing more complex networks in which interactions happen not just between two nodes at a time, but between multiple nodes simultaneously. This study will both deepen and extend the scope for applications of the infinitary model-theoretic machinery to questions in combinatorics of geometrically or algebraically arising hypergraphs, and conversely for applications of combinatorics to open questions in model theory. The project will involve training of graduate and undergraduate students. Shelah's classification program isolates combinatorial dividing lines (stability, distality, NIP, etc.) separating mathematical structures exhibiting various degrees of Gödelian behavior, from the tame ones in which one develops a “geometric” theory akin to algebraic geometry for definable sets in such structures. These tameness notions in Shelah’s classification theory are typically given by restrictions on the combinatorial complexity of definable binary relations. Many of the central results in graph combinatorics can be then improved dramatically if one restricts to graphs on the tame side of this classification, in particular to graphs arising from various algebraic or geometric configurations. The PI will investigate a higher generalization of Shelah's classification theory, where the restriction is only put on higher arity relations, focusing on n-dependence (with the case n=1 corresponding to the well studied class of NIP structures), n-stability, n-distality, and n-amalgamation, as opposed to the traditional binary case n=1. This will be applied to questions in extremal combinatorics of hypergraphs definable in various tame structures (via Keisler measures), as well as to generalizations of the polynomial expansion phenomena (Elekes-Szabó type theorems), and to the study of algebraic structures such as groups and fields definable in n-tame theories. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.