Graph profiles and their tropicalizations

Zoom Link

The number of homomorphisms from a graph H to a graph G, denoted by hom(H;G), is the number of maps from V(H) to V(G) that yield a graph homomorphism, i.e., that map every edge of H to an edge of G. Given a fixed collection of finite simple graphs {H_1, ..., H_s}, the graph profile is the set of all vectors (hom(H_1; G), ..., hom(H_s; G)) as G varies over all graphs. We will first discuss graph profiles, which are objects that essentially allow us to understand all polynomial inequalities in homomorphism numbers that are valid on all graphs. Profiles can be extremely complicated; for instance the full profile of any triple of connected graphs is not known. To simplify these objects, we introduce their tropicalization which we show is a closed convex cone that still captures interesting combinatorial information. We explicitly compute these tropicalizations for some sets of graphs, and use those results to answer some questions in extremal graph theory.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.