Blog Archives

Topic Archive: NIP

Model theory seminarCUNY Logic WorkshopFriday, March 13, 20152:00 pmGC 6417

Sergei Starchenko

Ramsey-type theorems in certain NIP theories

University of Notre Dame

In the paper “Crossing patterns of semi-algebraic sets” (J. Combin. Theory Ser. A 111, 2005) Alon et al. showed that families of graphs with the edge relation given by a semialgebraic relation of bounded complexity satisfy a stronger regularity property than arbitrary graphs. In this talk we show that this can be generalized to families of graphs whose edge relation is uniformly definable in a structure satisfying a certain model theoretic property called distality.

This is a joint work with A. Chernikov.

Model theory seminarFriday, May 9, 201412:30 pmGC6417

Artem Chernikov

VC-dimension in model theory and other subjects

Université Paris Diderot - Paris 7

Finite VC-dimension, a combinatorial property of families of
sets, was discovered simultaneously by Vapnik and Chervonenkis in the
context of probabilistic learning theory, and by Shelah in model
theory in the context of classification of unstable first-order
theories (where it is called NIP). From the model theoretic point of
view it is a very attractive setting generalizing stability and
o-minimality, and admitting a deep theory which had been recently used
to study ordered and valued fields. I will give an overview of some
results around NIP related to set theory (counting Dedekind cuts in
infinite linear orders), topological dynamics and compression schemes
in computational learning theory.

Model theory seminarFriday, November 15, 201312:30 pmGC 6417

Yevgeniy Vasilyev

On dense independent subsets of geometric structures

Memorial University of Newfoundland and Christopher Newport University

We consider expansions of geometric theories obtained by adding a predicate distinguishing a “dense” independent subset, generalizing a construction introduced by A. Dolich, C. Miller and C. Steinhorn in the o-minimal context. The expansion preserves many of the properties related to stability, simplicity, rosiness and NIP. We also study the structure induced on the predicate, and show that despite its geometric triviality, it inherits most of the “combinatorial” complexity of the original theory. This is a joint work with Alexander Berenstein.