Homomorphism counts in robustly sparse graphs

Time: 09:00 to  12:15 Ngày 17/02/2023

Venue/Location: Online via Zoom

Speaker: Chun-Hung Liu (Texas A&M University, USA)

Time: 9:00 am - Friday, 17/2/2023

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 from H.

Seminar: Online ZOOM

ZOOM link: https://us02web.zoom.us/j/87167950828?pwd=UFpHTkcwaDZWTndsRGloRE5yN2tIdz09 (updated)

Meeting ID: 871 6795 0828

Passcode: 352266

Website Seminar: https://sites.google.com/view/ktv-seminar/