Tomer Kotek
Applications of logic in graph theory: definability of graph invariants
VCLA will be hosting a RiSE seminar talk by Tomer Kotek on November 29th, 2012.
| DATE: | Thursday, November 29, 2012 |
| TIME: | 17:00 |
| VENUE: | Seminar room Goedel (Favoritenstrasse 9-11, ground floor, access through courtyard) |
ABSTRACT
Logical methods can be used to unify results for individual graph- theoretic objects, by providing meta-theorems which apply to all such objects definable in an appropriate logic. In this talk we discuss graph properties and graph polynomials definable in First Order Logic and Monadic Second Order Logic in terms of their definability and combinatorial meta-theorem. In particular, we show a method of proving non-definability using connection matrices. We extend the results for graph properties by showing a Feferman-Vaught type theorem for First Order Logic extended with counting quantifiers.
