Abstract: We introduce a novel measure of complexity of set systems called thicket density which can be seen as an analogue to both VC density and Cantor- Bendixson rank of topological spaces. The analogue to VC theory is quite exact: we have "thicket" versions of dimension, shatter function, and density. In this case, infinite dimensionality captures exactly those set systems which satisfy the order property, as opposed to the independence property. These quantities satisfy several identities (including the Sauer-Shelah dichotomy) that hold verbatim in the VC case. Curiously, the proofs of these identities seem quite different, and we cannot infer the "thicket" versions from the VC versions and vice versa. On the other hand, thicket density can be seen as a finitary version of Cantor-Bendixson rank; in particular, the polynomial/exponential growth dichotomy from "thicket Sauer-Shelah" corresponds to the countable/continuum cardinality dichotomy in the perfect set theorem. (This justifies the name "Finitary Stability.") We even believe there is a notion of "derivative of a set system" that corresponds to the Cantor derivative and induces something like the actual discrete deriative on shatter functions. Finitary stability has at least one application in pure model theory, namely a short proof of the Erdös-Hajnal property for stable graphs, which we might go over, time permitting. Curiously enough, I discovered it not through model theory, but implicitly hidden in a 1989 paper---about something totally different---by Polish computer scientist Jerzy Tiuryn. This talk should be widely accessible, being relatively close to first principles. It describes work that is very current, and I would like to present one proof (of "thicket Sauer-Shelah").
Tuesday November 29, 2016 at 4:00 PM in SEO 427