Threshold Graphs Maximize Homomorphism Densities

MaRDI QIDQ6335699zbMATH OpenFDO

Authors Grigoriy Blekherman, Shyamal Patel

Publication date 27 February 2020

Abstract: Given a fixed graph $H$ and a constant $cin[0,1]$, we can ask what graphs $G$ with edge density $c$ asymptotically maximize the homomorphism density of $H$ in $G$. For all $H$ for which this problem has been solved, the maximum is always asymptotically attained on one of two kinds of graphs: the quasi-star or the quasi-clique. We show that for any $H$ the maximizing $G$ is asymptotically a threshold graph, while the quasi-clique and the quasi-star are the simplest threshold graphs, having only two parts. This result gives us a unified framework to derive a number of results on graph homomorphism maximization, some of which were also found quite recently and independently using several different approaches. We show that there exist graphs $H$ and densities $c$ such that the optimizing graph $G$ is neither the quasi-star nor the quasi-clique, reproving a result of Day and Sarkar. We also show that for $c$ large enough all graphs $H$ maximize on the quasi-clique, which was also recently proven by Gerbner et al., and for any $cin[0,1]$ the density of $K_{1,2}$ is always maximized on either the quasi-star or the quasi-clique, which was originally shown by Ahlswede and Katona. Finally, we extend our results to uniform hypergraphs.

This page was built for publication: Threshold Graphs Maximize Homomorphism Densities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6335699)