论文标题
阈值图最大化同构密度
Threshold Graphs Maximize Homomorphism Densities
论文作者
论文摘要
鉴于固定的图$ h $和[0,1] $中的常数$ c \，我们可以询问哪些图形$ g $带有边缘密度$ c $渐近，从而最大化$ g $中$ h $的同态密度。对于已解决此问题的所有$ H $，最大值总是在两种图表之一上渐近：准星或准胶合。我们表明，对于任何$ h $，最大化$ g $都是渐近图形的图形，而准胶合和准星是最简单的阈值图，只有两个部分。该结果为我们提供了一个统一的框架，可以在图形同态最大化上得出许多结果，其中一些也是最近和使用几种不同方法独立发现的。我们证明存在图$ h $和密度$ c $，因此优化图$ g $既不是准星形明星也不是准胶合，而是依靠Day和Sarkar的结果。我们还表明，对于$ c $，所有图表$ h $最大化的准级，最近也由Gerbner等人证明，对于任何$ k_ {1,2} $的密度始终在Quasi-star或Quasi-clique上最大化，最初是由$ k_ {1,2} $的密度最大化的。最后，我们将结果扩展到统一的超图。
Given a fixed graph $H$ and a constant $c \in [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 $c \in [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.
