论文标题
通过凸优化界定平面图中奇数路径的数量
Bounding the number of odd paths in planar graphs via convex optimization
论文作者
论文摘要
令$ n _ {\ mathcal {p}}（n，h）$表示$ n $顶点平面图中$ h $的最大副本数。自70年代以来，已经对各种图$ h $界限此功能的问题进行了广泛的研究。最近受到很多关注的特殊情况是，$ h $是$ 200万美元+1 $顶点的路径，表示为$ p_ {2m+1} $。本文我们的主要结果是$ n _ {\ Mathcal {p}}（n，p_ {2m+1}）= o（m^{ - m} n^{m+1}）\;。以及考克斯和马丁。证明使用图理论参数以及凸优化理论的（简单）参数。
Let $N_{\mathcal{P}}(n,H)$ denote the maximum number of copies of $H$ in an $n$ vertex planar graph. The problem of bounding this function for various graphs $H$ has been extensively studied since the 70's. A special case that received a lot of attention recently is when $H$ is the path on $2m+1$ vertices, denoted $P_{2m+1}$. Our main result in this paper is that $$ N_{\mathcal{P}}(n,P_{2m+1})=O(m^{-m}n^{m+1})\;.$$ This improves upon the previously best known bound by a factor $e^{m}$, which is best possible up to the hidden constant, and makes a significant step towards resolving conjectures of Gosh et al. and of Cox and Martin. The proof uses graph theoretic arguments together with (simple) arguments from the theory of convex optimization.
