论文标题
表面的子图密度
Subgraph densities in a surface
论文作者
论文摘要
给定一个固定的图形$ h $，该$ h $嵌入了表面$σ$，$ n $ vertex Graph $ g $的$ h $的最大副本是嵌入$σ$的？我们证明答案为$θ（n^{f（h）}）$，其中$ f（h）$是一个$ h $的“ flap-number”的图形不变，该图独立于$σ$。这同时回答了Eppstein（1993）提出的两个开放问题。当$ h $是一个完整的图表时，我们给出更精确的答案。
Given a fixed graph $H$ that embeds in a surface $Σ$, what is the maximum number of copies of $H$ in an $n$-vertex graph $G$ that embeds in $Σ$? We show that the answer is $Θ(n^{f(H)})$, where $f(H)$ is a graph invariant called the `flap-number' of $H$, which is independent of $Σ$. This simultaneously answers two open problems posed by Eppstein (1993). When $H$ is a complete graph we give more precise answers.
