Pure pairs. VI: Excluding an ordered tree

Abstract: 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 | / l o g | 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)}

.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Pure pairs. VI: Excluding an ordered tree