Pure pairs. II: Excluding all subdivisions of a graph

DOI10.1007/S00493-020-4024-1MaRDI QIDQ2043764zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Alex Scotty, Sophie Spirkl, Paul Seymour

Publication date 3 August 2021

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.01060

Erdős-Hajnal conjecture pure pairs subdivisions of a graph

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Abstract: We prove for every graph H there exists a>0 such that, for every graph G with at least two vertices, if no induced subgraph of G is a subdivision of H, then either some vertex of G has at least a|G| neighbours, or there are two disjoint sets A,B of at least a|G| vertices such that no edge joins A and B. It follows that for every graph H, there exists c>0 such that for every graph G, if no induced subgraph of G or its complement is a subdivision of H, then G has a clique or stable set of cardinality at least |G|^c. This is related to the Erdos-Hajnal conjecture.

Review text

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)].

Recommendations

Cites work

Cited in

(14)

This page was built for publication: Pure pairs. II: Excluding all subdivisions of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2043764)