Reading Seminar

We willl study further the concept of L-definability for a fixed logic L, defined in the last lecture. We will use the method of Ehrenfeuct-Fraisse games to prove lower bounds for particular graph properties, e.g. that connectivity is not definable in first-order logic. Using these lower bounds, we will show that conjectures about logics capturing classes have important consequences in complexity theory.