Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.
Résumé du séminaire du Mardi 18 Octobre 2016
A Dual to a Classical Graph Homomorphism Theorem of Lovász
par Stefan Mengel (CNRS et Université d’Artois)
Graph homomorphism is a classical object of study in structural graph theory, with applications in many areas, like constraint satisfaction and database theory.
In this talk, I will first give a short introduction into graph homomorphisms and discuss some computational aspects. Then I will present a result that is dual to a classical result of Lovász; it roughly says that every graph is uniquely described by the number of homomorphisms it has to other graphs. I will close by sketching an application of this result in counting complexity.
This is joint work with Hubie Chen.