Digraphs with density maximized by transitive tournaments

A prototypical problem in extremal graph theory is determining which graphs are minimizers or maximizers of the density of a fixed graph H, possibly with some additional constraints. For example, considered among most important conjectures in extremal combinatorics, the famous conjecture by Sidorenko and Erdős-Simonovits claims that the density of every bipartite graph H is asymptotically minimized by quasirandom graphs among all graphs with the same edge density.

In this talk we will focus on directed graphs with the property that their homomorphism density is maximized by transitive tournaments. We prove that for any bipartite graph H whose edges are oriented in the same direction between both parts (that is, a directed graph that admits a homomorphism to a directed edge ), the n-vertex transitive tournament maximizes the number of homomorphisms from H among all oriented n-vertex graphs.

Joint work with Igor Balla, Bartlomiej Kielak, Daniel Král’, and Filip Kučerák.

ZOOM link: https://upr-si.zoom.us/j/94947596338?pwd=Ala2JolIlOnXb1jINtebXmk7ZlHjb9.1