Journal title
Combinatorica
DOI
10.1007/s00493-023-00025-8
Issue
3
Volume
43
Last updated
2024-03-28T21:49:01.067+00:00
Page
571-593
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|\ge \epsilon n$. 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|\ge \epsilon 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 $\ell_1, \ell_2\ge
4c^{-1}+9$, there exists $\epsilon>0$ such that, if $G$ is a graph with $n>1$
vertices and no hole of length exactly $\ell_1$ and no antihole of length
exactly $\ell_2$, then there is a pure pair $A,B$ in $G$ with $|A|\ge \epsilon
n$ and $|B|\ge \epsilon n^{1-c}$. This is further strengthened, replacing
excluding a hole by excluding some long subdivision of a general graph.
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|\ge \epsilon n$. 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|\ge \epsilon 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 $\ell_1, \ell_2\ge
4c^{-1}+9$, there exists $\epsilon>0$ such that, if $G$ is a graph with $n>1$
vertices and no hole of length exactly $\ell_1$ and no antihole of length
exactly $\ell_2$, then there is a pure pair $A,B$ in $G$ with $|A|\ge \epsilon
n$ and $|B|\ge \epsilon n^{1-c}$. This is further strengthened, replacing
excluding a hole by excluding some long subdivision of a general graph.
Symplectic ID
1176186
Submitted to ORA
Off
Favourite
Off
Publication type
Journal Article
Publication date
16 Jun 2023