论文标题
纯对。 vi。不包括有订单的树
Pure pairs. VI. Excluding an ordered tree
论文作者
论文摘要
图$ g $中的纯对是一对$（z_1，z_2）$ discoint的顶点集，以便$ z_1 $中的每个顶点都与$ z_2 $中的每个顶点相邻，或者在$ z_1 $和$ z_2 $之间没有边缘。借助Maria Chudnovsky，我们最近证明，对于每个森林$ f $，每个图$ g $，至少有两个不包含$ f $的顶点或它的补充，因为诱导子杂语具有纯对$（z_1，z_2）$，带有$ | z_1 | z_1 |，| z_1 |，| z_2 | z_2 | $ z_2 | $ linear in $ | g | $ | $ | $ | $ | $。 在这里，我们调查了{\ em Ordered} Graph $ g $中关于纯对的些什么，当我们排除有序的森林$ f $及其作为诱导子图的补充时。福克斯表明，不需要有线性纯对。但是Pach和Tomon表明，如果$ f $是单调路径，那么有一对大小的$ c | g |/\ log | g | $。我们将其推广到所有有序的森林，以稍差的范围：我们证明，对于每个有序的森林$ f $，每个有序的图形$ g $，至少有两个不包含$ f $的顶点或它的补充，因为诱导的子杂文都有一对纯粹的大小$ | g |^{1-o（1-o（1-o（1）} $。
A pure pair in a graph $G$ is a pair $(Z_1,Z_2)$ of disjoint sets of vertices such that either every vertex in $Z_1$ is adjacent to every vertex in $Z_2$, or there are no edges between $Z_1$ and $Z_2$. With Maria Chudnovsky, we recently proved that, for every forest $F$, every graph $G$ with at least two vertices that does not contain $F$ or its complement as an induced subgraph has a pure pair $(Z_1,Z_2)$ with $|Z_1|,|Z_2|$ linear in $|G|$. Here we investigate what we can say about pure pairs in an {\em ordered} graph $G$, when we exclude an ordered forest $F$ and its complement as induced subgraphs. Fox showed that there need not be a linear pure pair; but Pach and Tomon showed that if $F$ is a monotone path then there is a pure pair of size $c|G|/\log |G|$. We generalise this to all ordered forests, at the cost of a slightly worse bound: we prove that, for every ordered forest $F$, every ordered graph $G$ with at least two vertices that does not contain $F$ or its complement as an induced subgraph has a pure pair of size $|G|^{1-o(1)}$.
