论文标题
次要图形类的密度是理性的
Densities of minor-closed graph classes are rational
论文作者
论文摘要
对于Graph类$ \ MATHCAL {F} $，令$ ex _ {\ Mathcal {f}}}（n）$表示$ n $ dertices上$ \ Mathcal {f} $中图中的最大边数。我们表明，对于每一个适当的次要图形类$ \ MATHCAL {f} $函数$ ex _ {\ MathCal {f}}}}（n） - δn$最终是周期性的，其中$δ= \ lim_ {n \ to \ to \ to \ for \ to \ infty} ex _ { $ \ mathcal {f} $。这证实了Geelen，Gerards和Whittle的猜想的特殊情况。特别是，每个适当的次要封闭图类别的限制密度都是合理的，它回答了Eppstein的问题。 作为证明的主要步骤，我们表明，每个适当的次要闭合图类都包含一个具有相同限制密度的有界路径的子类，从而确认了第二作者的猜想。 最后，我们研究了在拓扑未成年人中关闭的图形类别的一组限制密度。
For a graph class $\mathcal{F}$, let $ex_{\mathcal{F}}(n)$ denote the maximum number of edges in a graph in $\mathcal{F}$ on $n$ vertices. We show that for every proper minor-closed graph class $\mathcal{F}$ the function $ex_{\mathcal{F}}(n) - Δn$ is eventually periodic, where $Δ= \lim_{n \to \infty} ex_{\mathcal{F}}(n)/n$ is the limiting density of $\mathcal{F}$. This confirms a special case of a conjecture by Geelen, Gerards and Whittle. In particular, the limiting density of every proper minor-closed graph class is rational, which answers a question of Eppstein. As a major step in the proof we show that every proper minor-closed graph class contains a subclass of bounded pathwidth with the same limiting density, confirming a conjecture of the second author. Finally, we investigate the set of limiting densities of classes of graphs closed under taking topological minors.
