论文标题
erdős-hajnal-type的有序路径结果
Erdős-Hajnal-type results for ordered paths
论文作者
论文摘要
有序的图是其顶点集上有线性排序的图形。我们证明，对于每个正整数$ k $，存在一个常数$ c_k> 0 $，因此，$ n $顶点上的任何有序的图形$ g $都没有$ g $和其补充的属性包含诱导的$ k $的单调路径，具有$ k $的单调路径，具有一个clique或独立的大小$ n^{c_k} $。这加强了Bousquet，Lagoutte和Thomassé的结果，他们证明了无序图的类似结果。 上述论文的一个关键思想是表明，在$ n $顶点上的任何无序的图形都不包含诱导的尺寸$ k $的路径，并且最高度为$ c（k）n $，对于某些小$ c（k）> 0 $，包含两个不相交的线性尺寸，它们之间没有边缘。该方法无法用于有序图，因为FOX的构造是$ k \ geq 3 $的类似语句。我们提供了进一步的示例，该陈述如何在有序图中避免其他有序树的订购图。
An ordered graph is a graph with a linear ordering on its vertex set. We prove that for every positive integer $k$, there exists a constant $c_k>0$ such that any ordered graph $G$ on $n$ vertices with the property that neither $G$ nor its complement contains an induced monotone path of size $k$, has either a clique or an independent set of size at least $n^{c_k}$. This strengthens a result of Bousquet, Lagoutte, and Thomassé, who proved the analogous result for unordered graphs. A key idea of the above paper was to show that any unordered graph on $n$ vertices that does not contain an induced path of size $k$, and whose maximum degree is at most $c(k)n$ for some small $c(k)>0$, contains two disjoint linear size subsets with no edge between them. This approach fails for ordered graphs, because the analogous statement is false for $k\geq 3$, by a construction of Fox. We provide further examples how this statement fails for ordered graphs avoiding other ordered trees as well.
