Applications of logic in graph theory: definability of graph invariants

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.

Posted in RiSE Seminar