论文标题
具有几乎线性极函数的边订购图的表征
A characterization of edge-ordered graphs with almost linear extremal functions
论文作者
论文摘要
Gerbner等人启动了Turán型极端问题的系统研究。 ARXIV：2001.00849。他们猜想，订购订单2的边订购森林的极端功能为$ n^{1+o（1）} $。在这里，我们解决了这个猜想，证明了$ n2^{o（\ sqrt {\ log n}）} $更强的上限。这代表了可能的极值功能家族的差距，因为其他禁止的边缘订购的图具有极值功能$ω（n^c）$，对于某些$ c> 1 $。但是，我们的结果可能不是最后一个单词：在这里我们猜想，$ n \ log^{o（1）} n $的更强的上限也适用于同一集的极端功能。
The systematic study of Turán-type extremal problems for edge-ordered graphs was initiated by Gerbner et al. arXiv:2001.00849. They conjectured that the extremal functions of edge-ordered forests of order chromatic number 2 are $n^{1+o(1)}$. Here we resolve this conjecture proving the stronger upper bound of $n2^{O(\sqrt{\log n})}$. This represents a gap in the family of possible extremal functions as other forbidden edge-ordered graphs have extremal functions $Ω(n^c)$ for some $c>1$. However, our result is probably not the last word: here we conjecture that the even stronger upper bound of $n\log^{O(1)}n$ also holds for the same set of extremal functions.
