Pure pairs. II: Excluding all subdivisions of a graph (Q2043764): Difference between revisions

This paper is part of a substantial ongoing sequence of papers by (various subsets of) the authors on so-called pure pairs. An ideal \(I\) of graphs is a set of graphs closed under isomorphism and taking induced subgraphs. For example, if \(H\) is a fixed graph, the \(H\)-free graphs (i.e. those not containing any induced subgraph isomorphic to \(H\)) is an ideal. The Erdős-Hajnal conjecture states that the ideal \(I\) of \(H\)-free graphs has the Erdős-Hajnal property, that is for every fixed graph \(H\) there is \(\epsilon(H)>0\) such that every graph \(G\) (with \(\vert V(G)\vert=n\)) it contains either a clique or an independent set of order at least \(n^{\epsilon(H)}\) (much larger than the order of magnitude \(\log(n)\) guaranteed for general graphs). A stronger property -- the strong Erdős-Hajnal property -- is that there is some \(\epsilon>0\) such that every \(n\)-vertex graph with at least two vertices in \(I\) contains a pure pair of sets \(A\), \(B\) with \(\min\{\vert A\vert, \vert B\vert\}\geq \epsilon n\), where two disjoint sets \(A\) and \(B\) of vertices form a pure pair if either all \(\vert A\vert \vert B\vert\) possible edges from \(A\) to \(B\) are present, or there are no edges from \(A\) to \(B\) (``all-or-nothing'' property). \par The important main result of the paper under review is that, for every fixed graph \(H\), the ideal of graphs \(G\) such that neither \(G\) nor its complement \(\overline{G}\) contains an induced subdivision of \(H\) has the strong Erdős-Hajnal property. In fact stronger results are proved. Note that the ideal of graphs which do not contain an induced subdivision of \(H\) does not necessarily have the strong Erdős-Hajnal property. A key role in the proof is played by a result from \textit{V. Rödl} [Discrete Math. 59, 125--134 (1986; Zbl 0619.05035)] which says one can assume that the graph is either quite sparse or quite dense and splitting into two cases, one where every small ball has small mass, and another where at least one small ball has substantial mass. \par For Part I see [the authors, Adv. Math. 375, Article ID 107396, 20 p. (2020; Zbl 1458.05171)].