Hunter Chase : Binary sequences and trees in model theory

Posted by Hunter Chase , part of the Louise Hay Logic Seminar.

At

April 12, 2018, 4 p.m.

In

SEO 427

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.