PURE PAIRS. IX. TRANSVERSAL TREES

Fix k > 0, and let G be a graph, with vertex set partitioned into k subsets (``blocks"") of approximately equal size. An induced subgraph of G is ``transversal"" (with respect to this partition) if it has exactly one vertex in each block (and therefore it has exactly k vertices). A ``pure pair"" in G is a pair X, Y of disjoint subsets of V (G) such that either all edges between X, Y are present or none are; and in the present context we are interested in pure pairs (X, Y ) where each of X, Y is a subset of one of the blocks, and not the same block. This paper collects several results and open questions concerning how large a pure pair must be present if various types of transversal subgraphs are excluded.