PIMS-UVic Discrete Math Seminar: Lina Simbaqueba

Given two graphs H and G, the homomorphism density t(H,G) represents the likelihood that a random mapping from V(H) to V(G) is a homomorphism. Sidorenko Conjecture states that for any bipartite graph H, t(H,G) is greater or equal to t(K_2,G)^{e(H)}.

Introducing a binary relation H \geq T if and only if t(H,G)^{e(T)} \geq t(T,G)^{e(H)} for all graphs G, we establish a partial order on the set of non-empty connected graphs. Employing a technique by Kopparty and Rossman, which involves the use of entropy to define a linear program, we derive several necessary and sufficient conditions for two trees T, F satisfy T\geq F. Furthermore, we show how important results and open problems in extremal graph theory can be reframed using this binary relation.

Joint work with Natalie Behage, Gabriel Crudele, and Jonathan Noel.