Thicket Density

Seminar: 
Combinatorics Seminar
Event time: 
Thursday, March 1, 2018 - 4:00pm to 5:00pm
Speaker: 
Siddharth Bhaskar
Speaker affiliation: 
Haverford College
Event description: 

Two fundamental dividing lines between "tame" and "wild" structures in model theory, combinatorics, and algebra are the order property and the independence property. In structures (or, more generally, set systems) without the order property, we can associate a realnumber called VC density with each definable set which can be interpreted as a measure of complexity. Thicket density is a new quantity we can assign to each definable set which relates to the order property in exactlythe same way VC density relates to the independence property, complete with a new notion of shatter function which satisfies a Sauer-Shelah typebound. In this talk, we will introduce and state the basic properties of thicket density, describe some recent work connecting it to extant VC-theory, and sketch applications to combinatorics and logic.