Tuesday, Feb 15, 4pm ET (9pm GMT, 10am Wed NZDT)
Chun-Hung Liu, Texas A&M University
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.