Date:
Thursday, November 29, 2012
Speaker:
Tomer Kotek
Venue: TU Wien
Logical methods can be used to unify results for individual graph-theoretic objects, by providing meta-theorems which apply to all suchobjects definable in an appropriate logic. In this talk we discuss graphproperties and graph polynomials definable in First Order Logic and MonadicSecond Order Logic in terms of their definability and combinatorialmeta-theorem. In particular, we show a method of proving non-definabilityusing connection matrices. We extend the results for graph properties byshowing a Feferman-Vaught type theorem for First Order Logic extended withcounting quantifiers.
