Absolutely avoidable order-size pairs for induced subgraphs

We call a pair $(m, f)$ of integers, $m \geq 1, 0 \leq f \leq \binom{m}{2}$, absolutely avoidable if there is $n_0$ such that for any pair of integers $(n, e)$ with $n \gt n_0$ and $0 \leq e \leq \binom{n}{2}$ there is a graph on $n$ vertices and e edges that contains no induced subgraph on $m$ vertices and $f$ edges. Some pairs are clearly not absolutely avoidable, for example $(m, 0)$ is not absolutely avoidable since any sufficiently sparse graph on at least m vertices contains independent sets on $m$ vertices. Here we show that there are infinitely many absolutely avoidable pairs. We give a specific infinite set $M$ such that for any $m \in M$, the pair $(m, \binom{m}{2} / 2)$ is absolutely avoidable. In addition, among other results, we show that for any integer function $q(m)$ for which the limit $\lim\limits _{m \to \infty} \frac{q(m)}{m}$ exists, there are infinitely many values of $m$ such that the pair $(m, \binom{m}{2}/2 +q(m))$ is absolutely avoidable.

Keywords

order, size, induced subgraphs, number of edges

2010 Mathematics Subject Classification

Primary 05C35. Secondary 05C75.

Full Text (PDF format)

The authors’ research was partially supported by the DFG grant FKZ AX 93/2-1.

Received 4 August 2021

Accepted 5 September 2022

Published 7 November 2023