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.

The full text of this article is unavailable through your IP address: 3.138.105.128

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