Graphs and Matroids Seminar - Chun-Hung Liu

Title: Homomorphism counts in robustly sparse graphs

Abstract:

For a fixed graph H and for arbitrarily large host graphs G, the number of homomorphisms from H to G and the number of subgraphs isomorphic to H contained in G have been extensively studied when the host graphs are allowed to be dense. This talk addresses the case when the host graphs are robustly sparse. We determine, up to a constant multiplicative error, the maximum number of subgraphs isomorphic to H contained in an n-vertex graph in any fixed hereditary graph class with bounded expansion. This result solves a number of open questions and can be generalized to counting the number of homomorphisms.