Pure pairs. V: Excluding some long subdivision

DOI10.1007/S00493-023-00025-8MaRDI QIDQ6081383zbMATH OpenOpenAlexFDO

Authors Alex Scott, Paul Seymour, Sophie Spirkl

Publication date 4 October 2023

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

branch-lengthErdős-Hajnal conjectureinduced subgraphslong subdivisionordered graphstrees

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) 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) Ramsey theory (05D10)

Abstract: A pure pair in a graph $G$ is a pair $A,B$ of disjoint subsets of $V(G)$ such that $A$ is complete or anticomplete to $B$. Jacob Fox showed that for all $epsilon>0$, there is a comparability graph $G$ with $n$ vertices, where $n$ is large, in which there is no pure pair $A,B$ with $|A|,|B|geepsilonn$. He also proved that for all $c>0$ there exists $epsilon>0$ such that for every comparability graph $G$ with $n>1$ vertices, there is a pure pair $A,B$ with $|A|,|B|geepsilon{n}^{1-c}$; and conjectured that the same holds for every perfect graph $G$. We prove this conjecture and strengthen it in several ways. In particular, we show that for all $c>0$, and all $el{l}_1,el{l}_{2}ge4c^{-1}+9$, there exists $epsilon>0$ such that, if $G$ is a graph with $n>1$ vertices and no hole of length exactly $el{l}_1$ and no antihole of length exactly $el{l}_2$, then there is a pure pair $A,B$ in $G$ with $|A|geepsilonn$ and $|B|geepsilon{n}^{1-c}$. This is further strengthened, replacing excluding a hole by excluding some long subdivision of a general graph.

Review text

Two disjoint sets \(A\) and \(B\) of vertices of a graph \(G\) form a pure pair in \(G\) if the possible edges between \(A\) and \(B\) are either all present in \(G\) or all absent. Which graphs have large pure pairs? \textit{J. Fox} [Order 23, No. 2--3, 197--209 (2006; Zbl 1108.06002)] proved that for every sufficiently large positive integer \(n\) and every \(n\)-vertex comparability graph \(G\) there is a pure pair \(A\), \(B\) in \(G\) with \(\vert A\vert ,\vert B\vert \ge n^{1-o(1)}\), and conjectured a similar bound for all perfect graphs. Part V of a series of at least 10 papers on pure pairs proves this conjecture, and strengthenings thereof. Let the branch-length of a forbidden induced subgraph \(H\) be the minimum of the length of a shortest cycle in \(H\) and the shortest distance between vertices of degree \(>2\) in \(H\). Let \(c>0\) be such that \(1/c\) is integral, and let \(H_1\) and \(H_2\) be graphs of branch-length \(>4/c+5\). There is an \(\varepsilon>0\) such that every \(H_1\)-free and \(\bar{H}_2\)-free graph on \(n>1\) vertices has a pure pair \(A\), \(B\) with \(\vert A\vert \ge \varepsilon n\) and \(\vert B\vert \ge \varepsilon n^{1-c}\). The connection to the Erdős-Hajnal conjecture is explained in part II by \textit{M. Chudnovsky} et al. [Combinatorica 41, No. 3, 379--405 (2021; Zbl 1488.05427)].

Recommendations

• Pure pairs. II: Excluding all subdivisions of a graph
• Pure pairs. VI: Excluding an ordered tree
• Pure pairs. I: Trees and linear anticomplete pairs
• Pure Pairs. IX. Transversal Trees
• Pure pairs. III. Sparse graphs with no polynomial‐sized anticomplete pairs

Cited in

(4)

• Erdös-Hajnal properties for powers of sparse graphs
• Pure Pairs. IX. Transversal Trees
• A multipartite analogue of Dilworth's theorem
• Pivot-minors and the Erdős-Hajnal conjecture

This page was built for publication: Pure pairs. V: Excluding some long subdivision

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