Louise Hay Logic Seminar
Hunter Chase
UIC
Binary sequences and trees in model theory
Abstract: VC-dimension and Shelah's 2-rank (also known as Littlestone or thicket dimension) are important measures of complexity associated with the NIP/IP and stable/unstable dividing lines. We examine these through the lens of binary trees and sequences. We introduce the concept of banned sequence problems as a tool to obtain new proofs of the Sauer-Shelah lemma and some of its variants. We use these results to modestly improve a result of Malliaris and Terry on type trees of stable graphs and prove a new variant of the Sauer-Shelah lemma for the op-rank setting of Guingona and Hill.
This work is joint with James Freitag.
Thursday April 12, 2018 at 4:00 PM in SEO 427