# The Erdős–Hajnal conjecture for paths and antipaths

Nicolas Bousquet, Aurélie Lagoutte, Stéphan Thomassé

## ► To cite this version:

Nicolas Bousquet, Aurélie Lagoutte, Stéphan Thomassé. The Erdős–Hajnal conjecture for paths and antipaths. Journal of Combinatorial Theory, Series B, 2015, 113, pp.261-264. 10.1016/j.jctb.2015.01.001. hal-01134469

HAL Id: hal-01134469

https://hal.science/hal-01134469

Submitted on 23 Mar 2015

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The Erdős-Hajnal Conjecture for Paths and Antipaths

N. Bousquet$^a$, A. Lagoutte$^{b,1,*}$, S. Thomassé$^{b,1}$

$^a$AlGCo project-team, CNRS, LIRMM, 161 rue Ada, 34392 Montpellier France.

$^b$LIP, UMR 5668 ENS Lyon - CNRS - UCBL - INRIA, Université de Lyon, 46, allée d'Italie, 69364 Lyon France.

## Abstract

We prove that for every $k$, there exists $c_k > 0$ such that every graph $G$ on $n$ vertices with no induced path $P_k$ or its complement $\bar{P}_k$ contains a clique or a stable set of size $n^{c_k}$.

**Keywords:** Erdős-Hajnal, path, antipath, Ramsey

An $n$-graph is a graph on $n$ vertices. For every vertex $x$, $N(x)$ denotes the neighborhood of $x$, that is the set of vertices $y$ such that $xy$ is an edge. The degree $\deg(x)$ is the size of $N(x)$. In this note, we only consider classes of graphs that are closed under induced subgraphs. Moreover a class $\mathcal{C}$ is strict if it does not contain all graphs. It is said to have the (weak) Erdős-Hajnal property if there exists some $c > 0$ such that every graph of $\mathcal{C}$ contains a clique or a stable set of size $n^c$ where $n$ is the size of $G$. The Erdős-Hajnal conjecture [8] asserts that every strict class of graphs has the Erdős-Hajnal property; see [3] for a survey. This fascinating question is open even for graphs not inducing a cycle of length five. When excluding a single graph $H$, Alon, Pach and Solymosi showed in [2] that it suffices to consider prime $H$, namely graphs without nontrivial modules (a module is a subset $V'$ of vertices such that for every $x, y \in V'$, $N(x) \setminus V' = N(y) \setminus V'$). A natural approach is then to study classes of graphs with intermediate difficulty, hoping to get a proof scheme which could be extended. A natural prime candidate to forbid is certainly the path. Unfortunately, even excluding the path on five vertices seems already hard. Chudnovsky and Zwols studied the class $\mathcal{C}_k$ of graphs not inducing the path $P_k$ on $k$ vertices or its complement $\bar{P}_k$. They proved the Erdős-Hajnal property for $P_5$ and $\bar{P}_6$-free graphs [7]. This was extended for $P_5$ and $\bar{P}_7$-free graphs by Chudnovsky and Seymour [6]. Moreover structural results have been provided for $\mathcal{C}_5$ [4, 5]. We show in this note that for every fixed $k$, the class $\mathcal{C}_k$ has the Erdős-Hajnal property. An $n$-graph is an $\varepsilon$-stable set if it has at most $\varepsilon(\binom{n}{2})$ edges. The complement of an $\varepsilon$-stable set is an $\varepsilon$-clique. Fox and Sudakov [11] proved the following:

**Theorem 1 ([11]).** For every positive integer $k$ and every $\varepsilon \in (0, 1/2)$, there exists $\delta > 0$ such that every $n$-graph $G$ satisfies one of the following:

* $G$ induces all graphs on $k$ vertices.

* $G$ contains an $\varepsilon$-stable set of size at least $\delta n$.

* $G$ contains an $\varepsilon$-clique of size at least $\delta n$.

Note that a stronger result was previously showed by Rödl [14] using Szemerédi's regularity lemma, but Fox and Sudakov's proof provides a much better quantitative estimate ($\delta = 2^{-ck(\log 1/\varepsilon)^2}$ for some constant $c$). They further conjecture that a polynomial estimate should hold, which would imply the Erdős-Hajnal conjecture.

<footnote>*Corresponding author</footnote>

<footnote>Email addresses: nicolas.bousquet@lirmm.fr (N. Bousquet), aurelie.lagoutte@ens-lyon.fr (A. Lagoutte), stephan.thomasse@ens-lyon.fr (S. Thomassé)</footnote>

<footnote n="1">¹These authors were partially supported by ANR Projet STINT under Contract ANR-13-BS02-0007.</footnote>
In a graph $G$, a biclique of size $t$ is a (not necessarily induced) complete bipartite subgraph $(X, Y)$ such that both $|X|, |Y| \ge t$. Observe that it does not require any condition inside $X$ or inside $Y$. Erdős, Hajnal and Pach proved in [9] that for every strict class $C$, there exists some $c > 0$ such that for every $n$-graph $G$ in $C$, $G$ or its complement $\bar{G}$ contains a biclique of size $n^c$. This "half" version of the conjecture was improved to a "three quarter" version by Fox and Sudakov [10], where they show the existence of a polynomial size stable set or biclique. Following the notations of [12], a class $C$ of graphs has the strong Erdős-Hajnal property if there exists a constant $c$ such that for every $n$-graph $G$ in $C$, $G$ or $\bar{G}$ contains a biclique of size $cn$. It was proved that having the strong Erdős-Hajnal property implies having the (weak) Erdős-Hajnal property:

**Theorem 2 ([1, 12]).** If $C$ is a class of graphs having the strong Erdős-Hajnal property, then $C$ has the weak Erdős-Hajnal property.

*Proof.* (sketch) Let $c$ be the constant of the strong Erdős-Hajnal property, meaning that for every $n$-graph $G$ in $C$, $G$ or $\bar{G}$ contains a biclique of size $cn$. Let $c' > 0$ be such that $c' \ge 1/2$. We prove by induction that every $n$-graph $G$ in $C$ induces a $P_4$-free graph of size $n^{c'}$. By our hypothesis on $C$, there exists, say, a biclique $(X, Y)$ of size $cn$ in $G$. Applying the induction hypothesis inside both $X$ and $Y$, we form a $P_4$-free graph on $2(cn)^{c'} \ge n^{c'}$ vertices. The Erdős-Hajnal property of $C$ follows from the fact that every $P_4$-free $n^{c'}$-graph has a clique or a stable set of size at least $n^{c'}/2$. $\square$

We now prove our main result. The key lemma is an adaptation of Gyárfás’ proof of the $\chi$-boundedness of $P_k$-free graphs, see [13].

**Lemma 3.** For every $k \ge 2$, there exists $\varepsilon_k > 0$ and $c_k$ (with $0 < c_k \le 1/2$) such that every connected $n$-graph $G$ with $n \ge 2$ satisfies one of the following:

* There exists a vertex of degree more than $\varepsilon_k n$.

* For every vertex $v$, $G$ contains an induced $P_k$ starting at $v$.

* The complement $\bar{G}$ of $G$ contains a biclique of size $c_k n$.

*Proof.* We proceed by induction on $k$. For $k=2$, since $G$ is connected, every vertex is the endpoint of an edge (that is, a $P_2$). Thus we can arbitrarily define $\varepsilon_2 = c_2 = 1/2$.

If $k > 2$, let $\varepsilon_k = \frac{\varepsilon_{k-1}}{2+\varepsilon_{k-1}}$ and $c_k = \frac{c_{k-1}(1-\varepsilon_k)}{2}$. Let us assume that the first item is false. We will show that the second or the third item is true. Let $v_1$ be any vertex and $S = V(G) \setminus (N(v_1) \cup \{v_2\})$. The size $s$ of $S$ is at least $(1-\varepsilon_k)n - 1$. If $S$ have only *small* connected components, meaning of size at most $s/2$, then one can divide the connected components into two parts with at least $(s+1)/4$ vertices each, and no edges between both parts. This gives in $\bar{G}$ a biclique of size $(s+1)/4 \ge \frac{(1-\varepsilon_k)n}{4}$, thus of size at least $c_k n$ since $c_k \le \frac{1-\varepsilon_k}{4}$. Otherwise, $S$ has a *giant* connected component $S'$, meaning of size $s'$ more than $s/2$. Let $v_2$ be a vertex adjacent both to $v_1$ and to some vertex in $S'$. Observe that $v_2$ exists since $G$ is connected. Consider now the graph $G_2$ induced by $S' \cup \{v_2\}$. The maximum degree in $G_2$ is still at most $\varepsilon_k n = \varepsilon_{k-1}(1-\varepsilon_k)n/2 \le \varepsilon_{k-1}(s'+1)$. By the induction hypothesis, either the second or the third item is true for $G_2$ with parameter $k-1$. The second item gives an induced $P_{k-1}$ in $G_2$ starting at $v_2$, thus an induced $P_k$ in $G$ starting at $v_1$. The third item gives a biclique of size $c_{k-1}|G_2|$ in $\bar{G}_2$. Since $|G_2| = s' + 1 \ge \frac{1-\varepsilon_k}{2}n$, this gives a biclique of size at least $\frac{c_{k-1}(1-\varepsilon_k)}{2}n = c_k n$ and concludes the proof. $\square$

**Theorem 4.** For every $k \ge 2$, $C_k$ has the strong Erdős-Hajnal property. Thus, by Theorem 2, the class $C_k$ has the (weak) Erdős-Hajnal property.

*Proof.* Let $\varepsilon_k$ be as defined in Lemma 3 and $\varepsilon = \varepsilon_k/8 > 0$. By Theorem 1, there exists $\delta > 0$ such that every graph $G$ not inducing $P_k$ or $\bar{P}_k$ does contain an $\varepsilon$-stable set or an $\varepsilon$-clique of size at least $\delta n$. Free to consider the complement of $G$, we can assume that $G$ contains an $\varepsilon$-stable set $S_0$ of size $\delta n$. We start by deleting in $S_0$ all the vertices with degree in $S_0$ at least $2\varepsilon s_0$ where $s_0$ is the size of $S_0$. Since the average degree in $S_0$
is at most $\varepsilon s_0$, we do not delete more than half of the vertices. We call $S$ the remaining subgraph which is a $4\varepsilon$-stable set of size $s \ge \delta n/2$ with maximum degree less than $4\varepsilon s$.

Let $G_S$ be the graph induced by $S$. Our goal is to find a constant $c$ such that $\overline{G_S}$ have a biclique of size $cs$, which gives a biclique in $\overline{G}$ of size at least $c\delta n/2$ and concludes the proof. Assume first that $G_S$ only has small connected components, meaning of size less than $s/2$. Then one can partition the connected components of $G_S$ in order to get a biclique in $\overline{G_S}$ of size $s/4$. Otherwise, $G_S$ has a connected component $S'$ of size $s' \ge s/2$. The degree of every vertex in $S'$ is at most $8\varepsilon s' = \varepsilon_k s'$, and $S'$ does not contain any induced $P_k$ since $G$ does not. By Lemma 3, there exists a biclique of size $c_k s' \ge c_k s/2$ in the complement of the graph induced by $S'$, thus in $\overline{G_S}$. $\square$

[1] N. Alon, J. Pach, R. Pinchasi, R. Radoičić and M. Sharir, Crossing patterns of semi-algebraic sets. *Journal of Combinatorial Theory Series A*, 111(2):310–326, 2005.

[2] N. Alon, J. Pach, and J. Solymosi, Ramsey-type theorems with forbidden subgraphs. *Combinatorica*, 21:155–170, 2001.

[3] M. Chudnovsky, The Erdős-Hajnal Conjecture - A Survey. *Journal of Graph Theory*, 75:178–190, 2014.

[4] M. Chudnovsky and P. Maceli, Simplicial vertices in graphs with no induced four-edge path or four-edge antipath, and the $H_6$ conjecture. *To appear*.

[5] M. Chudnovsky, P. Maceli and I. Penev, Excluding four-edge path and their complements. *Submitted for publication*.

[6] M. Chudnovsky and P. Seymour, Excluding paths and antipaths. *To appear*.

[7] M. Chudnovsky and Y. Zwols, Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement. *Journal of Graph Theory*, 70:449–472, 2012.

[8] P. Erdős and A. Hajnal, Ramsey-type theorems. *Discrete Applied Mathematics*, 25:37–52, 1989.

[9] P. Erdős, A. Hajnal and J. Pach, Ramsey-type theorem for bipartite graphs. *Geombinatorics*, 10:64–68, 2000.

[10] J. Fox and B. Sudakov, Density theorems for bipartite graphs and related Ramsey-type results. *Combinatorica*, 29:153–196, 2009.

[11] J. Fox and B. Sudakov, Induced Ramsey-type theorems. *Advances in Mathematics*, 219:1771–1800, 2008.

[12] J. Fox and J. Pach, Erdős-Hajnal-type results on intersection patterns of geometric objects. *Horizon of Combinatorics* (G.O.H. Katona et al., eds.), Bolyai Society Studies in Mathematics, Springer, 79–103, 2008.

[13] A. Gyárfás, Problems from the world surrounding perfect graphs. *Zastos. Mat.*, 413–441, 1987.

[14] V. Rödl, On universality of graphs with uniformly distributed edges. *Discrete Mathematics*, 59:125–134, 1986.