# Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs

@article{Chudnovsky2020PurePI, title={Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs}, author={M. Chudnovsky and Jacob Fox and Alex D. Scott and Paul D. Seymour and Sophie Theresa Spirkl}, journal={J. Graph Theory}, year={2020}, volume={95}, pages={315-340} }

A graph is "$H$-free" if it has no induced subgraph isomorphic to $H$. A conjecture of Conlon, Fox and Sudakov states that for every graph $H$, there exists $s>0$ such that in every $H$-free graph with $n>1$ vertices, either some vertex has degree at least $sn$, or there are two disjoint sets of vertices, of sizes at least $sn^s$ and $sn$, anticomplete to each other. We prove this holds for a large class of graphs $H$, and we prove that something like it holds for all graphs $H$.
Say $H$ is… Expand

#### Topics from this paper

#### 5 Citations

Towards Erdős-Hajnal for Graphs with No 5-Hole

- Computer Science, Mathematics
- Comb.
- 2019

This paper improves the general bound of Erdos and Hajnal, that for all H, $H$, $\max(\alpha(G),\omega(G))\ge 2^{\Omega(\sqrt{\log n })}$ if $G$ is $H$-free. Expand

Ramsey goodness of books revisited

- Mathematics
- 2021

The Ramsey number r(G,H) is the minimum N such that every graph onN vertices contains G as a subgraph or its complement contains H as a subgraph. For integers n ≥ k ≥ 1, the k-book Bk,n is the graph… Expand

Pure pairs. IX. Bonsai trees

- 2021

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 “bonsai” (with respect to this partition) if it has… Expand

Pure pairs. IX. Transversal trees

- Mathematics
- 2021

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… Expand

3 1 O ct 2 02 1 Pure pairs . IX . Transversal trees

- 2021

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… Expand

#### References

SHOWING 1-10 OF 38 REFERENCES

Trees and linear anticomplete pairs

- Mathematics
- 2018

We prove a conjecture of Liebenau, Pilipczuk, and the last two authors, that for every forest $H$ there exists $\epsilon>0$, such that if $G$ has $n\ge 2$ vertices and does not contain $H$ as an… Expand

Pure pairs. II. Sparse graphs without linear anticomplete pairs

- 2020

We prove for every graph H there exists > 0 such that, for every graph G with |G| ≥ 2, if no induced subgraph of G is a subdivision of H, then either some vertex of G has at least |G| neighbours, or… Expand

Towards Erdős-Hajnal for Graphs with No 5-Hole

- Computer Science, Mathematics
- Comb.
- 2019

This paper improves the general bound of Erdos and Hajnal, that for all H, $H$, $\max(\alpha(G),\omega(G))\ge 2^{\Omega(\sqrt{\log n })}$ if $G$ is $H$-free. Expand

Sparse graphs without linear anticomplete pairs

- Mathematics
- 2018

We prove that for every graph H there exists c>0 such that, for every graph G, if G has no clique or stable set of size |G|^c, then either G or its complement contains an induced subdivision of H.… Expand

On spanned subgraphs of graphs

- Mathematics
- 1977

The aim of this note is to prove some theorems of the following type : We assume that C is a class of finite graphs satisfying certain assymptotic conditions saying that both c and its complement are… Expand

Caterpillars in Erdős-Hajnal

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 2019

For every caterpillar subdivision T, there exists c > 0 such that for every graph G containing neither of T and its complement as an induced subgraph, G has a clique or stable set with at least | V ( G ) | c vertices. Expand

Recent developments in graph Ramsey theory

- Mathematics, Computer Science
- Surveys in Combinatorics
- 2015

There has been a great deal of recent progress on the study of Ramsey numbers and their variants, spurred on by the many advances across extremal combinatorics. Expand

Induced Ramsey-type theorems

- Mathematics
- 2008

Abstract We present a unified approach to proving Ramsey-type theorems for graphs with a forbidden induced subgraph which can be used to extend and improve the earlier results of Rodl, Erdős–Hajnal,… Expand

Ramsey-type theorems

- Computer Science, Mathematics
- Discret. Appl. Math.
- 1989

Abstract In this paper we will consider Ramsey-type problems for finite graphs, r -partitions and hypergraphs. All these problems ask for the existence of large homogeneous (monochromatic)… Expand

On universality of graphs with uniformly distributed edges

- Computer Science, Mathematics
- Discret. Math.
- 1986

Abstract We prove that sufficiently large graphs with sufficiently many ‘uniformly distributed’ edges contain all small graphs as induced subgraphs. This fails to be true for k-uniform hypergraphs… Expand