Logic, Ramsey Theory, and Relational Structures

University Of Denver, Denver CO

Investigators

Abstract

Ramsey Theory is a central area of mathematics aptly characterized by Motzkin's motto, "Complete disorder is impossible." Ramsey's Theorem states that given any coloring of all pairs of natural numbers into finitely many colors, there is an infinite subset in which all pairs have the same color. Since its inception, Ramsey theory has developed in multiple directions, often appearing as the core content in solutions to deep problems from a wide range of mathematical disciplines. This project utilizes techniques in mathematical logic to more fully develop Ramsey theory of infinite relational structures. A major motivation is to find dividing lines between those infinite structures which act like the natural numbers in the sense of possessing analogues of Ramsey's theorem, and those which do not. Of particular interest is the advancement of Ramsey theory for structures with forbidden configurations. Progress on infinite structures works in tandem with progress in mathematical logic and topology, creating new pathways between several areas of mathematics. This project includes some important questions which are suitable for graduate students and early career researchers, thus providing opportunities to broaden participation of well-trained mathematicians via the PI's mentoring. This research program will develop the Ramsey theory of infinite relational structures, especially those with forbidden configurations, an area which had been largely impervious to investigations prior to the PI's recent solution for the universal homogeneous triangle-free graph. This will involve constructing new types of trees which code homogeneous relational structures and using the technique of forcing to produce (in ZFC) Ramsey theorems for these classes of trees. These new techniques will be used obtain better bounds for finite structural Ramsey theory. Computability theoretic strengths of varying Ramsey statements, and connections with classification schemes in model theory will be investigated. Infinitary Ramsey theory will continue to be developed with a broad spectrum of implications for and applications to other areas of mathematics. The techniques developed, involving simultaneous uses of logic, combinatorics and topology, will create new pathways between these areas of mathematics. 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.