rwalke20@uic.edu
My research interests lie in mathematical logic and model theory.
Summary: Building on Pierre Simon's notion of distality, Part I of our thesis introduces distality rank as a property of first-order theories...
and gives examples for each rank m such that 1 ≤ m ≤ ω. For NIP theories, we show that distality rank is invariant under base change. We also define a generalization of type orthogonality called geometry,
so it coincides with
Vapnik-Chervonenkis (VC) dimension and Littlestone dimension have many important implications for model-theoretic classification. Part II of our thesis introduces tree dimension and its leveled variant in order to measure the complexity of leaf sets for finite-height binary trees. We then provide a tight upper bound for the size of an arbitrary leaf set based on its leveled tree dimension. This, in turn, implies the famous Sauer-Shelah Lemma for VC dimension and Bhaskar's version for Littlestone dimension giving clearer insight into why these results place the exact same upper bound on their respective shatter functions. We also fully classify the maximal leaf sets for each tree dimension by isomorphism type. With appropriate modifications, these results extend to higher-arity trees. Finally, we apply our analysis to infinite-height binary trees.
Abstract: Building on Pierre Simon's notion of distality, we introduce distality rank as a property of first-order theories...
and give examples for each rank m such that 1 ≤ m ≤ ω. For NIP theories, we show that distality rank is invariant under base change. We also define a generalization of type orthogonality called geometry,
so it coincides with
Abstract: We introduce tree dimension and its leveled variant in order to measure the complexity of leaf sets in binary trees...
. We then provide a tight upper bound on the size of such sets using leveled tree dimension. This, in turn, implies both the famous Sauer-Shelah Lemma for VC dimension and Bhaskar's version for Littlestone dimension, giving clearer insight into why these results place the exact same upper bound on their respective shatter functions. We also classify the isomorphism types of maximal leaf sets by tree dimension. Finally, we generalize this analysis to higher-arity trees.
April 6, 2022 -- Joint Mathematics Meetings (ASL Special Session: Model-Theoretic Classification)
March 26, 2022 -- AMS Spring Central Sectional Meeting (ASL Special Session: Model Theory and Its Applications)
March 4, 2021 -- Maryland Model Theory Seminar
April 7, 2020 -- Notre Dame Model Theory Seminar
March 27, 2020 -- ASL North American Annual Meeting (Special Session: Model Theory)
December 6, 2019 -- Caltech-UCLA Logic Seminar
October 29, 2019 -- UIC Logic Seminar
Abstract: Vapnik-Chervonenkis dimension and density are two measures of combinatorial complexity which arose from the study of probability theory. During this two-part talk...
, we will define these measures, give some examples, and discuss the consequences of the famous Sauer-Shelah Lemma. We will move into the model-theoretic context to define the VC density of a theory and discuss recent work by Aschenbrenner, Dolich, Haskell, Macpherson, and Starchenko which finds uniform bounds on VC density for RCVF and ACVF.
Abstract: The Szemerédi Regularity Lemma (1976) has proven to be a very important tool in extremal graph theory with many applications to number theory and computer science as well...
. It basically says that the vertices of any finite graph can be partitioned in such a way that the edges between any pair of sets from the partition are uniformly (or randomly) distributed up to a requested nonzero margin of error ε. Furthermore, the size of partition needed to obtain such regularity depends only on ε, not on the size or complexity of the graph. However, in 1997, Timothy Gowers showed that the size of partition needed in the general case grows faster than an exponential tower of height polynomial in
Abstract: So far in the seminar we have been discussing o-minimal theories. For the final weeks, we will broaden our scope to include all NIP theories...
and study the behavior of invariant types. My source will be Pierre Simon's paper of the same name (see link). We will be covering Section 2.
Abstract: Recursive saturation and S-saturation are interesting concepts at the intersection of model theory and recursion theory...
. In this talk, we will define and discuss recursively saturated models, Scott sets, effectively perfect theories, standard systems, and S-saturated models. We will prove that any recursively saturated model of an effectively perfect theory is S-saturated for exactly one Scott set S. It is natural to ask if all Scott sets arise in this fashion. In 1982, Knight and Nadel showed that all Scott sets of size at most ℵ1 arise as the standard system of some nonstandard model of Peano Arithmetic. We will prove a more general version of this result which applies to any computable theory. This closes the question under CH. We will discuss recent progress which closes the question for specific theories when CH is not assumed.
Abstract: A major focus of model theory is the study of definable sets. In this talk we will discuss externally definable sets and Shelah expansions...
. Our goal will be to prove a theorem of Saharon Shelah stating that in the NIP setting, Shelah expansions have quantifier elimination. While proving the theorem, we will review and use several basic techniques involving quantifier-free types, heirs, coheirs, and coheir sequences. We will also discuss some areas of open research concerning externally definable sets.
Abstract: Vapnik-Chervonenkis dimension and density are two measures of combinatorial complexity which arose from the study of probability theory. During this two-part talk...
, we will discuss these measures and their duals both in the classical and model-theoretic contexts, prove the famous Sauer-Shelah Lemma, discuss the relationship between VC dimension and NIP, and time permitting discuss some recent applications and open questions.
