Speaker : Professor Jaroslav Ne?et?il (Charles University, Prague)
Title : Homomorphism Preservation Theorems in Classes of Structures
Time : 2011-03-04 (Fri) 15:00 - 16:00
Place : Seminar Room 722, Institute of Mathematics (NTU Campus)
Abstract: Homomorphism preservation (HP) give descriptive characterization of FO definable classes of structures defined by homomorphism. Extending work of Rossman and Atserias, Dawar and Kolaits we study the restricted HP and use this for characterization FO definable Constraint Satisfaction Problems. The essential part of this study is related to sparse graphs and structures and it is combinatorial. This is a joint work with P. Ossona de Mendez (Paris).